Monoid

Gelen matematik bir monoid biridir cebirsel yapılar kullanılan genel cebir . İlişkisel iç kompozisyon yasası ve tarafsız bir unsur ile sağlanan bir settir . Başka bir deyişle, birleşik ve birleşik bir magma , yani birleşik bir yarı gruptur .

Önsöz

Bazen, bir küme ve tek bir işlemden oluşan bir yapının, tersine çevrilebilir elemanlarda, örneğin sadece çarpmanın dikkate alındığı bir halka gibi nispeten zayıf olduğu görülür . Böyle bir yapıya monoid denir . Operasyonun görünürdeki yoksulluğu, Green'in değişmeyen halkalarda bile monoidler veya idealler için ilişkileri gibi belirli bir teoriye yol açar . Diğer bir teknik, basitleştirilebilir bir işlemin varlığında , monoidin bir grup haline getirilmesi için "zenginleştirilmesinden" oluşur .

Bazen, tersine, monoid yapı tamamen yeterlidir. Bu tür için geçerlidir cebir bir çok belirsiz olanlar polinom  : Biz gibi inşa a cebir özellikle Monoid endeksleri kümesi tarafından oluşturulan.

Tanım

Bir monoid, birleşik birleşik bir magmadır .

Biçimsel olarak, ( E , ✻, e ) bir monoid olduğunda, tüm elemanlar için x , y ve z içinde E  :

• x∗y∈E{\ displaystyle x * y \ E’de} (iç hukuk);
• x∗(y∗z)=(x∗y)∗z{\ displaystyle x * (y * z) = (x * y) * z} (çağrışım);
• x∗e=e∗x=x{\ displaystyle x * e = e * x = x}( e nötrdür).

Bir monoid E'nin solda basitleştirildiği veya hatta solda (sırasıyla sağda ) düzenli olduğu söylenir.

∀(-de,b,vs)∈E3,-de∗b=-de∗vs{\ displaystyle \ forall (a, b, c) \ içinde E ^ {3}, a * b = a * c \,}(sırasıyla )b∗-de=vs∗-de{\ displaystyle b * a = c * a \,}⇒b=vs.{\ displaystyle \ Rightarrow b = c.}

Bir monoidin , elemanları değiştirilebilirse , yani eğer:

∀(x,y)∈E2x∗y=y∗x.{\ displaystyle \ forall (x, y) \ içinde E ^ {2} \ quad x * y = y * x.}

(Sonlu) bir dizi elemandan oluşur

Let E olmak bir monoid. Bileşim yasasını çarpımsal biçimde not edelim, yani yukarıda belirtilen bileşiği belirtmek için yazacağız . Nötr eleman daha sonra 1 ile gösterilir. xy{\ displaystyle xy}x∗y{\ displaystyle x * y}

Biz olabilir endüksiyon ile tanımlamak üzerinde n tane ürün bir bölgesinin N -tuple elemanlarının E için: x1⋯xdeğil{\ displaystyle x_ {1} \ cdots x_ {n}}

• 0-demetinin çarpımı eşittir  ;1(0){\ displaystyle 1 \ quad (0)}
• x1⋯xdeğil+1=(x1⋯xdeğil)xdeğil+1(1){\ displaystyle x_ {1} \ cdots x_ {n + 1} = (x_ {1} \ cdots x_ {n}) x_ {n + 1} \ quad (1)}.

Bu tanımı , E'nin bir dizi öğesinin bileşiğine (gösterimimizdeki "ürün") - yani, sonlu, tamamen sıralı bir küme tarafından indekslenmiş bir aileye - genişleterek , kanıtlıyoruz: ∏ben∈benxben{\ displaystyle \ prod _ {i \ in I} x_ {i}} (xben)ben∈ben{\ displaystyle (x_ {i}) _ {i \ I’de}}

• Bir monoidde, bu tanımla veya parantezleri başka herhangi bir şekilde yerleştirerek değerlendirilen bir ürünün aynı sonucu vereceği bir birleşim teoremi (örneğin :) .x1⋯xdeğil{\ displaystyle x_ {1} \ cdots x_ {n}}((-deb)vs)d=(-de(bvs))d=(-deb)(vsd)=-de((bvs)d)=-de(b(vsd)){\ displaystyle ((ab) c) d = (a (bc)) d = (ab) (cd) = a ((bc) d) = a (b (cd))}
• Bir Yerdeğiştirme teoremi değişmeli Monoid hangi birine göre, (ya da daha genel olarak, öğelerinin bir aile için gidip iki adet ikili), sonlu bir ailesinin bir bileşik, bu ailenin endeksi seçilen sırasına bağlı değildir.

Bir sonuç olduğu bir (için , n + 1) -tuple elemanlarının E , (x1,...,xdeğil+1){\ displaystyle (x_ {1}, \ ldots, x_ {n + 1})}

x1⋯xdeğil+1=x1(x2⋯xdeğil+1)(2){\ displaystyle x_ {1} \ cdots x_ {n + 1} = x_ {1} (x_ {2} \ cdots x_ {n + 1}) \ quad (2)}.

Yukarıdaki (0) koşulu ile birleştirilen bu formül (2), n üzerindeki tümevarım yoluyla ifadesinin diğer yaygın tanımıdır . Sonuç , faktör sayısı üzerinden tümevarım yoluyla bu iki tanımın denkliğini kanıtlamayı mümkün kılar . x1⋯xdeğil{\ displaystyle x_ {1} \ cdots x_ {n}}

Alt monoid

Bir Monoid (bir alt-monoid E , ✻, e ) bir alt kümesidir F arasında D karşılamasıdır:

• ∀x,y∈Fx∗y∈F{\ displaystyle \ forall x, y \ in F \ quad x * y \ in F} (kararlı);
• e∈F.F.'de {\ displaystyle e \}

Alt monoidlerin herhangi bir kesişimi bir alt monoiddir.

Bir monoid M'nin bir alt yarı grubu , M'nin bir alt monoidi olmaksızın bir monoid olabilir. Örneğin, M, çarpımı ile ℤ / 6ℤ kümesi tarafından oluşturulan monoid ise , artık sayı çiftleri sınıfları bir M'nin alt yarı grubu D'dir ve artık sınıf 4'ün bu alt yarı grubun nötr bir öğesi olduğunu doğrulamak kolaydır. Bununla birlikte, D, M'nin bir submonoid değildir, çünkü M'nin nötr elemanı (1'in artık sınıfı) D'ye ait değildir.

Bir submonoid ailesinin oluşturulması

P bir monoidin parçası olsun ( E , ✻, e ). P tarafından oluşturulan submonoid olarak adlandırılır (belirtilen P *), P içeren alt monoidler E'nin kesişimi . Bu, P içeren E'nin en küçük submonoididir . Şu şekilde tanımlanabilir:

P∗={x∈E∣∃değil∈DEĞİL,∃(-de1,⋯,-dedeğil)∈Pdeğil,x=-de1∗⋯∗-dedeğil}{\ displaystyle P ^ {*} = \ {x \ E \ ortada \ var n \ mathbb içinde {N}, \ var (a_ {1}, \ cdots, a_ {n}) \ P ^ {n içinde }, x = a_ {1} * \ cdots * a_ {n} \}}

( e öğesi aslında bu kümenin bir parçasıdır: n = 0'a karşılık gelen boş üründür ).

P bir denir üreten aile arasında P *.

En önemsiz olanı, herhangi bir monoid için her zaman bir jeneratör ailesi bulabiliriz.

Serbest bazlar ve monoidler

Bir monoidin ( E , ✻, e ) bir P parçası , E'nin her bir elementin benzersiz bir şekilde ayrıştığı bir üreten E ailesi ise , E'nin temeli olarak adlandırılır.

∀x∈E∃!değil∈DEĞİL∃!(-de1,...,-dedeğil)∈Pdeğil,x=-de1∗⋯∗-dedeğil.{\ displaystyle \ forall x \ in E \ quad \ var! n \ in \ mathbb {N} \ quad \ var! (a_ {1}, \ ldots, a_ {n}) \ P ^ {n}, x = a_ {1} * \ cdots * a_ {n}.}

Bir monoidin bir üssü kabul etmesi halinde özgür olduğu söylenir . Bu durumda taban benzersizdir.

• e asla tabana ait değildir, aksi takdirde elemanlar sonsuz sayıda olası ayrıştırmaya sahip olacaktır.
• Eğer bir set (bazen bir alfabe ) elemanlarının sonlu dizilerin grubu bir (denilen bir deyişle işlem ile) birleştirme olan tanınmış bir serbest monoid bir * ve adı serbest monoid  (in) ile A . Temeli, bir uzunluğundaki kelimeler kümesidir ve bu nedenle doğal olarak alfabeye asimile edilebilir.
• Sonlu alfabeler üzerindeki iki serbest monoid, ancak ve ancak tabanları aynı kardinaliteye sahipse izomorfiktir .
• Serbest bir monoidde, nötr öğe simetrik olan tek öğedir .

Örnekler

• Grubu arasında doğal katkısıyla donatılmıştır olarak 0 nötr elemanı ve 1 tabanının sadece bir eleman olduğu bir serbest monoid vardır.DEĞİL{\ displaystyle \ mathbb {N}}
• DEĞİL{\ displaystyle \ mathbb {N}}çarpımla birlikte nötr eleman 1'den oluşan bir monoid sağlanır. 0 elemanı basitleştirilemez .(∀(değil,m)0.değil=0.m){\ displaystyle (\ forall (n, m) \, 0.n = 0.m \,)}
• DEĞİL{\ displaystyle \ mathbb {N}}iki tamsayı ile ilişkilendiren maksimum kanunu ile sağlandığında, ikisinden büyük olan nötr 0 olan bir monoiddir.
• Bir dizi parçalarının grubu E grubu birliği ile donatılmış, boş grubu nötr bir eleman olduğu bir monoid vardır. Küme kesişimi ile donatılmış aynı küme, aynı zamanda, E'nin nötr eleman olduğu bir monoiddir .
• Grubu uygulamaları ile temin kendi içinde bir set için, bileşimin , bağlı nötr bir monoid olan kimlik uygulaması , solda basitleştirilebilir unsurlardır enjeksiyonlar sağda basitleştirilebilir ve olanlardır surjections .
• Üniter bir halkanın ikinci yasası, monoid bir yapıya sahiptir (eğer halka değişmez ise değişmez ).

Monoid morfizm

( E , ✻, e ) ve ( F , ✮, f ) iki monoid olsun. Biz diyoruz morfizma dan ( E , ✻, e ) ila ( F , ✮, f ) Herhangi bir harita φ gelen E için F böyle

• ∀x,y∈Eφ(x∗y)=φ(x)⋆φ(y){\ displaystyle \ forall x, y \ içinde E \ quad \ varphi (x * y) = \ varphi (x) \ yıldız \ varphi (y)}
• φ(e)=f.{\ displaystyle \ varphi (e) = f.}

İlk özellik, magmaların morfizmidir .

• İki monoid morfizminin bileşiği, monoidlerin bir morfizmidir.
• Bir karşılıklı bijective morfizmalar Monoids ait Monoids bir morfizmanın olduğunu. Sonuç olarak, önyargılı bir morfizm, izomorfizm olarak adlandırılır.
• Bir monoidden basitleştirilebilir bir monoide kadar herhangi bir magma morfizmi, monoidlerin bir morfizmidir.
• Doğal tam sayılar kümesine maks. Yasasını verirsek , n ↦ n + 1 haritası , magmaların bir morfizmidir, ancak monoidlerin bir morfizmi değildir.
• İki monoid arasındaki herhangi bir örtük magma morfizmi , monoid bir morfizmdir.
• Monoid morfizminin çekirdeğini, nötr elementin öncülleri kümesi olarak adlandırıyoruz. Morfizmanın daha sonra çekirdek nötr element indirgenir birebirdir, fakat tersi (bir grup olması durumunda, aksine, genel olarak yanlış ise morfizmalar örneğin bir tarafından, herhangi bir kelime ile uzunluğunu ilişkilendirir morfizmanın:) serbest Monoid de (üzerinde (ℕ, +) 'ya doğru en az) iki eleman , enjekte edici değildir.

• Karşılıklı görüntü Monoids bir morfizma tarafından submonoid bir olduğunu submonoid . Özellikle, bir monoid morfizmin çekirdeği bir submonoiddir.
• Bir submonoid görüntü Monoids bir morfizma bir submonoid olduğunu. Özellikle, bir monoid morfizminin görüntüsü bir submonoiddir.

Monoidlerin doğrudan çarpımı

• ( E , ✻, e ) ve ( F , ✮, f ) iki monoid olsun. Kartezyen ürününe aşağıdaki gibi yeni bir yasa getirerek monoid bir yapı sağlayabiliriz :E×F{\ displaystyle E \ times F \,}∧{\ displaystyle \ kama}

∀(x,y),(x′,y′)∈(E×F)2, (x,y)∧(x′,y′)=(x∗x′,y⋆y′){\ displaystyle \ forall (x, y), (x ', y') \ in (E \ times F) ^ {2}, \ (x, y) \ kama (x ', y') = (x * x ', y \ yıldız y')}.
Nötr bir monoiddir .(e,f){\ displaystyle \ displaystyle (e, f)}

• İki projeksiyonları arasında yer ve içinde in monoid morfizimler vardır. Ve üçlü , doğrudan çarpımın evrensel özelliğini kontrol eder .p:(x,y)↦x{\ displaystyle p: (x, y) \ mapsto x}E×F{\ displaystyle E \ times F}E{\ displaystyle \ displaystyle E}q:(x,y)↦y{\ displaystyle q: (x, y) \ mapsto y}E×F{\ displaystyle E \ times F}F{\ displaystyle \ displaystyle F}((E×F,∧,(e,f)),p,q){\ displaystyle ((E \ çarpı F, \ kama, (e, f)), p, q)}
• Daha genel olarak, yani bir küme ve bir monoid ailesi. Doğrudan ürün yapısını kartezyen ürün üzerine formülle kuruyoruzben{\ displaystyle I}((Eben,∗ben,eben))ben∈ben{\ displaystyle ((E_ {i}, * _ {i}, e_ {i})) _ {i \ I’de}}∏ben∈ben(Eben){\ displaystyle \ prod _ {i \ I} (E_ {i})}

(xben)ben∈ben∗(yben)ben∈ben=(xben∗benyben)ben∈ben.{\ displaystyle (x_ {i}) _ {i \ I'de} * (y_ {i}) _ {i \ I'de} = (x_ {i} * _ {i} y_ {i}) _ {i \ I}.}.

Bir elemanın simetrik

• ( E , ✻, e ) bir monoid ve x bir E öğesi olsun . Biz şunu söylüyoruz:
  • X bir eleman mevcutsa doğru symmetrizable olan y de E , öyle ki X ✻ y = e . Sonra y'nin x'in sağ simetrik olduğunu söyleriz  ;
  • X bir eleman mevcutsa soldaki symmetrizable olan z içinde E , öyle ki z ✻ X = e . Daha sonra z'nin x'in soluna simetrik olduğunu söyleriz  ;
  • Sağda ve solda simetrikse x simetriktir.
• Ne zaman x symmetrizable, bu benzersiz itiraf sağ simetrik ve benzersiz sol simetrik ve bu eşittir.Aslında, yukarıdaki notasyonlarla, y = e ✻ y = ( z ✻ x ) ✻ y = z ✻ ( x ✻ y ) = z ✻ e = z .Bu tek eleman, x'in simetrik olarak adlandırılır ve genellikle x noted1 olarak belirtilir .
• Monoidin simetrik elemanlarının I ( E ) kümesi bir grup oluşturur, çünkü kararlıdır:
  • simetrik olarak: tüm x ∈ I ( E ), x −1 ∈ I ( E ) ve ( x −1 ) −1 = x için  ;
  • çarpıma göre: tüm x , y ∈ I ( E ), x ✻ y ∈ I ( E ) ve ( x ✻ y ) −1 = y −1 ✻ x −1 .Aslında, ( y −1 ✻ x −1 ) ✻ ( x ✻ y ) = y −1 ✻ ( x −1 ✻ x ) ✻ y = y −1 ✻ e ✻ y = y −1 ✻ y = e dolayısıyla da ( ayarlayarak , a = y -1 ve b = x -1 ) ( x ✻ y ) ✻ ( y -1 ✻ x -1 ) = ( b -1 ✻ bir -1 ) ✻ ( bir ✻ b ) = e .
• Kısıtlama ile, iki monoid arasındaki herhangi bir morfizm φ: ( E , ✻, e ) → ( F , ✮, f ), I ( E ) 'den I ( F )' ye bir grup morfizmini indükler .
  In kategori teorisi , gerçeği yorumlamada söyleyerek ben bir olduğunu funktor gelen Monoids kategorisinde yer grubundan (olan sağ eşlenik ait unutmadan funktor M  : Grp → My ).

Simetri

Biz genelleme ilgili tam sayı inşaatı gelen doğal tam sayı ile, kanonik birleştirilmesi için herhangi bir değişmeli monoid E = ( S +, 0), bir değişmeli grubu G ( E ), onun adı Grothendieck grubu arasından Monoids bir morfizma sahip, M G içine ( M ).

Yapım sürecine monoid simetrizasyon denir. Bunun için , S × S üzerindeki ∼ eşdeğerlik ilişkisini şu şekilde tanımlıyoruz:

(m,değil)∼(p,q)⇔∃k∈Sm+q+k=p+değil+k.{\ displaystyle (m, n) \ sim (p, q) \ Leftrightarrow \ S \ quad m + q + k = p + n + k içinde k \ var.}

G grubu ( E ) unsurları olarak ~ denklik sınıfları ve doğal morfizmalar sahiptir M G ( E ) herhangi bir elemanı ile ilişkilendirir x ait S (sınıf x , 0). Bu morfizm, ancak ve ancak M basitleştirilebilirse enjekte edicidir ; bu durumda, ∼ ilişkisi daha basit bir şekilde tanımlanabilir:

(m,değil)∼(p,q)⇔m+q=p+değil.{\ displaystyle (m, n) \ sim (p, q) \ Leftrightarrow m + q = p + n.}

Başvurular

Monoid, bir elemanın yinelemelerini tanımlamak için uygun bir çerçevedir .

Gelen teorik bilgisayar bilimleri , Monoidler ve özellikle serbest Monoid özellikle, en kullanılan yapılar arasında yer alıyor kodlarının teorisi ve dillerin teorisi .

"Monoid" terimi , 1970'lerde, Pour un art schématique: study d'un monoïdeographique , Éditions de Beaune et Goutal-Darley, 1978 adlı kitabında kendisini haklı çıkaran ressam Jean-Claude Bédard ile çağdaş sanata giriş yaptı .

Notlar ve referanslar

1. Bu bölüm çok daha ayrıntılı olduğu “Bir dizinin oluşan” bölümünde monoidler ders Vikiversite üzerinde .
2. N. Bourbaki , Cebir, bölüm 1 ila 3 , Springer ,2007, ch. I, § 1, n o  3, s.  4 ve § 2, n o  1, s.  13 .
3. Bourbaki 2007 , bölüm. I, § 1, teori. 2, s. 8.
4. Bourbaki 2007 , bölüm. I, § 2, n o  1, s. 13.
5. (in) Arjeh Cohen, Hans Cuypers ve Hans Sterk, Cebir Etkileşimli !: Cebiri Heyecanlı Bir Şekilde Öğrenme Springer1999( çevrimiçi okuyun ) , s.  71.
6. (inç) Henri Bourlès ve Bogdan Marinescu Doğrusal Zamanla Değişen Sistemler: Cebirsel-Analitik Yaklaşım , Springer,2011( çevrimiçi okuyun ) , s.  30.
7. Bir gösteri için, örneğin Wikiversity'deki ilgili alıştırmanın cevabına bakınız .

İlgili Makaleler

• Yarım grup
• Dijital monoid

Kaynakça

(en) Alfred H. Clifford ve Gordon B. Preston , The Cebebraic Theory of Semigroups , cilt.  (1 2 inci ed. 1964) ve Vol. 2 (yeniden baskı 1988), AMS

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">