Cours 1: Rappels

Notations et rappels

1. Cardinaux

  • $ω$ est souvent utilisé pour dénoter $\aleph_0$ (ex: $ω$-stable)

  • Cardinaux: $κ, λ ≥\aleph_0 \qquad κ > \aleph_0$

  • $\vert A\vert$ cardinalité de $A$

  • $A$ dénombrable ⟺ $\vert A \vert = \aleph_0$

2. Fonctions, uplets, ensembles

Soit $A$ un ensemble.

  • $(I, <)$ sera toujours un ensemble totalement ordonné (fini ou infini)

  • $\overline{a}$: uplets finis ou infinis à valeurs dans $A$

    • si $(I, <)$, $\overline{a} ∈ A^{\vert I \vert}$ siginifie $\overline{a} = (a_i)_{i ∈ I}$, $a_i ∈ A$

  • Si $\overline{a}, \overline{b} ∈ A^{\vert I \vert}$, $\overline{a} \overline{b}$ est un $(\vert I \vert + \vert J \vert)$-uplet

  • Si $f: A ⟶ B$, $\overline{a} ∈ A^I$, \(f(\overline{a}) ≝ (f(a_i))_{i∈I}\)

  • Suites binaires:

    • $2^n$ = ensemble des suites binaire de longueur $n$
    • $2^{≤n}$ = ensemble des suites binaire de longueur $≤n$
    • $2^{<ω}$ = ensemble des suites binaire finies
    • $2^{ω}$ = ensemble des suites binaire infinies

  • $σ ∈ 2^{< ω}$, $\vert σ \vert$ = longueur de la suite

  • $σ ∈ 2^{ω}$, $σ_{≤n}$ la suite tronquée au niveau $n$: $(σ_1, ⋯, σ_n)$

3. Langages, structures, formules

Les langages $ℒ$ ont toujours le symbole d’égalité $=$

  • “Il existe exactement $n$ uplets $\overline{x}$ tq $φ(\text{x})$”: \(∃^{=n} \overline{x}; φ(\overline{x})\)

  • \(F(ℒ) = \bigcup_n F_n(ℒ)\) où $F_n(ℒ)$ est la colleciton de toutes les $ℒ$-formules avec $≤n$ variables libres

  • $E(ℒ)$ = collection des $ℒ$-énoncés

  • \[𝔐 = ⟨M, \underbrace{⋯}_{interprétation des symboles du langage}⟩\]

  • $A ⊆ M$, $ℒ_A = ℒ ∪ \lbrace c_a \mid a ∈ A\rbrace$

  • $𝔐, 𝔑$ $ℒ$-structures: \(𝔐 ≡ 𝔑 \text{ élémentairement équivalentes, i.e.} \\∀φ∈ E(ℒ), 𝔐 ⊨ φ ⟺ 𝔑 ⊨ φ\)

  • $𝔄 ⊆ 𝔐$: $𝔄$ est une sous-structure de $𝔐$ ssi

    • $A ⊆ M$
    • et l’interprétation des symboles de $M$ est la même

  • $A⊆M$, $⟨A⟩_𝔐$ la sous-structure engendrée par $A$ dans $𝔐$ \(\left\lbrace t^𝔐(\overline{a}) \mid t \text{ terme}, \overline{a} ∈ A^n\right\rbrace\)

  • $𝔄 ≤ 𝔐$, $𝔄$ une sous-structure élémentaire de $𝔐$: \(∀φ ∈ E(ℒ_A), 𝔄_A ⊨ φ ⟺ 𝔐_A ⊨ φ\)

Test de Tarski-Vaught

$𝔐$ une $ℒ$-structure, $A⊆M$, alors $A$ est le domaine d’une sous-structure élémentaire $𝔄 ≤ 𝔐$ ssi

\[∀ φ(x) ∈ F_2(ℒ_A), 𝔐_A ⊨ ∃x; φ(x) ⟺ ∃a∈A; 𝔐_A ⊨ φ(a)\]

Chaînes élémentaires

$(I, <)$, $\lbrace 𝔐_i\rbrace_{i∈I}$ chaîne élémentaire si \(𝔐_i ≤ 𝔐_j \quad ∀i, j \\ ⟹ \bigcup_{i∈I} 𝔐_i ≥ 𝔐_j \quad ∀j ∈ I\)

Ensembles définissables

  • $φ(\overline{x}, \overline{y})$
  • $𝔐$ une $ℒ$-structure
  • $B⊆M$
  • $\overline{b} ∈ B^m$

L’ensemble défini par $φ(\overline{a}, \overline{b})$:

\[φ(𝔐, \overline{b}) ≝ \left\lbrace \overline{a} ∈ M^n \mid 𝔐 ⊨ φ(\overline{a}, \overline{b})\right\rbrace\]

Théories et modèles

$ℒ$-théorie:

ensemble de $ℒ$-énoncés

NB: nos théories seront toujours consistantes

$T$ complète:
\[∀φ∈E(ℒ), \quad T ⊨ φ \text{ ou } T ⊨ ¬ φ\]
$T$ dénombrable:

$\vert ℒ\vert ≤ \aleph_0$

$𝔐$ une $ℒ$-structure,

$Th(𝔐)$:

théorie complète de $𝔐$

Si $φ, ψ ∈ F_n(ℒ)$,

$φ$ est équivalente à $ψ$ modulo $T$ (noté $φ \sim_T ψ$):

ssi $T ⊨ ∀\overline{x} \left(φ(\overline{x}) ⟺ ψ(\overline{x})\right)$

NB: Nos théories complètes n’auront pas de modèles finis, car s’il existe un modèle de card $n$ et la théorie est complète, alors tous ses modèles sont de card $n$, puisque l’énoncé “il y a exactement $n$ éléments” est dans la théorie (par complétude).

Compacité et ses conséquences

Th de Compacité:

Toute théorie finiment satisfaisable a un modèle.

Théorèmes de Löwenheim-Skolem

Th de Löwenheim-Skolem:

Soit $T$ une $ℒ$-théorie avec un modèle fini. Alors pour tout $κ ≥ \max \lbrace \vert ℒ \vert, \aleph_0 \rbrace$, $T$ a un modèle de cardinalité $κ$

Th de Löwenheim-Skolem descendant:

Pour tout $\vert M \vert ≥ κ ≥ \max \lbrace \vert ℒ \vert, \aleph_0, A \rbrace$, \(∃𝔑 ≤ 𝔐; \vert N \vert = κ \text{ et } A ⊆ N\)

Th de Löwenheim-Skolem ascendant:

Si $𝔐$ est infine, alors pour tout $κ ≥ \max \lbrace \vert ℒ \vert, \aleph_0 \rbrace$, \(∃𝔑 ≥ 𝔐; \vert N \vert = κ\)

Corollaire:

$T$ complète, dénombrable, sans modèles finis.

$∀ κ ≥ \aleph_0$, $T$ a un modèle de card. $κ$

Morphismes

$𝔐, 𝔑$ des $ℒ$-structures.

Notations:

Plongement (injectif):
\[f: 𝔐 \hookrightarrow 𝔑\]
Isomorphisme (= plongement surjectif):
\[f: 𝔐 \overset{\sim}{⟶} 𝔑\]
$𝔐$ et $𝔑$ isomorphes:
\[𝔐 ≃ 𝔑\]
Plongement élémentaire:
\[f: 𝔐 \overset{\sim}{\hookrightarrow} 𝔑\]
\[∀φ∈ℱ_n(ℒ), ∀\overline{a}∈M^n, M ⊨ φ(\overline{a}) ⟺ N ⊨ φ(f(\overline{a}))\]

Applications partielles

  • $A ⊆ M$

  • $f: A ⟶ N$

    • tq $∀φ∈ℱ_n(ℒ) \text{ sans quantificateurs}, ∀\overline{a}∈M^n$, \(M ⊨ φ(\overline{a}) ⟺ N ⊨ φ(f(\overline{a}))\)
Application partielle notée:

$𝔐 \supset A ⟶ 𝔑$

Application partielle élémetaire notée:

$𝔐 \supset A \overset{\sim}{⟶} 𝔑$

Si $𝔄 ⊆ 𝔐$,

  • isomorphisme partiel (ip)
  • isomorphisme partiel élémentaire (ipe)

NB (Exercices):

  1. tout application partielle est injective ($x=y$)

  2. Application partielle élémentaire $𝔐 \supset A \overset{\sim}{⟶} 𝔑$ s’étend de manière unique à \(𝔐 \supset ⟨A⟩_𝔐 \overset{(\sim)}{⟶} 𝔑\)

  3. Tout isomorphisme partiel (ip) $𝔐 \supset 𝔄 \overset{\sim}{⟶} 𝔑$ induit un isomorphisme des sous-structures $𝔄 ⊆ 𝔐$ et $f(𝔄) ⊆ 𝔑$

Va-et-vient

Propriété du va-et-vient pour une famille $ℑ = ℑ(𝔐, 𝔑)$ d’ip entre $𝔐$ et $𝔑$:

ssi:

  • $∀f ∈ ℑ, ∀ a ∈ M, ∃ g ∈ ℑ; g \text{ s’étend à } f \text{ et } a∈dom(g)$
  • $∀f ∈ ℑ, ∀ b ∈ M, ∃ g ∈ ℑ; g \text{ s’étend à } f \text{ et } b∈Im(g)$

S’il existe une telle famille $ℑ$ non vide avec la propriété du va-et-vient, alors on dit que $𝔐$ et $𝔑$ sont partiellement isomorphes:

\[𝔐 ≃^p_ℑ 𝔑\]

Th

  1. Si $𝔐$ et $𝔑$ sont partiellement isomorphes, alors tout $f ∈ ℑ$ est ipe. En particulier, $𝔐 ≡ 𝔑$

  2. Si $𝔐, 𝔑$ sont dénombrables et $𝔐 ≃_ℑ 𝔑$, alors $𝔐 ≃ 𝔑$

Elimination des quantificateurs et modèle-complétude

$T$ a l’élimination des qunatificateurs EQ:

si toute formule est équivalente $\mod T$ à une formule sans quantificateurs

Critère d’EQ

$T$ a l’EQ ssi

\[∀ 𝔐, 𝔑 ⊨ T \text{ qui ont une sous-structure commune } 𝔄, \text{ on a:}\\ 𝔐_A ≃ 𝔑_A\]
$T$ est modèle-complète:

si $∀𝔐 ⊆ 𝔑 ⊨ T$, on a $𝔐 ≤ 𝔑$

Test de Robinson

sont équivalents:

  1. $T$ est modèle-complète
  2. $∀𝔐 ⊆ 𝔑 ⊨ T, ∀φ ∈ E(ℒ_M)$ énoncé existentiel (quantificateurs existentiels puis formule sans quantificateurs), \(𝔑_M ⊨ φ ⟺ 𝔐_M ⊨ φ\)
  3. $∀φ ∈ ℱ_n(ℒ), ∃ θ ∈ ℱ_n(ℒ) \text{ exitentielle tq } φ \sim_T θ$

Donc EQ ⟹ modèle-complétude

Exercices/Remarques:

  1. Si $T$ a l’EQ, et s’il existe une “structure première” (i.e. une structure non vide qui se plonge dans tous les modèles de $T$), alors $T$ est complète.

  2. Si $T$ est modèle-complète et s’il existe un modèle premier (i.e. une structure non vide qui se plonge élémentairement dans tous les modèles de $T$), alors $T$ est complète.

Types

$T$ une théorie complète.

Un $n$-type partiel de $T$:

Un sous-ensemble de formules $p ⊆ ℱ_n(ℒ)$ finiment satisfaisable (pour toute conjonction finie, il existe un modèle la satisfiant) dans des modèles de $T$

Un type complet de $T$:

un $n$-type partiel $p$ tq $φ ∈ ℱ_n(ℒ)$, soit $φ ∈ p$, soit $¬φ ∈ p$

Dans ce cours: TYPE ≝ TYPE COMPLET

$S_n(T)$:

collection des $n$-types de $T$

$n$-type de $Th(𝔐)$:

un $n$-type d’une structure $𝔐$

\[S_n^𝔐 ≝ S_n(Th(𝔐))\]

$T$ complète, $𝔐 ⊨ T$, \(S_n^𝔐 = S_n(T)\)

Si $A⊆M$ $n$-type de $𝔐$ sur $A$

\[S_n^𝔐(A) = S_n(Th(𝔐_A))\] \[S_n^𝔐 = S_n(∅)\]

$\overline{a}∈M^n$, \(tp^𝔐(\overline{a}) ≝ \lbrace φ ∈ ℱ_n(ℒ) \mid 𝔐 ⊨ φ(\overline{a}) \rbrace\)

\[tp^𝔐 ∈ S_n^𝔐\]

$A⊆M$, \(tp^𝔐(\overline{a}/A) ≝ \lbrace φ ∈ ℱ_n(ℒ_A) \mid 𝔐_A ⊨ φ(\overline{a}) \rbrace ∈ S_n^𝔐(A)\)

Un type $p ∈ S_n(T)$ est réalisé dans un modèle $𝔐 ⊨ T$ ssi il existe $\overline{a} ∈ M^n$ tq \(p = tp(\overline{a})\)

Si $p$ n’est pas réalisé dans $𝔐$, $p$ est omis dans $𝔐$

Ex:

$⟨ℝ, <⟩$:

  • Omis dans $ℝ$: \(\lbrace 0 < x < q \mid q ∈ ℚ^{>0} \rbrace\)

  • Réalisé dans $ℝ$: $r∈ ℝ\backslash ℚ$, \(\lbrace q_1 < x < q_2 \mid q_1 < r < q_2 \rbrace\)

Exercices/Remarques:

$T$ complète, $p ⊆ ℱ_n(ℒ)$; sont équivalents:

  • $p ∈ S_n(T)$
  • $∃ 𝔐 ⊨ T$ tq $p ∈ S_n^𝔐$
  • $∀ 𝔐 ⊨ T, p ∈ S_n^𝔐$
  • $∃ 𝔐 ⊨ T, ∃ \overline{a} ∈ M^n$ tq $p = tp^𝔐(\overline{a})$
  • $p$ est maximal (par inclusion) dans la famille des $n$-types partiels

NB:

  • $p, q ∈ S_n(T), p ⊆ q ⟹ p=q$

  • $φ ∈ p, ψ∈ ℱ_n(ℒ)$, \(T ⊨ ∀\overline{x}, (φ(\overline{x}) ⟶ ψ(\overline{x})) ⟹ ψ ∈ p\)

(complétude)

  • $φ_1 ∨ ⋯ ∨ φ_k ∈ p ⟺ ∃i; φ_i ∈ p$
  • $φ_1 ∧ ⋯ ∧ φ_k ∈ p ⟺ ∀i; φ_i ∈ p$

Remarques:

  • \[p∈ S_n^𝔐(A) ⟺ ∃ 𝔑 ≥ 𝔐, ∃ \overline{a} ∈ N^n, p = tp^n(\overline{a}/A)\]
  • \[p = tp^𝔐(\overline{b}/A) (\overline{b} ∈ M^n) ⟹ p = tp^𝔑(\overline{b}/A) \quad ∀𝔑 ≥ 𝔐\]

Exercice:

Soit $S⊆ \bigcup_{n∈ℕ} S_n^𝔐(A)$. Alors $∃ 𝔑 ≥ 𝔐$ qui réalise tous les types de $S$ et \(\vert N \vert ≤ \vert M \vert+ \vert ℒ \vert + \vert S \vert\)

(argument de chaînes élémentaires)

Type d’un uplet infini $\overline{a} ≝ (a_i)_{i∈I}$ ($(I, <)$ et $a_i ∈ M$):
\[tp^𝔐(\overline{a}) = \lbrace φ(x_{i_1}, ⋯, x_{i_n}) \mid n∈ ℕ, i_j ∈ I, \text{ tq } 𝔐 ⊨ φ(a_{i_1}, ⋯, a_{i_n})\rbrace\]

Espaces de Stone

Notation: $φ∈ ℱ_n(ℒ)$.

Ensemble des types qui contiennent la formule $φ$:
\[[φ] ⊆ S_n(T)\]

Remarques:

  1. $[φ] = [ψ] ⟺ φ \sim_T ψ$

  2. La famille $\lbrace [φ] \mid φ ∈ ℱ_n(ℒ)\rbrace$ est stable par les opérations booléennes

    • $[φ] ∩ [ψ] = [φ ∧ ψ]$
    • $[φ] ∪ [ψ] = [φ ∨ ψ]$
    • $[¬φ] = S_n(T)\backslash [φ]$
    • $S_n(T) = [x=x]$
    • $∅ = [x ≠ x]$

Topologie de Stone

\(\lbrace [φ] \mid φ ∈ ℱ_n(ℒ)\rbrace\) forme une base pour une topologie sur $S_n(T)$

  • les $[φ]$ sont les (seuls) ouverts-fermés

  • $T_2$ (i.e., any two points have disjoint neighborhoods), compacte

  • Fermés, $Σ ⊆ ℱ_n(ℒ)$:
\[[Σ] = \lbrace p∈S_n(T) \mid ∀φ∈ Σ, φ ∈p \rbrace\]
Formule complète $φ$:

ssi $[φ]$ est un singleton

Type isolé $p∈S_n(T)$:

si l’une des conditions suivantes équivalentes est réalisée:

  • $p$ est un point isolé de $S_n(T)$ (i.e. $\lbrace p \rbrace$ est ouvert)

  • il existe une formule $φ$ qui isole $p$: \(T ⊨ ∀\overline{x}, (φ(\overline{x})⟶ ψ(\overline{x})) \qquad ψ ∈ p\)

  • il existe une formule $φ$ tq $[φ] = p$
  • il existe une formule $φ$ complète tq $φ ∈ p$

Types réalisés et types omis

Remarque:

Si un type $p ∈ S_n(T)$ est réalisé dans un modèle $𝔐 ⊨ T$, alors $p$ est aussi réalisé dans toute $𝔑 ≥ 𝔐$. Donc si $p$ est omis dans $𝔐 ⊨ T$ alors $p$ est omis dans toute $𝔑 ≤ 𝔐$.

Proposition:

Si $T$ est complète, alors les types isolés sont réalisés dans tous les modèles de $T$

Preuve: $p$ isolé par $φ ∈ F_n(ℒ)$, \(T ⊨ ∃ \overline{x}, φ(\overline{x})\)

NB: pas intéressants, car la théorie a tout à dire dans ce cas (alors qu’elle n’a rien à dire dans le cas général).

Th d’omission des types:

$T$ dénombrable, $S ⊆ \bigcup S_n(T)$ un ensemble dénombrable de types non isolés.

Alors il existe $𝔐 ⊨ T$, $\vert M \vert = \aleph_0$ tq $𝔐$ omet tous les types de $S$.

$\vert F(ℒ) \vert = \vert ℒ \vert + \aleph_0$

$\vert S_n(T) \vert ≤ 2^{\vert ℒ \vert+\aleph_0}$

En particulier,

  • $𝔐 ⊨ T, A ⊆ M$, \(\vert S_n^𝔐(A) \vert ≤ 2^{\vert ℒ \vert+\aleph_0 + \vert A \vert}\)

  • $\vert ℒ \vert ≤ \aleph_0 ≤ \vert A \vert$, \(\vert S_n^𝔐(A) \vert ≤ 2^{\vert A \vert}\)

  • Dense Linear Order: $DLO = Th(ℚ_{<})$

    • admet EQ
    • est $\aleph_0$-catégorique

    • n’est pas $2^{\aleph_0}$-catégorique:

      • $ℝ_< = ⟨ℝ, <⟩$

      • $⟨ℝ \sqcup ℚ, <⟩ ≝ 𝔐$

        • $ℝ_< \not ≃ 𝔐$, car si $f: 𝔐 ⟶ ℝ_<, q ⟼ r$, alors $\lbrace x \mid x>q \rbrace$ est une image non dénombrable
  • Algebraically Closed Fields of Char. 0: $ACF_0 = Th(\overline{ℂ})$
  • Real Closed Fields: $RCF = Th(\overline{ℝ})$

Exercice (Marker):

Types de DLO:

  • $S_1(T) = \lbrace p_0 \rbrace$ ($x=x$)

    • $∀a, b∈ M, tp(a) = tp(b)$
  • $S_2(T) \qquad x=y, x<y, x>y$

  • $S_n^𝔐(A) \qquad A = \lbrace a_1, ⋯, a_m \rbrace, x=a_1, a_1 < x < a_2$

    • $\vert A \vert <∞ ⟹ \vert S_n^𝔐(A) \vert < ∞$

  • $\vert A \vert ≥ \aleph_0$,

    • $S_1^{ℚ_<}(ℚ) \qquad (x=q), q∈ℚ$

      • $p_{+∞} = \lbrace x>q \mid q ∈ ℚ \rbrace$
      • $p_{-∞} = \lbrace x<q \mid q ∈ ℚ \rbrace$
      • Pour $r ∈ ℝ\backslash ℚ$, $p_{r} = \lbrace q_1 < x <q_2 \mid q_1 < r < q_2 ∈ ℚ \rbrace$ ⟶ $\vert S_1^{ℚ_<}(ℚ) \vert = 2^{\aleph_0}$
      • Pour $q_0 ∈ ℚ$, $p_{q_0^+} = \lbrace q_0 < x <q’ \mid q_0 < q’ ∈ ℚ \rbrace$
      • Pour $q_0 ∈ ℚ$, $p_{q_0^-} = \lbrace q’ < x <q_0 \mid q_0 > q’ ∈ ℚ \rbrace$

Leave a comment