Title: Theory / Unimportant / CS / Fundamental / Automata / Finite / Pin{ / C The profinite world / 10 Profinite words;
Tags: fromMath mathToDef mathToSee examplesSwitchExample1 hasSeenConjDef counterExample mid1516974248815 property toUnary

Name: \(\phi\) separates \(u\) and \(v\)
Definition: \(\phi(u)\ne\phi(v)\).
Page: 180
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet,
\(u,v\in A^*\),
\(M\) a monoid
\(\phi:A^*\to M\).

Question: \(u\) and \(v\) can be separated by
Answer: the finite monoid which recognizes \(\{u\}\)
Page: 181
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet,
\(u,v\in A^*\) distinct.
Index: 2
Kind: Prop

Definition: The cardinality of the minimal monoid \(M\) which separates \(u\) and \(v\), or \(\infty\) otherwise.
Page: 181
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet,
\(u,v\in A^*\).
Notation: \(r(u,v)\)

Definition: \(2^{-r(u,v)}\).
Page: 181
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet, \(u,v\in A^*\).
Notation: \(d(u,v)\)

Smaller0: \(d(uw,vw)\)
Greater0: \(d(u,v)\)
Page: 181
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet
\(d:A^*\times A^*:\mathbb R^{>0}\)
Index: 3 (3)
Kind: Prop
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Page: 181
Set: \(A^*\)
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet
Kind: Prop
Base: singletons
Metric: \(d(u,v)=2^{-r(u,v)}\) with \(r(u,v)\) the cardinality of the least monoid separating \(u\) and \(v\)
Index: 3
Totally bounded: Yes

Question: The concatenation function on \(({A^*},d)\) is
Answer: uniformly continuous.
Page: 183
Chapter: X
Section: 2.2
Variables: \(A\) a finite alphabet.
Index: 9
Kind: Prop

Question: Topologically, \(\phi\) is
Answer: uniformly continuous.
Page: 184
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet,
\(M\) a discrete monoid and
\(\phi:A^*\to M\) a morphism.
Index: 10
Kind: Prop
Assuming: \(M\) finite

Question: The number of extension to a uniformly contiuous morphism \(\widehat\phi\) from \(\widehat{A^*}\) to \(M\) is
Answer: exactly one.
Page: 184
Chapter: X
Section: 2.2
Variables: \(A\) a finite alphabet
\(M\) a discrete monoid
\(\phi:A^*\to M\) a morphism.
Index: 10
Kind: Prop
Assuming: \(M\) finite

Name: Noncontinuous morphism from \(\widehat{A^*}\)
Page: 181
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet.
Example: \(\widehat \phi:\widehat{A^*}\to (\{0,1\},\times)\) which sends finite word to \(1\) and everything else to 0.

Question: The number of extension to a continuous monoid morphism from \(\widehat{A^*}\to M\) is
Answer: exactly one
Page: 185
Chapter: X
Section: 2.3
Variables: \(A\) a finite alphabet,
\(M\) a discrete finite monoid
\(\phi:A\to M\) a morphism
Index: 11
Kind: Prop

Smaller0: surjective
Greater0: \(\phi(A)\) generates \(M\)
Page: 185
Chapter: X
Section: 2.3
Variables: \(A\) a finite alphabet
\(M\) a discrete finite monoid
\(\phi:A\to M\) a morphism.
Index: 11
Kind: Prop
Smaller to greater: iff
Prefix Smaller: \(\widehat\phi:\widehat{A^*}\to M\) is

Page: 184, 185
Name: The profinite topology on \(\widehat {A^*}\)
Chapter: X
Section: 2.1, 2.3
Variables: Let \(A\) a finite alphabet.
Metric: Distance generated by the topology it completes
Definition: least topology which makes continuous every morphism from \(A^*\) onto a discrete monoid
Completion of: [$](u,v)\mapsto 2^{\min\{\abs{M}\mid M\text{ finite monoid separating $u$ and $v$.}\}}[/$] on \(A^*\)

Name: Profinite word
Definition: An element of the profinite topology.
Page: 182
Chapter: X
Section: 2.1
Variables: \(A\) a finite alphabet.

Definition: \(\lim_{n\to\infty}x^{n!}\).
Page: 186
Chapter: X
Section: 2.4
Variables: \(A\) a finite alphabet and \(x\in A^*\).
Notation: \(x^\omega\)
Index: 13
Kind: Prop
Typ: profinite word
Construction: for each \(M\) finite discrete monoid, \(\phi:A^*\to M\).
There is \(r\) such that \(\phi(x^{r})\) is idempotent \(e\), it follows that for each \(n\ge r\), \(\phi(x^{n!})=e^{(r+1)\dots n}=e\). Thus it is a Cauchy sequence converging to an idempotent.

Name: An idempotent element of \(\widehat{A^*}\)
Page: 184
Chapter: X
Section: 2.3
Variables: \(A\) a finite alphabet and \(x\in A^*\).
Index: 10
Kind: Prop
Example: \(x^\omega\)

Smaller0: \(\widehat\phi(x^\omega)\)
Greater0: the unique idempotent of \(\langle\phi(x)\rangle\)
Page: 186
Chapter: X
Section: 2.4
Variables: \(A\) a finite alphabet,
\(x\in A^*\),
\(M\) a finite monoid
\(\phi:A^*\to M\).
Smaller to greater: is equal to

Question: \((x^\omega)^\omega=\)
Answer: \(x^\omega\).
Page: 183
Chapter: X
Section: 2.3
Variables: \(A\) a finite alphabet and \(x\in A^*\).

Definition: \(\lim_{n\to\infty}x^{n!+1}\)
Page: 186
Chapter: X
Section: 2.4
Variables: \(A\) a finite alphabet
\(x\in A^*\).
Notation: \(x^{\omega+1}\)

Definition: \(\lim_{n\to\infty}x^{n!-1}\)
Page: 186
Chapter: X
Section: 2.4
Variables: \(A\) a finite alphabet and \(x\in A^*\).
Notation: \(x^{\omega-1}\)
Definition2: the inverse of \(x^{\omega+1}\) in the group generated by \(x\)

Question: Let \(A\) a finite alphabet and \(x\in A^*\).
\(xx^{\omega-1}=\)
Answer: \(x^\omega\)
Page: 183
Chapter: X
Section: 2.3

Question: Let \(A\) a finite alphabet and \(x\in A^*\).
\(xx^{\omega}=\)
Answer: \(x^{\omega+1} \)
Page: 182
Chapter: X
Section: 2.3

Smaller0: \(P\) is clopen
Greater0: \(P\) is recognisable and its syntactic morphism is a continuous map from \(\widehat{A^*}\) onto the discrete finite space \(M\)
Page: 187
Chapter: X
Section: 3
Variables: \(A\) an alphabet,
\(P\subseteq\widehat{A^*}\) and
\(M\) the syntactic monoid of \(P\).
Index: 14
Kind: Prop
Smaller to greater: iff
Smallest: the syntactic congruence of \(P\) is a clopen subset of \(\widehat{A^*}\times \widehat{A^*}\)

Name: A recognisable language
Definition: recognisable in \(\widehat{A^*}\)
Page: 182, 188,167
Chapter: X, X, IX
Section: 2, 1,3
Variables: \(A\) an alphabet
Index: 5, 15, 5
Kind: Prop, Prop, Theo
Definition2: \(\overline L\) is clopen in \(\widehat{A^*}\)
Conjdef: A language over \(A\), equivalently
Definition3: definable by a \(\mathrm{MSO}[S]\)
Definition4: definable by a \(\mathrm{MSO}[<]\)
Definition5: definable by a \(\exists\mathrm{MSO}[<]\) formula
Definition6: of the form \(K\cap A^*\) for some clopen \(K\subseteq\widehat{A^*}\)
Definition7: a finite union of open ball of \((A^*,d)\)

Smaller0: \(u\in\overline L\)
Greater0: \(\widehat\eta(u)\in \eta(L)\) where \(\eta\) is the syntactic morphism of \(L\)
Page: 188
Chapter: X
Section: 1
Variables: \(A\) an alphabet
\(u\in \widehat{A^*}\)
\(L\subseteq A^*\).
Index: 16
Kind: Prop
Smaller to greater: iff
Assuming: \(L\) is recognisable
Smallest: \(\widehat\phi(u)\in \phi(L)\) for some morphisms \(\phi\) from \(A^*\) onto a finite monoid
Greatest: \(\widehat\phi(u)\in \phi(L)\) for all morphisms \(\phi\) from \(A^*\) onto a finite monoid

Smaller0: \(L\) is recognisable
Greater0: \(\overline L\)
Page: 189
Chapter: X
Section: 1
Variables: \(A\) an alphabet,
\(L\subseteq A^*\) with syntactic morphism \(\eta\)
Index: 17
Kind: Cor
Greater1: \(\widehat\eta^{-1}(\eta(L))\)
Connect Greater0: =

Definition: Boolean algebra of all clopen sets of \(\widehat {A^*}\)
Page: 189
Chapter: X
Section: 1
Variables: \(A\) an alphabet
Notation: \(\mathrm{Clopen}(\widehat{A^*})\)

Q: [...] is [type].
A: [$]\defFun{\mathcal P(A^*)}{\mathcal P(\widehat{A^*})}{L}{\overline L}[/$]; an isomorphism from \(Rec(A^*)\) to \(Clopen(\widehat{A^*})\)
Page: 189
Chapter: X
Section: 3
Variables: \(A\) an alphabet
Index: 19
Kind: Theo

Q: [...] is [...].
A: [$]\defFun{\mathcal P(\widehat{A^*})}{\mathcal P(A^*)}{K}{K\cap A^*}[/$]; an isomorphism from Clopen\((\widehat{A^*})\) to Rec\((A^*)\)
Page: 189
Chapter: X
Section: 3
Variables: \(A\) an alphabet
Index: 18
Kind: Theo
Extra: what kind of iso ? from topologie to monoid...

In {\(\text{Rec}(A^*)\), the closure operator:
-commutes with boolean operations,
-commutes with left/right quotients,
-commutes with inverse of morphism.
Page: 189-190
Chapter: X
Section: 1
Variables: \(A\) an alphabet
Index: 19,20,21
Kind: Theo, Prop

Page: 182, 134
Name: Profinite topology
Chapter: X
Section: 2.1, 2.2
Variables: \(A\) a finite alphabet
Kind: Theo, Prop
Index: 5, 9
Notation: \(\hat A^*\)
Definition: The least topology which makes continuous every morphism from \(A^*\) onto a finite discrete monoid
Compact: yes

Smaller0: \(\phi\) is uniformly continuous
Greater0: \(\phi^{-1}\) preserve recognisable languages
Page: 182
Chapter: X
Section: 2.1
Variables: \(A,B\) alphabets
\(\phi:A^*\to B^*\)
Smaller to greater: iff

Definition: the only continous monoid morphism \(\widehat{A^*}\to M\) extending \(\phi\)
Page: 185
Section: 2.3
Chapter: X
Variables: \(A\) alphabet
\(M\) a finite monoid
\(\phi:A^*\to M\) morphism
Notation: \(\hat\phi\)
Morphism: monoid morphism
Continuous: uniformly continuous

Name: An ultrametric
Definition: A metric \(d\) such that \(d(x,y)\le\max(d(x,z), d(z,y))\) for each \(x,y,z\)
Page: 190
Chapter: X
Section: 4