4. Tweetallige bewerkingen

Tweetallige bewerkingen op X zijn functies f : X × X → X. De bewerking wordt vaak aangeduid met een infix *, of ook helemaal zonder symbool, zodat f(x,y) als x*y of als xy geschreven wordt.

(Denk niet dat dat betekent dat er vermenigvuldigd wordt. Het gaat hier om een onbekende bewerking, * is maar een naam.)

De bewerking heet idempotent als x*x = x voor alle x.

De bewerking heet commutatief als x*y = y*x voor alle x en y.

De bewerking heet associatief als x*(y*z) = (x*y)*z voor alle x en y en z.

Voorbeeld (i) De tweetallige bewerking "aftrekken": x*y = x – y (bijvoorbeeld op de reele getallen) is niet idempotent en niet commutatief en niet associatief.
(ii) De tweetallige bewerking "gemiddelde nemen": x*y = (x+y)/2 (bijvoorbeeld op de reele getallen) is idempotent en commutatief, maar niet associatief.
(iii) De tweetallige bewerking "de grootste nemen": x*y = max(x,y) (bijvoorbeeld op de reele getallen) is idempotent en commutatief en associatief.
(iv) Optelling en vermenigvuldiging (van reele of complexe getallen) zijn commutatief en associatief.
(v) Matrixvermenigvuldiging is associatief (maar niet commutatief of idempotent).

Een element e heet een eenheidselement als e*x = x*e = x voor alle x.

Voorbeeld (i) Bij de optelling is 0 eenheidselement.
(ii) Bij de vermenigvuldiging is 1 eenheidselement.
(iii) Bij aftrekken of gemiddelde nemen is er geen eenheidselement.
(iv) Bij "de grootste nemen" is een eenheidselement een kleinste element. Dus op de positieve reele getallen is er geen eenheidselement. Op de niet-negatieve reele getallen is 0 het eenheidselement.

Opgave Een links-eenheidselement is een element e met e*x = x voor alle x. Een rechts-eenheidselement is een element e met x*e = x voor alle x.
(i) Geef een voorbeeld van een bewerking met rechts-eenheidselement maar zonder links-eenheidselement.
(ii) Laat zien dat als er zowel links- als rechts-eenheidselementen zijn, dan zijn ze gelijk. In het bijzonder is er ten hoogste één eenheidselement.

Neem aan dat er een eenheidselement e is. Een element y heet een inverse van x als x*y = y*x = e.

(Weer heb je linksinverse: y*x = e en rechtsinverse: x*y = e.)

4.1 Halfgroepen

Een halfgroep is een algebraïsche structuur (X,*) met een associatieve vermenigvuldiging.

Voorbeeld Neem voor X de verzameling reele getallen groter dan 10. Neem voor * de gewone vermenigvuldiging. Dan is (X,*) een halfgroep zonder eenheidselement.

Het grote voordeel van halfgroepen is dat in willekeurige producten de haakjes weggelaten kunnen worden.

Opgave Bewijs met behulp van de associatieve wet dat in een halfgroep x*((y*z)*w) = (x*y)*(z*w) geldt voor alle x, y, z en w.

Opgave Laat zien dat een element in een halfgroep met eenheidselement hooguit één inverse heeft. (Meer in het algemeen is elke linksinverse gelijk aan elke rechtsinverse.)

4.2 Monoiden

Een monoide is een algebraïsche structuur (X,*,1) waarbij (X,*) een halfgroep is met eenheidselement 1.

Opmerking De formulering zorgt ervoor dat "het eenheidselement kiezen" een van de bewerkingen is. Voor de structuur zelf lijkt dat niet uit te maken: een monoide is gewoon een halfgroep met eenheidselement. Maar zodra je naar deelstructuren gaat kijken is er verschil. Als bijvoorbeeld max de bewerking "de grootste nemen" is, en N = {0,1,2,...} de verzameling natuurlijke getallen, en P = {1,2,...} de verzameling positieve natuurlijke getallen, dan is (P,max) een deelhalfgroep van de halfgroep (N,max), en (P,max) heeft een eenheidselement, namelijk 1, maar P is niet de drager van een deelmonoide van (N,max,0) omdat P niet gesloten is onder de 0-tallige operatie 0.

Kortom, een deelmonoide van een monoide (X,*,1) is een deelverzameling Y van X die 1 bevat en gesloten is onder *.

Voorbeeld Zij A een verzameling (het alfabet) en zij A* de collectie van eindige rijtjes symbolen uit A. De elementen van A* worden woorden genoemd. De verzameling A* wordt een halfgroep met de operatie concatenatie ("achterelkaar zetten"). Deze halfgroep heeft een eenheidselement (het lege rijtje). De monoide (A*,*,  ) met concatenatie * en leeg woord    wordt vrije monoide over A genoemd.

Bijvoorbeeld: met A={0,1} is A* de collectie van alle binaire rijtjes, en 101*10=10110.