\( \newcommand{\O}{\mathcal{O}} \newcommand{\P}{\mathcal{P}} \)
\( \newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACC}{\mathcal{C}} \newcommand{\ACV}{\mathcal{V}} \newcommand{\ACQ}{\mathcal{Q}} \)

Compacité

Cours M2 - MIT
Victor Poupet

Prologue

Lemme de König

Théorème
Tout arbre infini à branchement fini contient un chemin infini

Preuve : Induction à partir de la racine

  • sous-arbre en \(n\) infini
  • nombre fini de fils
  • un fils de \(n\) a un sous-arbre infini

Le processus n'est jamais bloqué

→ chemin infini

Topologie 101

Définition

\((E, \O)\) espace topologique si

  • \(E\) est un ensemble
  • \(\O \subseteq \P(E)\) vérifiant
    • \(\emptyset \in \O\)
    • \(E \in \O\)
    • \(\O\) est stable par union quelconque
    • \(\O\) est stable par intersection finie

Éléments de \(\O\) sont appelés ouverts de \(E\)

On peut définir un espace topologique en donnant une base d'ouverts

\(\O\) est alors la plus petite partie de \(\P(E)\) contenant ces ouverts de base vérifiant la définition


Exemples :

  • Les intervalles ouverts dans \(\RR\)
  • Les boules ouvertes dans un espace métrique
  • La topologie triviale \(\O=\{\emptyset, E\}\)
  • La topologie discrète \(\O=\P(E)\)

Quelques définitions

Soit \((E, \O)\) un espace topologique

Définition
\(V\subseteq E\) est un voisinage de \(x\in E\) si \(V\) est ouvert et \(x\in V\)
Définition
Une fonction \(f\) de \(E \rightarrow E\) est continue si pour tout ouvert \(V\), \(f^{−1}(V)\) est un ouvert
Définition
Une suite \((u_n) \in E^\NN\) converge vers \(x \in E\) si pour tout voisinage \(V\) de \(x\), il existe \(n_0 \in \NN\) tel que \(u_n \in V\) pour tout \(n \geq n_0\)

Compacité

Définition
Un espace topologique est compact si de tout recouvrement par des ouverts on peut extraire un recouvrement fini

Définition
Un espace topologique vérifie la propriété de Bolzano-Weierstrass si de toute suite infinie on peut extraire une sous-suite convergente
Proposition
Les définitions sont équivalentes sur les espaces admettant une base dénombrable d’ouverts

Proposition
Les définitions sont équivalentes sur les espaces métriques

Retour sur les
configurations

Distance

On munit l'espace des configurations de la distance

\[\begin{align}\ACQ^{\ZZ^d} \times \ACQ^{\ZZ^d} &\rightarrow \RR\\ \ACC_1, \ACC_2 &\mapsto \frac{1}{2^{\operatorname{min}\{\|x\|, \ACC_1(x)\neq \ACC_2(x)\}}} \end{align}\]

Deux configurations sont proches si elles coïncident sur une grande zone autour de l'origine

Interprétations

On se place dans l’espace des configurations \(\ACQ^{\ZZ^d}\)

Interprétation
Les voisinages d’une configuration \(c\) sont des ensembles de configurations qui coïncident avec \(c\) sur une zone autour de l’origine. Plus la zone est grande, plus le voisinage est fin.
Interprétation
Une suite \((c_n)\) converge vers \(c\) si pour tout \(r \in \NN\) il existe \(n_0\) tel que \(c\) et \(c_n\) coincident sur \(\llbracket −r, r\rrbracket^d\) pour tout \(n \geq n_0\)

Preuve de compacité

Théorème
L’espace des configurations \(\ACQ^{\ZZ^d}\) est compact

Preuve : On montre que de toute suite infinie on peut extraire une sous-suite convergente

  • Soit \((c_n)\) une suite de configurations
  • Pour tout \(r\) il existe un remplissage de \(\llbracket −r, r\rrbracket^d\) qui coïncide avec une infinité de \(c_n\)
  • On obtient une suite extraite \((c_{\phi(n)})\) qui converge vers une configuration \(c\)

Exemples

Sous-shifts

Définition
Un sous-shift est un ensemble de configurations ne contenant pas un ensemble de motifs finis (appelés motifs interdits)
Définition
Un sous-shift qui peut être caractérisé par un ensemble fini de motifs interdits est dit de type fini
Proposition
S’il existe des carrés arbitrairement grands ne contenant pas de motifs interdits, alors il existe une configuration n’en contenant aucun

Preuve : Par compacité

  • Soit \((c_n)\) une suite de configurations telle que \(c_r\) n’a pas de motif interdit sur \(\llbracket −r, r\rrbracket^2\)
  • Il existe une sous-suite convergente
  • La limite \(c\) de la sous-suite ne contient aucun motif interdit

Surjectivité des AC

Proposition
Si tout motif fini apparaît dans l’image d’une configuration par un AC \(\ACA\), alors \(\ACA\) est surjectif.

Preuve : Par compacité

Attention à la convergence

Définition
Un AC est nilpotent s’il existe un état \(q_0 \in \ACQ\) tel que de toute configuration \(c \in \ACQ^{\ZZ^d}\) on arrive dans la configuration uniforme ne contenant que l’état \(q_0\)
Proposition
Si un AC est nilpotent, il existe un temps \(t\) tel que pour toute configuration \(c ∈ \ACQ^{\ZZ^d}\), \(\ACA^t(c) = \overline{q_0}\)

Preuve : Par compacité sur la contraposée ?

  • On considère une suite \((c_n)\) telle que \(\ACA^n(c_n)(0) \neq q_0\)
  • On extrait une sous-suite convergente vers \(c\)
  • On ne sait pas grand chose sur \(c\)...

Preuve : Directe

  • Soit \(c\) une configuration univers (contenant tout motif fini)
  • Il existe un temps \(t\) tel que \(\ACA^t(c) = {\overline{q_0}}\)

Caractérisation topologique

Théorème (G. A. Hedlund)
Les automates cellulaires de dimension \(d\) et d’états \(\ACQ\) sont exactement les fonctions continues de \(\ACQ^{\ZZ^d} \rightarrow \ACQ^{\ZZ^d}\) qui commutent avec le shift

✎ Exercice : Prouvez le théorème

Un sens évident, l’autre par compacité en montrant que toute fonction continue est uniformément continue (cf. Théorème de Heine)


Corollaire
Si un automate cellulaire est bijectif, son inverse est également un automate cellulaire

Remarque : Le théorème ne donne aucune information sur le voisinage de l’inverse