Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Pin{ / A Automata and semigroups / 02 Semigroups and beyond
Tags: fromMath mathToDef hasSeenConjDef automaticImplies closed complex exampleToQuestion examplesSwitchExample1 toBinaryRelation defToAlgebra setMultiplication toAlgebra typToBinary

Name: The order of \(S\)
Definition: The number of elements of \(S\).
Page: 13
Chapter: II
Section: 1.1
Variables: \(S\) a finite semigroup.

Name: An idempotent element of \(S\)
Definition: An element \(s\in S\) such that \(ss=s\).
Page: 14
Chapter: II
Section: 1.2
Variables: \((S,\cdot)\) a semigroup.

Name: A right identity
Definition: An element \(s\in S\)such that \(ts=t\) for all \(t\in S\).
Page: 14
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup
\(s\in S\)
Typ: Idempotent

Smaller0: \(r,t\) are idempotent of \(S^1\)
Greater0: \(rs=s=st\)
Page: 14, 135
Chapter: II, VI
Section: 1.2, 3
Variables: \(S\) be a semigroup
\(r,s,t\in S\).
Index: 1.1, 5
Kind: Prop, Lem
Smaller1: \(S\) is aperiodic
Name: Simplification lemma
Extra: similaire avec H?
Prefix Smaller: (
Connect Smaller0: or
Construction: in case of idempotence:
\(s=rst\) thus \(rs=rst=rst=s\)
in case of aperiodicity
\(s=r^nst^n\) thus \(rs=rr^nst^n=r^nst^n=s\)
and similarly \(st=s\) by symmetry
Smaller2: \(s=rst\)
Connect Smaller1: ) and

Name: A zero
Definition: An element \(s\) such that, for all \(t\in S\), \(ts=s=st\).
Page: 14
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup.
Cardinal: At most one

Name: A null semigroup
Definition: A semigroup such that, equivalently the range of the product contains a single element
Page: 14
Chapter: II
Section: 1.2

Name: Left cancellative element of \(S\)
Definition: An element \(s\in S\) such that \(sx=sy\) implies \(x=y\) for all \(x,y\in S\).
Page: 15
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup

Name: Right cancellative element of \(S\)
Definition: An element \(s\in S\) such that \(xs=ys\) implies \(x=y\) for all \(x,y\in S\).
Page: 15
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup

Name: A cancelative element of \(S\)
Definition: A right and left cancelative element.
Page: 15
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup
\(s\in S\).

Name: A left group inverse of \(t\)
Definition: An element \(s\) such that \(st=1\).
Page: 15
Chapter: II
Section: 1.2
Variables: \(M\) be a monoid
\(s,t\in M\).

Name: A right group inverse of \(t\)
Definition: An element \(s\) such that \(ts=1\).
Page: 15
Chapter: II
Section: 1.2
Variables: \(M\) be a monoid and \(s,t\in M\).

Name: Left cancellative monoid
Definition: A monoid such that all of its elements are left cancellative.
Page: 15
Chapter: II
Section: 1.2

Name: Right cancellative monoid
Definition: A monoid such that all of its elements are right cancellative.
Page: 15
Chapter: II
Section: 1.2

Name: A ring
Definition: A semiring \((S,+,\times,0,1)\) such that \((S,+,0)\) is a group.
Page: 16
Chapter: II
Section: 1.5
Variables: \((S,+,\times,0,1)\) a semiring.

Definition: The set of elements of \(\{0,1\}^{n\times n}\) with at most one 1.
Page: 17
Chapter: II
Section: 2.1
Variables: \(n\in\mathbb N\).
Notation: \(B_n\)
Index: (3)

Name: A left-zero semigroup
Definition: \((S,(s,t)\mapsto s)\) for \(S\) a set
Page: 17
Chapter: II
Section: 2.1
Index: (4)

Name: Cancellative semigroup without identity.
Page: 19
Chapter: II
Section: 2.1
Index: (5)
Example: The set of matrices of the form \(\left(\begin{array}{ll}a&0\\b&1\end{array}\right)\), with \(a,b>0\).

Name: An isomorphism
Definition: A bijective morphism
Page: 20
Chapter: II
Section: 3.1
Index: 7
Kind: Prop

Name: A bijective morphism of ordered semigroup which is not iso
Page: 20
Chapter: II
Section: 3.1
Example: The identity \((\mathbb N,=)\to(\mathbb N,\le)\).

Name: A quotient of \(S\)
Definition: A semigroup \(T\) such that there exists a surjective morphism from \(S\) onto \(T\).
Page: 21
Chapter: II
Section: 3.3
Variables: \(S\) be semigroups.
Example: \(\mathbb Z/2\mathbb Z\)
Applied to: \(\mathbb Z/4\mathbb Z\)
Counterexample: \(\mathbb Z/2\mathbb Z\) is a quotient of \((\mathbb Z/4\mathbb Z)^0\)

Page: 21
Definition: \(T\) is a quotient of a subsemigroup of \(S\).
Chapter: II
Section: 3.3
Variables: \(S,T\) be semigroups.
Notation: \(T\preccurlyeq S\)
Name: \(T\) divides \(S\)
Transitive: Transitive relation
Extra: notation quotient
Example: \(\mathbb Z/2\mathbb Z\) does not divide \((\mathbb Z/4\mathbb Z)^0\)

Name: A left ideal
Definition: A set \(H\subseteq S\) such that \(SH\subseteq H\).
Page: 4, 22
Chapter: Howie, 1, II
Section: 1, 3.5
Variables: \(S\) a semigroup
\(H\subseteq S\).
Definition2: A set \(S^1A\) for some \(A\subseteq S\)

Name: An ideal
Definition: A left and right ideal.
Page: 24
Chapter: II
Section: 3.5
Variables: \(S\) a semigroup.

Name: A principal ideal
Definition: An ideal generated by a single element.
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup,

Name: A minimal ideal of \(S\)
Definition: A nonempty ideal \(I\) of \(S\) such that, for all nonempty ideal \(J\subseteq I\), \(J=I\).
Page: 23
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup
Index: 3.17
Kind: Prop
Extra: une condition implique l'autre

Name: A 0-minimal ideal of \(S\)
Definition: An ideal \(I\) of \(S\) such that, for all nonempty ideal \(J\subseteq I\), \(J\in\{\{0\},I\}\).
Page: 23
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup.

Name: A simple semigroup
Definition: whose only ideal are \(\emptyset\) and \(S\).
Page: 24, 497
Chapter: II, XI
Section: 3.6, 4.2
Index: 19
Definition2: satisfying \((xyx)^\omega=x^\omega\) and \(x^{\omega+1}=x\) (assuming finiteness)
Conjdef: A semigroup, equivalently

Name: A semigroup congruence
Definition: A binary relation \(\sim\), such that for all \(s,t\in S\), \(u,v\in S^ 1\), \(s\sim t\) implies \(usv\sim utv\).
Page: 24
Chapter: II
Section: 3.7
Variables: \(S\) be a semigroup

Name: The Rees congruence of an ideal \(I\)
Definition: equal elements and
Page: 24
Chapter: II
Section: 3.7
Variables: \(S\) be a semigroup and \(I\) an ideal of \(S\).
Notation: \(\equiv_I\)
Definition2: the pair of elements of \(I\).
Conjdef: The binary relation containing

Definition: \(S/\equiv_I\).
Page: 24
Chapter: II
Section: 3.7
Variables: \(S\) a semigroup
\(I\) an ideal of \(S\).
Notation: \(S/I\)

Name: A congruence of ordered semigroup
Definition: A stable preorder \(\underline\prec\) coarser than \(\le\).
Page: 27
Chapter: II
Section: 3.7
Variables: \(M\) an ordered semigroup.
Kind: (e)

Name: [Partial] transformation on \(P\)
Definition: [Partial] function from \(P\) to \(P\).
Page: 27
Chapter: II
Section: 4.1
Variables: \(P\) a set.

Name: Faithful right action
Definition: A right action such that, for all \(p\in P\), \(s,t\in S\), \(ps=pt\) implies \(s=t\).
Page: 27
Chapter: II
Section: 4.1
Variables: \(S\) a semigroup, \(P\) a set and \(\cdot\) a right action.

Name: A transformation semigroup
Definition: \((S,\cdot)\) a semigroup and
Page: 27
Chapter: II
Section: 4.1
Definition2: \(\circ\) a faithful action.
Conjdef: A pair \(((S,\cdot),\circ)\) with

Name: The transformation semigroup induced by the action of \(S\) on \(P\)
Definition: The tranformation semigroup on \((P,S/\sim)\).
Page: 27
Chapter: II
Section: 4.1
Variables: \(P\) be a set,
\(S\) a semigroup,
\(\cdot\) an action of \(S\) on \(P\)
\(\sim\) the congruence on \(S\) induced by this equivalence.

Name: A fixed-point-free transformation semigroup
Definition: \((P,S,\cdot)\) a transformation semigroup such that for every \(p\in P\), and every \(s\in S\), \(ps=p\) implies \(s=s^2\).
Page: 28
Chapter: II
Section: 4.1

Name: The full transformation semigroup on a set \(P\)
Definition: The set of all transformation on \(P\).
Page: 28
Chapter: II
Section: 4.2
Variables: \(P\) a set.
Notation: \(\mathcal T(P)\)

Definition: \(\mathcal T(\{1,\dots,n\})\).
Page: 28
Chapter: II
Section: 4.2
Variables: \(n\in\mathbb N\).
Notation: \(\mathcal T_n\)

Name: The symmetric group of a permutation \(P\)
Definition: The set of permutation on \(P\).
Page: 28
Chapter: II
Section: 4.2
Variables: \(P\) a set.
Notation: \(\mathcal S(P)\)

Definition: \(\mathcal S(\{1,\dots,n\})\).
Page: 28
Chapter: II
Section: 4.2
Variables: \(n\in\mathbb N\)
Notation: \(\mathcal S_n\)

Smaller0: \(S\) divides \(T\)
Greater0: \((S^ 1,S)\) divides \((T^1,T)\)
Page: 29
Chapter: II
Section: 4.3
Variables: \(S,T\) semigroups.
Index: 27
Kind: Prop
Smaller to greater: iff
Hide sides: yes

Definition: The number of \(a\) in the word \(u\).
Page: 30
Chapter: II
Section: 5.3
Variables: \(A\) an alphabet
\(u\in A^*\)
\(a\in A\).
Notation: [$]\abs{u}_a[/$]

Definition: The length of the word \(u\).
Page: 30
Chapter: II
Section: 5.3
Variables: \(A\) an alphabet,
\(u\in A^*\).
Notation: [$]\abs{u}[/$]

Definition: The set of non-empty words on \(A\).
Page: 30
Chapter: II
Section: 5.3
Variables: \(A\) an alphabet.
Notation: \(A^+\)

Definition: The set of words on \(A\)
Page: 30
Chapter: II
Section: 5.3
Variables: \(A\) an alphabet.
Notation: \(A^*\)

Name: The set of idempotents of \(S\)
Page: 33
Chapter: II
Section: 6
Variables: \(S\) a semigroup.
Notation: \(E(S)\)
Index: 35
Kind: Cor

Name: A \(r\)-subset of \(E\)
Definition: A subset of \(E\) of cardinal \(r\).
Page: 33
Chapter: II
Section: 6
Variables: \(E\) a set
\(r\in\mathbb N\).

Question: The number of minimal ideal is
Answer: at most one.
Page: 23
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup.
Index: 17
Kind: Prop
Construction: Ideal are closed under intersection

Name: The index of \(S\)
Definition: The least \(n\) such that \(x^{n}=x^{n+m}\), for \(x\) a generator.
Page: 34
Chapter: II
Section: 6
Variables: \(S\) a monogenic semigroup.

Name: The period of \(S\)
Definition: The least \(m\) such that \(x^{n}=x^{n+m}\), for \(x\) a generator.
Page: 32
Chapter: II
Section: 6
Variables: \(S\) a monogenic semigroup.

Smaller0: \(T\) is a quotient of \(S\)
Greater0: \(T\) divides \(S\)
Page: 21
Chapter: II
Section: 3.3
Variables: \(S,T\) semigroups

Name: A right ideal
Definition: A set \(A\subseteq S\) such that \(AS\subseteq A\)
Page: 22, 9, 4
Chapter: Mathematical fundation Pin II, Infinite automata pin 1, Howie 1
Section: 3.5, 2, 1
Variables: \((S,\cdot)\) a semigroup
Definition2: A set of the form \(AS^1\)

Definition: \(S\) if \(S\) is a monoid,
Page: 14
Chapter: II
Section: 1.1
Variables: \((S,\cdot)\) a semigroup.
Notation: \(S^1\)
Definition2: \(S\cup{1}\) where \(1\) is an identity otherwise
Conjdef: Either

Name: \(B(I,J)\)
Definition: The set \(I\times J\)
Page: 15
Chapter: II
Section: 2.1
Variables: \(I,J\) two non-empty sets.
Index: (2)
Definition2: Product \((i,j)(i',j')\mapsto(i,j')\)
Conjdef: The semigroup

Name: \((P,S)\) divide \((Q,T)\)
Definition: There exists a surjective partial function \(\pi:Q\to P\)
Page: 29
Chapter: II
Section: 4.3
Variables: \((P,S)\), \((Q,T)\) transformation semigroups.
Definition2: for every \(s\in S\), an element \(\widehat s\in T\), called a cover of \(s\), such that
Conjdef: -
Definition3: for each \(q\in\text{Dom}(\pi)\), \(\pi(q)\cdot s =\pi(q\cdot \widehat s)\).

Definition: The set \(\{1,a_1,\dots,a_n\}\) with \(a_i1=1a_i=a_i\) and \(a_ia_j=a_j\) is noted
Page: 20
Chapter: II
Section: 2.2
Variables: \(n\in\mathbb N\)
Notation: \(U_n\).
Index: (5)

Question: The product of \(I_1,\dots,I_n\) is
Answer: an ideal contained in their intersection.
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup,
\(I_1,\dots,I_n\) be ideals of \(S\).
Index: 16
Kind: Proposition
Construction: \(S^1I_1\dots I_nS^1=(S^1I_1)I_2\dots I_{n-1}(I_nS^1)=I_1\dots I_n\)

Question: There exists a unique
Answer: semigroup morphism \(\overline\phi:S/\sim_\phi\to T\) such that \(\phi=\overline\phi\circ\pi\) and \(\overline\phi\) is an isomorphism from \(S/\sim_\phi\) onto \(\phi(S)\).
Page: 26
Chapter: II
Section: 3.7
Variables: \(\phi:S\to T\) be a morphism of semigroup
\(\pi:S\to S/\sim _\phi\) be the quotient morphism.
Index: 21
Kind: Prop

Question: \(S/\sim_\phi\) is isomorph to
Answer: \(\phi(S)\).
Page: 26
Chapter: II
Section: 3.7
Variables: \(S,T\) groups
\(\phi:S\to T\) a morphism.
Context: Group morphism
Index: 21
Kind: Prop
Name: First isomorphism theorem:

Question: Second isomorphism theorem concerns:
Answer: A congruence and a coarser congruence.
Page: 26
Chapter: II
Section: 3.7
Index: 21
Kind: Prop

Question: \(S\) is isomorphic to
Answer: a subsemigroup of the monoid \(\mathcal T(S^ 1)\).
Page: 28
Chapter: II
Section: 4.2
Variables: \(S\) a semigroup.
Index: 25
Kind: Prop
Construction: for each \(s\in S\), associate it the function [$]\rho_s:\defFun{S^1}{S^1}{x}{xs}\in\mathcal T(S^1)[/$]

Question: \(G\) is isomorphic to
Answer: a subgroup of \(\mathcal S(G)\).
Page: 28
Chapter: II
Section: 4.2
Variables: \(G\) a group.
Index: 26
Kind: Prop
Name: Cayley's theorem
Construction: for each \(s\in G\), associate it the function [$]\rho_s:\defFun{G}{G}{x}{xs}\in\mathcal T(G)[/$]

Name: The product of the \(\left(P_i,S_i\right)\)
Definition: \(\left(\Pi_{i\in I}P_i,\Pi_{i\in I}S_i\right)\)
Page: 28
Chapter: II
Section: 4.3
Variables: \(\left(P_i,S_i\right)_{i\in I}\) a family of tranformation semigroup.

Question: \(\{e^i\mid i\in\mathbb N\}\) contains
Answer: an idempotent
Page: 30
Chapter: II
Section: 6
Variables: \(S\) a semigroup
\(e\in S\).
Index: 31
Kind: Prop
Extra: finite ?

Question: For every sequence [$]s_1,\dots,s_{\abs{S}}[/$], there exists
Answer: an index [$]i\in \{1,\dots,\abs{n}\}[/$] and an idempotent \(e\in S\) such that \(s_1\dots s_ie=s_1\dots s_i\).
Page: 33
Chapter: II
Section: 6
Variables: \(S\) be a finite semigroupc
Index: 34
Kind: Prop

Definition: for every finite set \(E\) having at least \(N\) elements and
for every \(m\)-colouring of the set of the \(r\)-subsets of \(E\),
Page: 33
Chapter: II
Section: 6
Variables: \(r,k,m\in\mathbb N^{>0}\)
Notation: \(R(r,k,m)\)
Index: 36
Kind: Theo
Definition2: there exists a \(k\)-subset of \(E\)
Conjdef: An integer \(N\) such that
Definition3: of which all \(r\)-subsets have the same colour.
Assuming: \(k\ge r\)
Hide remaining def: yes

Question: what can be said about factorization of long words of \(A^+\) in \(k\)-factors
Answer: There exists an integer \(N > 0\) such that,
for every alphabet \(A\),
for every morphism \(\phi : A^ + \to S\) and
for every word \(w=a_0\dots a_n\) of \(A^ +\) of length greater than or equal to \(N\) ,
there exists
an idempotent \(e\in S\) and a factorisation \(w = xu_ 1\dots u_ k y\) with \(x, y \in A^*\),
\(u_1,\dots, u_ k \in A^ +\) and \(\phi(u_ 1 ) = \dots = \phi(u_ k ) = e\).
Page: 33
Chapter: II
Section: 6
Variables: \(A\) an alphabet.
\(k>0\)
Index: 37
Kind: theo
Construction: [$]N=R(2,k+1,\abs{S})[/$]
By Ramsey, there exists a set \(T=\{i_0,\dots,i_k\}\subseteq \{0,\dots,n\}\) such that for each \(i<j,i'<j'\in T\), \(\phi(a_i\dots a_j)=\phi(a_{i'}\dots a_{j'})\), take \(u_i=a_i\dots a_{i+1}\). Note that \(\phi(u_i)\phi(u_{i+1})=\phi(u_iu_{i+1})=\phi(u_i)\phi(u_{i+1})\) and \(\phi(u_i)=\phi(u_{i+1})\), thus \(\phi(u_i)\) is idempotent

Question: what can be said about factorization of long sequence of words of \(A^+\) in \(k\)-factors
Answer: For any \(n > 0\),
there exists \(N > 0\) and
an idempotent \(e\) in \(M\)
such that, for any \(u_0,u_ 1 ,\dots,u_ N\in A^*\) there exists
a sequence \(0\le i_ 0< i_ 1<\dots< i_ n\le N\) such that \(\pi(u_ {i_j} u_{ i_ j +1}\dots u _{i_{j+1}-1})=e\).
Page: 34
Chapter: II
Section: 6
Variables: \(A\) an alphabet.
\(M\) be a finite monoid
\(\pi:A^*\to M\) be a surjective morphism.
Index: 38
Kind: Theo
Construction: [$]N=R(2,k+1,\abs{S})[/$]
By Ramsey, there exists a set \(T=\{i_0,\dots,i_k\}\subseteq \{0,\dots,N\}\) such that for each \(i<j,i'<j'\in T\), \(\pi(u_i\dots u_j)=\pi(u_{i'}\dots u_{j'})\), take \(v_i=u_i\dots u_{i+1}\). Note that \(\pi(v_i)\pi(v_{i+1})=\pi(v_iv_{i+1})=\pi(u_i)\pi(u_{i+1})\) and \(\pi(u_i)=\pi(u_{i+1})\), thus \(\pi(u_i)\) is idempotent

Smaller0: \(S\) have zero
Greater0: isomorphic to a subsemigroup of \(S/I_1\times S/I_2\)
Page: 27
Chapter: II
Section: 3.7
Variables: \(S\) be a semigroup.
\(I_1,I_2\subseteq S\).
Index: 24
Kind: Cor
Prefix Greater: \(S\) is
Smaller1: \(I_1\) and \(I_2\) are two distinct \(0\)-minimal ideals
Construction: Apply cor 23 with \(\sim=\cong_{I_1}\cap\cong_{I_2}=\{0\}\), and \(S=S/\sim\)

Name: The dual semigroup of \((S,\cdot)\)
Definition: \((S,\star)\) such that \(x\star y=y\cdot x\).
Page: 15
Chapter: II
Section: 1.1
Variables: \((S,\cdot)\) a semigroup.

Definition: \((S\cup \{0\},\star)\) with \(0\star x=x\star 0=0\) and \(x\star y=x\cdot y\).
Page: 16
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup.
Notation: \(S^0\)

Name: A group inverse of \(t\)
Definition: A right and left group inverse of \(t\).
Page: 17
Chapter: II
Section: 1.2
Variables: \(S\) be a semigroup
\(t\in S\).
Cardinal: At most one

Smaller0: a group
Greater0: each element has a left inverse
Page: 18
Chapter: II
Section: 1.3
Variables: \(S\) be a monoid.
Kind: Proposition
Smaller to greater: iff
Hide middle: yes
Extra: 1.4
Prefix Smaller: \(S\) is
Suffix Greater: )
Greater2: it is finite
Connect Greater1: (
Greater3: each element has a right inverse
Connect Greater2: or

Name: An ordered semigroup
Definition: \((S,\cdot)\) a semigroup
Page: 18
Chapter: II
Section: 1.2
Variables: Let \(S\) be a monoid.
Definition2: an order \(\le\) for every \(x,y\in S\), for every \(u,v\in S^ 1\), \(x\le y\) implies \(uxv\le uyv\).
Conjdef: A tuple

Name: A semiring
Definition: \((S,+,0)\) is a commutative monoid
Page: 18
Chapter: II
Section: 1.5
Definition2: \((S,\times,1)\) is a monoid with zero 0
Conjdef: A tuple \((S,+,\times,0,1)\) with
Definition3: multiplication is distributive over addition.

Page: 20
Chapter: II
Section: 2.2
Notation: Semirings which are not a ring
Example: (Boolean, \(\lor,\land\))
Example2: \((\mathbb N,+,\times)\),
Example3: \((\mathbb N\cup\{\infty\},+,\times)\)
Example4: \(\mathcal P(M)\) for \(M\) a monoid, with union and the monoid product.

Page: 20
Chapter: II
Section: 2.2
Name: The bicyclic monoid
Set: \(\mathbb N^2\)
*: \(((i,j),(i',j')\mapsto (i+i'-\min(j,i'),j+j'-\text{min}(j,i'))\)
Index: (7)
Relation: \(ab=1\)
Generating family: \(\{a,b\}\)

Definition: \(U_1=\{1,0\}\) ordered by \(1<0\).
Page: 20
Chapter: II
Section: 2.4
Notation: \(U^+_1\)
Index: (3)

Definition: \(U_1=\{1,0\}\) ordered by \(0<1\).
Page: 20
Chapter: II
Section: 2.4
Notation: \(U^-_1\)
Index: (3)

Name: The universal counterexample
Definition: \(B_2\).
Page: 19
Chapter: II
Section: 2.1
Index: (3)
Definition2: \(\{a,b,ab,ba,0\}\) with \(aa=bb=0\), \(aba=a\) and \(bab=b\).

Smaller0: \(f\) is a semigroup morphism
Greater0: \(f\) is a group morphism
Page: 21
Chapter: II
Section: 3.1
Variables: \(G,H\) two semigroups
\(f:G\to H\).
Index: 6
Kind: Prop
Smaller1: \(G,H\) are groups

Name: A subsemigroup of \((S,\cdot)\)
Definition: A set \(T\subseteq S\) such that \(tt'\in T\) for all \(t,t'\in T\).
Page: 21
Chapter: II
Section: 3.1
Variables: \((S,\cdot)\) a semigroup.

Smaller0: the left ideal generated by \(e\)
Greater0: \(Se\)
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup
\(e\in S\) idempotent.
Smaller to greater: is equal to
Hide middle: yes
Suffix Smaller: of \(S\)

Smaller0: the ideal of \(S\) generated by \(e\)
Greater0: \(SeS\)
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup
\(e\in S\) idempotent.
Smaller to greater: is equal to
Hide middle: yes

Smaller0: the right ideal generated by \(e\)
Greater0: \(eS\)
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup and \(e\in S\) idempotent.
Smaller to greater: is equal to
Hide middle: yes
Suffix Smaller: of \(S\)

Smaller0: \(T'\) is a subsemigroup of \(T\) and \(\phi\) is a semigroup morphism
Greater0: a subsemigroup of \(S\)
Page: 22
Chapter: II
Section: 3.2
Variables: \(S,T\) be semigroups
\(\phi:S\to T\)
\(T'\subseteq T\)
Index: 3.8
Kind: Prop
Prefix Greater: \(\phi^{-1}(T')\) is

Question: An equivalence classes of the division is
Answer: an isomorphic class.
Page: 23
Chapter: II
Section: 3.3
Context: Semigroup
Index: 10
Kind: Prop

Name: The ideal generated by \(R\)
Definition: The smallest ideal containing \(R\).
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup,
\(R\subseteq S\).
Definition2: \(S^1RS^1\)

Name: The left ideal generated by \(R\)
Definition: The smallest left ideal containing \(R\).
Page: 24
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup,
\(R\subseteq S\).
Definition2: \(S^1R\)

Name: The right ideal generated by \(R\)
Definition: the smallest right ideal containing \(R\).
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup,
\(R\subseteq S\).
Definition2: \(RS^1\)
Extra: Do the same for 3 notes, for e instead of \(R\)

Name: A principal right ideal
Definition: A right ideal generated by a single element.
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup
\(R\subseteq S\).

Name: A principal left ideal
Definition: A left ideal generated by a single element.
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup
\(R\subseteq S\).

Name: The right Cayley graph of \(M\)
Definition: A labelled graph with \(M\) as vertices and \((m,a,ma)\) as edges.
Page: 32
Chapter: II
Section: 5.2
Variables: \(M\) an \(A\)-generated monoid

Name: The left Cayley graph of \(M\)
Definition: A labelled graph with \(M\) as vertices and \((m,a,am)\) as edges.
Page: 32
Chapter: II
Section: 5.2
Variables: \(M\) an \(A\)-generated monoid

Name: A submonoid of \((S,\cdot,1)\)
Definition: a subsemigroup of \((S,\cdot)\) containing 1.
Page: 22
Chapter: II
Section: 3.2
Variables: \((S,\cdot,1)\) a monoid.

Name: A subgroup of \((S,\cdot,1)\)
Definition: A submonoid closed by inverse.
Page: 22
Chapter: II
Section: 3.2
Variables: \((S,\cdot,1)\) a monoid.

Name: A subgroup of \(S\)
Definition: A submonoid \(T\) containing an idempotent \(e\) such that \((T,\cdot, e)\) is a group.
Page: 22
Chapter: II
Section: 3.12
Variables: \((S,\cdot)\) a semigroup.

Smaller0: \(S'\) is a subsemigroup of \(S\)
Greater0: a subsemigroup of \(T\)
Page: 22
Chapter: II
Section: 3.2
Variables: \(S,T\) be semigroups,
\(\phi:S\to T\) and
\(S'\subseteq S\).
Index: 3.8
Kind: Prop
Hide middle: yes
Prefix Greater: \(\phi(S')\) is
Smaller1: \(\phi\) is a semigroup morphism

Smaller0: \(H\) is non empty
Greater0: \(H\) is a subgroup of \(G\)
Page: 24
Chapter: II
Section: 3.3
Variables: \(G\) a group and
\(H\subseteq G\).
Index: 3.13
Kind: Proposition
Smaller1: \(G\) is finite
Construction: \(H\) is closed under product.
For each \(h\in H\), some \(h^n=1\), thus the inverse is \(h^{n-1}\)
Smaller2: \(H\) is a subsemigroup

Smaller0: a family of subsemigroup/quotient/divisor of \((T_i)_{i\in I}\)
Greater0: a subsemigroup/quotient/divisor of \(\Pi_{i\in I}(T_i)\)
Page: 24
Chapter: II
Section: 3.4
Variables: \(I\) a set
\((S_i)_{i\in I}\)
\((T_i)_{i\in I}\) semigroups.
Index: 14
Kind: Prop
Hide middle: yes
Prefix Greater: \(\Pi_{i\in I}S_i\) is
Prefix Smaller: \((S_i)_{i\in I}\) is

Smaller0: \(J\) is an ideal of \(T\)
Greater0: an ideal of \(S\)
Page: 25
Chapter: II
Section: 3.5
Variables: \(S,T\) semigroups
\(\phi:S\to T\) a semigroup morphism
\(J\subseteq T\).
Index: 15
Kind: Prop
Hide middle: yes
Prefix Greater: \(\phi^{-1}(J)\) is
Construction: \(x,z\in S, y\in\phi^{-1}(J)\).
\(\phi(y)\in J\) and \(J\) ideal thus \(\phi(x)\phi(y)\phi(z)\in J\)
\(xyz\in\phi^{-1}(\phi(xyz))=\phi^{-1}(\phi(x)\phi(y)\phi(z))\subseteq\phi^{-1}(J)\)

Name: A 0-simple semigroup
Definition: \(S\) have a zero,
\(S^2\ne\{0\}\),
\(\emptyset, \{0\},S\) are the only ideals of \(S\)
Page: 26
Chapter: II
Section: 3.6
Index: 19
Kind: Prop
Definition2: \(SsS=S\) for all \(s\in S\setminus0\)
Conjdef: A semigroup \(S\) such that, equivalently

Name: A simple semigroup
Definition: \(SsS=S\) for all \(s\in S\)
Page: 26
Chapter: II
Section: 3.6
Index: 3.19
Kind: Prop
Definition2: the only ideals are \(\emptyset\) and \(S\)
Conjdef: A semigroup \(S\) such that, equivalently

Page: 26
Definition: The relation containing the pairs of \(s,t\in S\) such that for every \(x,y\in S^1\), \(xsy\in P\iff xty\in P\).
Chapter: II
Section: 3.7
Variables: \(S\) a semigroup
\(P\subseteq S\).
Notation: \(\sim_P\)
Name: The syntactic congruence of \(P\)

Name: The congruence generated by \(R\)
Definition: The smallest congruence containing \(R\).
Page: 27
Chapter: II
Section: 3.7 (c)
Variables: \(S\) a semigroup and
\(R\subseteq S\times S\).
Index: 20
Kind: Prp
Definition2: The reflexive-transitive cloture of \(\{(xry,xsy)\mid (r,s)\in R, x,y\in S^ 1\}\).

Smaller0: \(\sim_2\) is a coarser congruence than \(\sim_1\)
Greater0: there exists a unique surjective morphism \(\pi:S/\sim_1\to S/\sim _2\) such that \(\pi\circ \pi_1=\pi_2\)
Page: 28
Chapter: II
Section: 3.7
Variables: \(S\) be a semigroup and
\(\sim_1\) and \(\sim_2\) be two congruences on \(S\).
Index: 22
Kind: Prop
Name: Second isomorphism theorem

Question: \(S/\sim\)
Answer: is isomorphic to a subsemigroup of \(\Pi_{i\in I}S/\sim_i\)
Page: 28
Chapter: II
Section: 3.7
Variables: \(S\) be a semigroup and
\((\sim_i)_{i\in I}\) and
\(\sim\) be their intersection.
Index: 23
Kind: Prop
Construction: take \(\pi_i:{S}\to{S/\sim_i}\) and [$]\pi:\defFun{S}{\prod_i S/\sim i}{s}{(\pi_i(i))_i}[/$], \(\pi(s)=\pi(s')\) iff \(s\sim_i s'\) for each \(\sim_i\), thus iff \(s\sim s'\)
\(S/\sim\) is isomorphic to the image of \(\pi\)

Name: A right action from a semigroup \(S\) to \(P\)
Definition: A function \(\cdot:P\times S\to P\) such that \((p\cdot s)\cdot t=p\cdot (st)\).
Page: 29
Chapter: II
Section: 4.1
Variables: \(S\) a semigroup and
\(P\) a set.

Definition: For all \(p\in P, ps=pt\).
Page: 29
Chapter: II
Section: 4.1
Variables: \(S\) a semigroup,
\(P\) a set
\(\cdot\) a right action.
\(s,t\in S\)
Notation: \(s\sim t\)

Definition: The transformation semigroup \((R,R)\), \(R=\{1,\dots,n\}\) such that \(rs=s\).
Page: 30
Chapter: II
Section: 4.1
Variables: \(n\in\mathbb N\).
Context: semigroup theory
Notation: \(\overline{n}\)
Index: 2
Kind: Ex

Definition: \(\beta\circ\alpha\).
Page: 30
Chapter: II
Section: 4.2
Variables: \(P\) a set and and
\(\alpha,\beta\in\mathcal T(P)\).
Notation: \(\alpha\beta\)

Smaller0: \((P,S)\) divides \((Q,T)\)
Greater0: \(S\) divides \(T\)
Page: 31
Chapter: II
Section: 4.3
Variables: \((P,S)\) and \((Q,T)\) transformation semigroup.
Index: 27
Kind: Prop

Name: The semigroup generated by \(A\)
Definition: containg the elements of the form \(a_1\dots a_n\) with \(a_i\in A\).
Page: 31
Chapter: II
Section: 5.1
Variables: \(S\) a semigroup and
\(A\subseteq S\)
Notation: \(\langle A \rangle\)
Definition2: minimal containing the A
Conjdef: The subsemigroup

Name: An \(A\)-generated semigroup
Definition: A semigroup generated by \(A\).
Page: 31
Chapter: II
Section: 5.1
Variables: \(A\) a set.

Name: Monogenic semigroup
Definition: generated by a single element.
Page: 31
Chapter: II
Section: 5.1, 6
Definition2: of the form \(\{x^i\mid 0\le i\le n\}\), and \(x^{i+p}=x^i\) for some \(i,p\in\mathbb N\)
Conjdef: A semigroup, equivalently

Smaller0: \(\phi:A^+\to S\) is surjective
Greater0: \(\phi(A)\) generates \(S\)
Page: 33
Chapter: II
Section: 5.4
Variables: \(A\) a finite alphabet
\(S\) a semigroup
\(\phi:A\to S\) a function.
Index: 28
Kind: Prop
Smaller to greater: iff

Name: The semigroup presented by \(\langle A|R\rangle\)
Definition: the quotient of \(A^+\) by the congruence generated by the elements of \(R\).
Page: 33
Chapter: II
Section: 5.5
Variables: \(A\) a finite alphabet
\(R\subseteq A^+\times A^+\).

Smaller0: \(S\) is finite
Greater0: at least one
Page: 34
Chapter: II
Section: 6
Variables: \(S\) a semigroup.
Index: 32
Kind: Cor
Prefix Greater: the number of idempotent of \(S\) is
Construction: take \(s\in S\), consider the sequence \((s^n)_n\), by Pigeonhole, there exists \(k,p\) such that \(s^k=s^{k+p}\), and thus \(s^{k'+p}=s^{k'+p}\) for each \(k'\ge k\). For \(k'>k\) a multiple of \(k\), \((x^{k'})^2=x^{2k}=x^{k+qp}=x^{k'}\)

Name: The exponent of \(S\)
Definition: the least integer \(\omega\) such that for all \(x\in S\), \(x^\omega\) is idempotent.
Page: 35
Chapter: II
Section: 6
Variables: \(S\) a semigroup.

Name: An \(m\)-coloring of a set \(E\)
Definition: A function from \(E\) to \(\{1,\dots,m\}\).
Page: 35
Chapter: II
Section: 6
Variables: \(E\) a set and \(m\in\mathbb N\).

Smaller0: \(\phi\) is a morphism from \(A\) into \(S\)
Greater0: there exists a unique semigroup morphism \(\overline\phi:A^+\to S\) such that, for each \(a\in A\), \(\overline \phi(a)=\phi(a)\)
Page: 33
Chapter: II
Section: 5.4
Variables: \(S\) be a semigroup
\(A\) an alphabet.
Index: 28
Kind: Prop
Hide middle: yes
Name: Universal property of the free semigroup \(A^+\)

Smaller0: \(\langle\{a,b\}|ab=ba\rangle\)
Greater0: \(\mathbb N^2\)
Page: 34
Chapter: II
Section: 5.5
Index: 1
Kind: Ex
Smaller to greater: is
Hide middle: yes
Prefix Smaller: the monoid presented by
Construction: Each word can be rewritten as a word of \(a^*b^*\), thus their equivalence class is determined by the number of \(a\)'s and of \(b\)'s

Smaller0: [$]m>\abs{S}[/$]
Greater0: \(S^m\)
Page: 33
Chapter: II
Section: 6
Variables: \(S\) be a finite semigroup,
\(m\in\mathbb N\).
Index: 35
Kind: Cor
Hide middle: yes
Greater1: \(SE(S)S\)
Connect Greater0: =
Construction: Let \(w=s_1\dots s_n\in S^n\).
By prop 34, there exists \(i\le n\) and \(e\) idempotent such that \(s_1\dots s_ie=s_1\dots s_i\). Thus \(w=(s_1\dots s_i)e(s_{i+1}\dots s_n)\)
Let \(w=ses'\in SE(S)S\). Then \(w=se\dots es\) with \(n-2\) copies of \(s\). Assuming \(n>2\).
If \(S=\{e\}\) then \(w=e\)
If \(S=\{e,y\}\), bruteforce

Smaller0: is finite
Greater0: \(S\) admits at least one minimal ideal
Page: 25
Chapter: II
Section: 3.5
Variables: \(S\) be a semigroup.
Index: 17
Kind: Prop
Smaller1: contains a 0
Prefix Smaller: \(S\)
Connect Smaller0: or
Construction: if \(S\) contains a 0, \(\{0\}\) is the minimal ideal.
If \(S\) is finite, the lattice of ideals is finite, thus contain minimal elements

Name: Semigroups
Page: 22
Section: 3.4
Chapter: II
Index: 3
Under: product

Name: The set of pairs \((S,T)\) with \(S\) a semigroups and \(T\) a quotient
Page: 22
Section: 3.4
Chapter: II
Index: 3
Under: product (of quotient and semigroup)

Name: Semigroups divisor
Page: 22
Section: 3.4
Chapter: II
Index: 3
Under: product (of divisor and semigroup)

Name: Pairs \((S,H)\) with \(S\) is a semigroup and \(H\) a subsemigroup
Page: 24, 228?
Section: 3.4, 1
Chapter: II, XIII
Index: 3, 4
Kind: , Prop
Under: product (of divisor and semigroup)

Name: Pairs \((S,H)\) with \(S\) is a semigroup and \(I\) an ideal
Page: 25
Section: 3.4
Chapter: II
Index: 15
Kind: Prop
Under: inverse of morphism
Condition: arbitrary
Under2: morphism
Condition2: surjective
Under3: taking a subsemigroup
Condition3: ?
Under4: Product

Name: Semigroup ideals of \(S\)
Page: 23
Section: 3.4
Chapter: II
Index: 15
Variables: \(S\) a semigroup
Kind: Prop
Under: product
Under2: intersection