Chapitre 3 Flashcards
Expression de la formule “α est un ordinal” par une formule ensembliste (schéma de preuve)
La définition d’un ordinal (transitivité et restriction de ∈ bon ordre) est exprimable par une formule ensembliste :
∀ x ∈ α, (x ⊆ α), et
∀ x ∈ α, (x !∈ x), et
∀ x, y, z ∈ α, ((x ∈ y et y ∈ z ) ⇒ x ∈ z), et
∀ t ⊆ α, (t != ∅ ⇒ ∃ x ∈ t, ∀ y ∈ t, (y = x ou x ∈ y))
où l’utilisation de ∅ et ⊆ sont des simplifications qui pourraient être évitées
Qu’est-ce qu’Ord(α) ?
La formule ensembliste correspondant à “α est un ordinal”
Lemme de l’existence des ordinaux dans le système Zermelo fini (énoncé)
L’ordinal 0 existe, et pour chaque ordinal α, l’ordinal S(α) existe
Lemme de l’existence des ordinaux dans le système Zermelo fini (schéma de preuve)
- L’ensemble vide s’obtient par séparation par ∅ = {x ∈ a | x!= x} à partir de a un ensemble quelconque
- S(α) s’obtient en utilisant les axiomes de la paire et de la réunion qui garantissent la bonne définition de ∪, donc S(α) = α ∪ {α}
Induction ordinale dans le système Zfini
Si ϕ est une formule ensembliste et v est un vecteur d’arguments, et que pour tout ordinal α, si ϕ(β, v) est vraie pour tout β < α alors ϕ(α, v) est vraie, alors ϕ(α, v) est vraie pour tout ordinal α
Quel problème pose le système Zfini vis-à-vis des ordinaux ?
Pour garantir l’existence de l’ordinal ω, il manque un axiome
Qu’est-ce qu’un ensemble récurrent ?
Un ensemble est dit récurrent s’il contient ∅ et est clos par l’application S : x → x ∪ {x}
Quel est l’axiome d’infini ?
∃ a, (∅ ∈ a et ∀ x ∈ a, (S(x) ∈ a)), c’est-à-dire qu’il existe au moins un ensemble récurrent
(où l’utilisation de ∅ et S sont de simplifications qui pourraient être évitées)
Quels axiomes forment le système Zermelo ?
Les axiomes du système Zermelo fini auxquels on ajoute l’axiome d’infini :
- L’axiome d’extensionnalité
- L’axiome de la paire
- L’axiome de l’union
- L’axiome des parties
- L’axiome de séparation en Φ pour chaque formule du premier ordre Φ
- L’axiome d’infini
Il existe un plus petit ordinal récurrent (schéma de preuve)
- Prendre les ordinaux α d’un ensemble a
- Par séparation, prendre le plus petit d’entre eux
Définition d’oméga (ω) dans le système Zermelo
ω est le plus petit ordinal récurrent
Définition des entiers dans le système de Zermelo
Les entiers sont les ordinaux α < ω
Qu’est-ce qu’un ensemble dénombrable dans le système de Zermelo
Un ensemble en bijection avec un entiers
Qu’est-ce qu’un ensemble fini dans le système de Zermelo ?
Un ensemble en bijection avec ω
Axiomes de remplacement
Pour ϕ(x, y, v) formule ensembliste où a et b n’apparaissent pas comme variable libre, on appelle axiome de replacement pour ϕ l’énonc suivant :
∀ a, ∀ v, (∀ x, y, z, ((ϕ(x, y, v) et ϕ(x, z, v)) ⇒ y = z) ⇒ ∃ b, ∀ y, (∃ x ∈ a, (ϕ(x, y, v)) ⇒ y ∈ b))
Quels axiomes forment le système ZF. ?
Les axiomes du système Zermelo auxquels on ajoute les axiomes de remplacement
Quel problème pose le système Z vis-à-vis des ordinaux ?
Il ne garantit pas la comparaison des bons ordres
Qu’est-ce que la suite des Vα ?
Il existe une unique suite d’esembles (Vα)Ord(α) indexée par les ordinaux et vérifiant pour tout α, λ :
- V0 = ∅
- Vα+1 = P(Vα)
- Vλ = ⋃α<λ Vα pour λ limite
Qu’est-ce que la classe V ?
La classe définissable des ensembles purs
Qu’est-ce que le rang ?
Une classe fonctionnelle sur la classe V, telle que le plus petit ordinal α tel que a ensemble pur appartient à Vα+1 est le range de a, et rang(α) = α ⇔ α ∈ Vα+1 \ Vα
Axiome du choix
On appelle “axiome du choix” l’énoncé “tout ensemble possède une fonction de choix”, c’est-à-dire :
∀ A, ∃ F : A ∖ {∅} → ⋃A, ∀ x ∈ A ∖ {∅}, (F(x) ∈ x)
Axiomes de Peano
- ∀ x, (x != 0 ⇔ ∃ y, (x = S(y)) (Succ1)
- ∀ x, y, (x !=y ⇒ S(x) != S(y)) (Succ2)
- ∀ x, (x + 0 = x) (Add1)
- ∀ x, y, (x + S(y) = S(x + y)) (Add2)
- ∀ x, (x × 0 = 0) (Mult1)
- ∀ x, y, (x × S(y) = x × y + x) (Mult2)
- ∀ X, ((X(0) et ∀ x, (X(x) ⇒ X(S(x)))) ⇒ ∀ x, X(x))) (Ind)
Lien entre les ordinaux et Peano
La structure (ω, 0, S, +, ×) satisfait les axiomes de Peano