Halvgrupp med två element

I matematik är en halvgrupp med två element en halvgrupp för vilken kardinaliteten för den underliggande mängden är två. Det finns exakt fem icke-isomorfa semigrupper som har två element:

O ₂ , noll-semigruppen av ordning två,
LO ₂ , den vänstra noll-semigruppen av ordning två,
RO ₂ , den högra nollhalvgruppen av ordning två,
({0,1}, ∧) (där "∧" är den logiska kopplingen " och "), eller motsvarande mängden {0,1} under multiplikation: det enda semigitteret med två element och den enda icke-nullhalvgruppen med noll av ordningen två, också en monoid , och slutligen den booleska algebra med två element ,
(Z ₂ , + ₂ ) (där Z ₂ = {0,1} och "+ ₂ " är "addition modulo 2"), eller motsvarande ({0,1}, ⊕) (där "⊕" är den logiska kopplingen " xor "), eller motsvarande mängden {−1,1} under multiplikation: den enda gruppen av ordning två.

Semigrupperna LO ₂ och RO ₂ är antiisomorfa . O ₂ , ({0,1}, ∧) och (Z ₂ , + ₂ ) är kommutativa och LO ₂ och RO ₂ är icke-kommutativa. LO ₂ , RO ₂ och ({0,1}, ∧) är band och även omvända semigrupper .

Bestämning av semigrupper med två element

Genom att välja mängden A = { 1, 2 } som den underliggande mängden med två element, kan sexton binära operationer definieras i A . Dessa operationer visas i tabellen nedan. I tabellen, en matris av formen

x	y
z	t

indikerar en binär operation på A med följande Cayley-tabell .

	1	2
1	x	y
2	z	t

Lista över binära operationer i { 1, 2 }

1	1
1	1

1	1
1	2

1	1
2	1

1	1
2	2

Noll semigroup O ₂

≡ Halvgrupp ({0,1},

\wedge

)

2·(1·2) = 2 , (2·1)·2 = 1

Vänster noll semigrupp LO ₂

1	2
1	1

1	2
1	2

1	2
2	1

1	2
2	2

2·(1·2) = 1 , (2·1)·2 = 2

Höger noll semigrupp RO ₂

≡ Grupp (Z ₂ , + ₂ )

≡ Halvgrupp ({0,1},

\wedge

)

2	1
1	1

2	1
1	2

2	1
2	1

2	1
2	2

1·(1·2) = 2 , (1·1)·2 = 1

≡ Grupp (Z ₂ , + ₂ )

1·(1·1) = 1 , (1·1)·1 = 2

1·(2·1) = 1 , (1·2)·1 = 2

2	2
1	1

2	2
1	2

2	2
2	1

2	2
2	2

1·(1·1) = 2 , (1·1)·1 = 1

1·(2·1) = 2 , (1·2)·1 = 1

1·(1·2) = 2 , (1·1)·2 = 1

Noll semigroup O ₂

I den här tabellen:

Halvgruppen ({0,1}, $\wedge$ ) betecknar tvåelementssemigruppen som innehåller nollelementet zero element 0 and the unit element 1. The two binary operations defined by matrices in a green background are associative and pairing either with A creates a semigroup isomorphic to the semigroup ({0,1}, $\wedge$ ). Every element is idempotent in this semigroup, so it is a band. Furthermore, it is commutative (abelian) and thus a semilattice. The order induced is a linear order, and so it is in fact a lattice and it is also a distributive and complemented lattice, i.e. it is actually the two-element Boolean algebra.
De två binära operationerna som definieras av matriser i en blå bakgrund är associativa och parning antingen med A skapar en semigrupp isomorf till noll-semigruppen O ₂ med två element.
Den binära operationen som definieras av matrisen i en orange bakgrund är associativ och parning av den med A skapar en halvgrupp. Detta är den vänstra noll-semigruppen LO ₂ . Den är inte kommutativ.
Den binära operationen som definieras av matrisen i en lila bakgrund är associativ och parning av den med A skapar en halvgrupp. Detta är den högra noll-semigruppen RO ₂ . Den är inte heller kommutativ.
De två binära operationerna som definieras av matriser i röd bakgrund är associativa och parning antingen med A skapar en semigrupp isomorf till gruppen (Z _{2 ,} + ₂ ) .
De återstående åtta binära operationerna som definieras av matriser i en vit bakgrund är inte associativa och därför skapar ingen av dem en halvgrupp när de paras ihop med A .

Halvgruppen med två element ({0,1}, ∧)

Cayley -tabellen för halvgruppen ({0,1}, ${\displaystyle \wedge })$ ges nedan:

$\wedge$	0	1
0	0	0
1	0	1

Detta är det enklaste icke-triviala exemplet på en semigrupp som inte är en grupp. Denna halvgrupp har ett identitetselement, 1, vilket gör den till en monoid . Den är också kommutativ. Det är inte en grupp eftersom elementet 0 inte har en invers, och är inte ens en kansellativ halvgrupp eftersom vi inte kan ta bort nollan i ekvationen 1·0 = 0·0.

Denna semigrupp uppstår i olika sammanhang. Till exempel, om vi väljer 1 för att vara sanningsvärdet " sant " och 0 för att vara sanningsvärdet " falskt " och operationen för att vara den logiska kopplingen " och ", får vi denna semigrupp i logik . Det är isomorft till monoiden {0,1} under multiplikation. Det är också isomorft till halvgruppen

S=\left\{{\begin{pmatrix}1&0\\0&1\end{pmatrix}},{\begin{pmatrix}1&0\\0&0\end {pmatrix}}\right\}

under matrismultiplikation .

Halvgruppen med två element (Z ₂ , + ₂ )

Cayley -tabellen för halvgruppen (Z ₂ , + ₂ ) ges nedan:

+ ₂	0	1
0	0	1
1	1	0

Denna grupp är isomorf till den _cykliska gruppen Z2 och den _symmetriska gruppen S2 .

Halvgrupper av ordning 3

Låt A vara treelementsmängden {1, 2, 3} . Sammanlagt kan totalt 3 ⁹ = 19683 olika binära operationer definieras på A . 113 av de binära operationerna 19683 bestämmer 24 icke-isomorfa semigrupper, eller 18 icke-ekvivalenta semigrupper (med ekvivalens är isomorfism eller anti-isomorfism). Med undantag för gruppen med tre element har var och en av dessa en (eller flera) av ovanstående tvåelementssemigrupper som undersemigrupper. Till exempel är mängden {−1, 0, 1} under multiplikation en halvgrupp av ordningen 3, och innehåller både {0, 1} och {−1, 1} som undersemigrupper.

Finita halvgrupper av högre ordning

Algoritmer och datorprogram har utvecklats för att bestämma icke-isomorfa ändliga semigrupper av en given ordning. Dessa har använts för att bestämma de icke-isomorfa semigrupperna av liten ordning. Antalet icke-isomorfa semigrupper med n element, för n ett icke-negativt heltal, listas under OEIS : A027851 i On-Line Encyclopedia of Integer Sequences . OEIS : A001423 listar antalet icke-ekvivalenta semigrupper och OEIS : A023814 antalet associativa binära operationer, av totalt n ^{n ²} , som bestämmer en semigrupp.

Se även

Tom semigrupp
Trivial semigroup (semigroup med ett element)
Halvgrupp med tre element
Särskilda klasser av semigrupper