Chapitre 2 Flashcards
Qu’est-ce qu’une relation bien fondée ?
Une relation binaire R sur un ensemble A est bien fondée si toute partie non vide X de A possède un élément minimal par R
Proposition sur l’induction à partir des relations bien fondées (énoncé)
Soit R une relation bien fondée sur A et soit P une propriété valide pour le principe de séparation tel que pour tout élément x de A, si P(y) est vrai pour tout y tel que y R x, alors P(x) est vrai, alors P(x) est vrai pour tout élément de A
Proposition sur l’induction à partir des relations bien fondées (schéma de preuve)
- Définir X l’ensemble des éléments pour lesquels P(x) est faux et x0 l’élément minimal de X
- Regarder tous les y tels que y R x0, qui ne sont pas dans X puisqu’ils sont plus petits que l’élément minimal
- Conclure en appliquant la prémisse
Qu’est-ce qu’un ordre ?
Une relation réflexive (si c’est un ordre partiel), antisymétrique et transitive
Qu’est-ce qu’un bon ordre ?
Un ordre sur un ensemble A tel que toute partie non-vide de A possède un plus petit élément
Qu’est-ce qu’un ensemle bien ordonné ?
Un couple (ensemble, ordre) tel que l’ordre est un bon ordre sur l’ensemble
Propriétés d’un ensemble bien ordonné
- Si l’ensemble est non-vide, il possède un plus petit élément
- Tout élément possède non-maximal un plus petit majorant
- Il n’existe pas de suite infinie strictement décroissante
- La restriction de l’ordre à tout sous-ensemble est également un ensemble bien ordonné
Proposition sur les ordres totaux biens fondés
Une relation d’ordre stricte est un bon ordre (strict) si et seulement si c’est un ordre total bien fondé
Qu’est-ce qu’un isomorphisme ?
Une application bijective et strictement croissante
Quelles sont les caractéristiques d’une application f strictement croissante de A sur B avec (A, < A) et (B, B) des ensembles bien ordonnés et «sub>A</sub> total ? (énoncé)
- f est injective
- x «sub>A</sub> y ⇔ f(x) «sub>B</sub> f(y)
Quelles sont les caractéristiques d’une application f strictement croissante de A sur B avec (A, «sub>A</sub>) et (B, B) des ensembles bien ordonnés et «sub>A</sub> total ? (schéma de preuve)
- Prouver f injective par cas
- Prouver l’équivalence
Quelles sont les caractéristiques d’une application strictement croissante f de (A, <) bien ordonné dans lui-même ? (énoncé)
a ≤ f(a) est vrai pour tout élément a de A
Quelles sont les caractéristiques d’une application strictement croissante f de (A, <) bien ordonné dans lui-même ? (schéma de preuve)
- Poser X = {a ∈ A | f(a) < x} et x0 le plus petit élément de X
- Appliquer f sur x0 et f(x0) et en déduire que f(f(x0)) < f(x0) < x0
- Par contradiction, X n’a pas de plus petit élément et est donc vide
Proposition de la rigidité (énoncé)
Si (A, «sub>A</sub>) et (B, «sub>B</sub>) sont deux ensembles bien ordonnés, il existe au plus un isomorphisme du premier sur le second
Proposition de la rigidité (schéma de preuve)
- Supposer qu’il existe deux isomorphismes f et g
- Construire g-1∘f strictement croissante
- Montrer qu’on a f(a) ≤ g(a) et g(a) ≤ f(a) donc f(a) = g(a)
Qu’est-ce qu’un segment initial ?
Si (A, <) est un ensemble bien ordonné et si a ∈ A, alors le segment initial de A déterminé par a est (Init(a) = {x ∈ A | x < a}, <)
Propriété du segment initial
- Clotûre par minorant
- Unicité
Quelles sont les propriétés d’un ensemble X ⊆ A avec (A, <) un ensemble bien ordonné et X un ensemble clos par minorant ? (énoncé)
Soit X = A, soit il existe a ∈ A tel que X = Init(a) le segment initial déterminé par a
Quelles sont les propriétés d’un ensemble X ⊆ A avec (A, <) un ensemble bien ordonné et X un ensemble clos par minorant ? (schéma de preuve)
- Définir Y = A\X
- Si Y est vide, X = A
- Sinon, y0 minore Y, et on montre Init(y0) ⊆ X et X ⊆ Initi(u0)
Inexistence d’isomorphismes entre (A, <) et un de ses segments initiaux (schéma de preuve)
- Supposons que f est un isomorphosme de A dans Init(a)
- f(a) > a par définition d’un isomorphisme (strictement croissant)
- f(a) < a car x ∈ Init(a) ⇒ x < a
- Contradiction donc conclusion
Inexistence d’isomorphismes entre deux segmentes initiaux distincts (schéma de preuve)
- Pour Init(a) et Init(b), deux cas symétriques a < b et b < a
- Si a < b, Init(a) segment initial de Init(b) donc on peut se ramener au cas de l’inexistence d’isomorphismes entre un ensemble et ses segments initiaux
Proposition de la comparaison pour les bons ordres (énoncé)
Soient (A, «sub>A</sub>) et (B, «sub>B</sub>) deux ensembles bien ordonnés, alors l’un exactement des cas suivants est vrai
- ils sont isomorphes
- le premier est un segment initial du second
- le second est un segment initial du premier
Proposition de la comparaison pour les bons ordres (schéma de preuve)
- Définir F telle que F(a) = b si et seulement si Init(a) est isomorphe à Init(b) et montrer que F est fonctionnelle et injective
- Montrer que si a ∈ Dom (F) et a’ < a, a’ ∈ Dom(F), c’est à dire que le domaine et l’image de F sont clos par minorant
- Regarder les 4 cas possibles :
- Dom(F) = A et Im(F) = B, alors A et B sont isomorphes
- Dom(F) = A et Im(F) est un segment initial de B, alors A est isomorphe à un segment initial de B
- Dom(F) est un segment initial de A et Im(F) = B, alors B est isomorphe à un segment initial de A
- Dom(F) est un segment initial de A déterminé par a et Im(F) est un segment inital de B déterminé par b, ce qui est impossible car on aurait F(a) = b, donc a ∈ Init(a) et b ∈ Init(b)
Comment se définit l’adition sur deux ensembles bien ordonnés ?
A ⊞ B = (A × {1}) ∪ (B × {2}) tel que (a, i) ⊏ (b, j) si et seulement si
- i = j = 1 et a < b
- i = j = 2 et a < b
- i < j
Comment peut-on résumer la structure construite à la somme de deux ensembles bien ordonnés ?
Les deux ensembles sont juxtaposés (mis à la suite l’un de l’autre) : (A, <) + (B, <) peut se voir comme A puis B
Propriété de l’addition de deux ensembles bien ordonnés
- L’addition de deux ensembles bien ordonnés est un ensemble bien ordonné
- Associativité
Comment se définit la multiplication sur deux ensembles bien ordonnés ?
A × B tel que (a, b) ⊏ (a’, b’) si et seulement si
- b < b’
- b = b’ et a < a’
Comment peut-on résumer la structure construite à la multiplication de deux ensembles bien ordonnés ?
Le premier ensemble est indexé par le second, c’est à dire que A × B correspond à autant de copies de A qu’il y a d’éléments dans B, et pour cahcune des copies, on l’indexe par un des éléments de B dans l’ordre
Propriété de la multiplication de deux ensembles bien ordonnés
- La multiplication de deux ensembles bien ordonnés est un ensemble bien ordonné
- Associativité
- Distributivité sur l’addition
Comment se définit l’exponentiation sur deux ensembles bien ordonnés ?
Si A a un plus petit élément a0, un support d’une suite f d’éléments de A est {i | f(i) != a0}, et A(B) est le sous-ensemble de AB</sub> formé par les suites à support fini, tel que f ⊏ g si et seulement si
- ∃ i, f(i) < g(i) et ∀ j > i, (f(j) = g(j))
Propriété de l’exponentiation de deux ensembles bien ordonnés
- L’exponentation de deux ensembles bien ordonnés donc le premier a un plus petit élément est un ensemble bien ordonné
- Distributivité
Qu’est-ce qu’un ensemble transitif ?
Un ensemble d’ensemble est transitif si et seulement si tout élément de l’un de ses élément lui appartient : ∀ X ∈ A, x ∈ X ⇒ x ∈ A
Que peut-on dire des parties d’un ensemble transitif ?
A ⊆ P(A) si et seulement A est transitif
Montrer qu’il existe au moins un ensemble transitif
∅ est un ensemble transitif
Comment construire des ensembles transitifs à partir d’un ou de plusieurs ensembles transitifs ?
- Si A est transitif A ∪ {A}, P(A) et ∪A sont transitifs
- Une réunion d’ensembles transitifs est transitive
- Une intersection d’ensembles transitifs est transitive
Combien existe-t-il d’ensembles transitifs ?
Une infinité
Qu’est-ce qu’un ordinal ?
Un ensemble α est un ordinal si et seulement si α est transitif et que la restriction de ∈ à α est un bon ordre
Propriétés condition d’un ordinal
- ∀ x ∈ α, x ⊆ α (transitivé de l’ensemble)
- ∀ x ∈ α, x !∈ x (anti-réflexivité)
- ∀ x, y, z ∈ α, (x ∈ y ∧ y ∈ z) ⇒ (x ∈ z) (transitivité de l’ensemble)
- ∀ A != ∅ ⊆ α, ∃ x ∈ A, ∀ y != x ∈ A, x ∈ y (bon ordre)
Montrer qu’il existe au moins un ordinal
∅ est un ordinal
Comment construire des ordinaux à partir d’un ordinal ?
Si α est un ordinal α ∪ {α} est un ordinal
Définition de l’opération successeur pour les ordinaux
Pour tout ensemble A, S(A) = A ∪ {A}, et pour n un entier naturel, on note n l’ordinal Sn(∅)
Définition de l’ordinal n
Pour tout entier n, l’ordinal n a exactement n éléments, à savoir les ordinaux k pour k < n
Qu’est-ce qu’un élément d’un ordinal α ?
Un ordinal strictement inclus dans α
Proposition sur l’intersection d’ordinaux
Si A est un ensemble non-vide d’ordinaux, ∩A est un ordinal
Définition de l’ordre des ordinaux
Si α et β sont des ordinaux, α est strictement plus petit que β (α < β) si α est un élément de β
Quel est l’ordre large associé à l’appartenance (ordre strict) pour les ordinaux ?
C’est l’inclusion : α ⊆ β est vrai si et seulement si soit α ∈ β, soit α = β
Quel est le plus petit élément d’un ensemble non-vide d’ordinaux ?
Son intersection
Quelle propriété sur les ordres peut-on dire des ordinaux ?
Tout ensemble non-vide d’ordinaux est un ensemble bien ordonné
Trichotomie des ordinaux
Pour toute paire d’ordinaux α, β
- α ∈ β
- α = β
- β ∈ α
À quoi correspond le segment initial Init(α) pour α un ordinal ?
À α lui-même : l’ensemble qui contient tous les ordinaux plus petits que α est α
Définition de l’induction par les ordinaux (première définition)
Soit P(α) une proposition valide pour le principe de séparation, alors
- soit θ un ordinal tel que pout tout α < θ, si P(α) est vraie si P(β) l’est pour tout β < α, alors P(α) est vrai pout tout α < θ
- P(α) est vraie si P(β) l’est pour tout β < α, alors P(α) est vrai pout tout α < θ
Quel est le plus petit élément d’un ensemble non-vide d’ordinaux ?
Son union
Paradoxe de Burali-Forti (énoncé)
Aucun ensemble ne contient tous les ordinaux
Paradoxe de Burali-Forti (schéma de preuve)
Il suffit de considérer qu’un tel ensemble existe et de montrer que l’union de cet ensemble est un ordinal qui n’y appartient pas
Définition de ω
ω est la borne supérieure des ordinaux n pour n entier, c’est le premier ordinal infini
Que vaut ⋃α pour α un ordinal ? (énoncé)
- Si ∀ β, β < α implique S(β) < α, alors ⋃α = α
- Si ∃ β, α = S(β), alors ⋃α = β
Que vaut ⋃α pour α un ordinal ? (schéma de preuve)
- ⋃α ⊆ α car α est un ordinal, α ⊆ ⋃α car β < α ∈ β < α ⇒ β < S(β) < α ⇒ β ∈ S(β) ∈ α ⇒ β ⊆ ⋃α
- β ⊆ ⋃α car γ ∈ β ⇒ γ < β ⇒ γ ∈ β ∈ α ⇒ γ ∈ ⋃α, ⋃α ⊆ β car ⋃α = ⋃S(β) = ⋃β ∪ β ⊆ β
Qu’est-ce qu’un ordinal successeur ?
Un ordinal non-nul α tel qu’il existe β vérifiant α = S(β)
Qu’est-ce qu’un ordinal limite ? (définition classique)
Un ordinal non-nul α tel que α = ⋃α
Définition de l’induction par les ordinaux (successeurs et limites)
Soit P(α) une proposition valide pour le principe de séparation, alors si
- P(0) est vraie
- si P(α) est vraie, P(S(α)) l’est aussi
- si λ est limite et si P(α) est vraie pour α < λ, alors P(λ) est vraie
Alors P(α) est vraie pour tout ordinal α
Proposition de la comparaison pour les ordinaux (énoncé)
Tout ensemble bien ordonnée est isomorphe à un unique ordinal
Proposition de la comparaison pour les ordinaux (schéma de preuve)
- Reprendre la proposition de la comparaison sur les bons ordres : puisque pour les ordinaux sont une famille d’ensemble bien ordonnés, on sait que pour tout ensemble bien ordonné (A, <)
- (A, <) est isomorphe à la suite des ordinaux entière → impossible car la suite des ordinaux ne forme pas un ensemble
- la suite des ordinaux est isomorphe à un segment initial de (A, <) → impossible car la suite des ordinaux ne forme pas un ensemble
- (A, <) est isomorphe à la suite des ordinaux → seule possibilité, et comme un segment initial de la suite des ordinaux est un ordinal, c’est fini
Qu’est-ce que ord(A, <) ?
ord(A, <) est le type d’ordre de l’ensemble bien ordonné (A, <), c’est-à-dire que c’est le seul ordinal avec lequel (A, <) est isomorphe
Soit ord(A) = α et ord(B) = β, comment montrer que α = β ?
En construisant une bijection strictement croissante de A sur B
Soit ord(A) = α et ord(B) = β, comment montrer que α < β ? (énoncé)
En construisant une bijection strictement croissante de A sur un segment initial de B
Soit ord(A) = α et ord(B) = β, comment montrer que α < ? (schéma de preuve)
Un isomorphisme de A dans un segment inital de B entraîne un isomorphisme de (α, >) dans un segment initial de (β, <) déterminé par un ordinal qu’on note γ et qui coïncide avec le segment initial, donc (α, >) est isomorphe à (γ, >) et α = γ < β
Soit ord(A) = α et ord(B) = β, comment montrer que α ≤ β ? (énoncé)
En construisant une injection strictement croissante de A sur B
Soit ord(A) = α et ord(B) = β, comment montrer que α ≤ β ? (schéma de preuve)
Une injection croissante de A dans B entraîne une injection croissante de (α, >) dans (β, <), or si on avait α > β on aurait une injection croissante (α, >) dans un de ses propres segments initiaux, donc on a bien α ≤ β
Comment se définit l’addition de deux ordinaux ?
Si α et β sont des ordinaux, on définit α + β comme l’unique ordinal γ tel que (γ, ∈) est isomorphe à (α, ∈) + (β, ∈)
Propriétés de l’addition d’ordinaux
- α + 0 = 0 + α = α
- α + 1 = S(α)
- Pour α fini, 1 + α = S(α)
- Pour α infini, 1 + α = α
- Associativité
Lien entre l’addition et l’ordre d’ordinaux (énoncé)
Pour α, β ordinaux, α < β si et seulement s’il existe γ tel que α + γ = β
Lien entre l’addition et l’ordre d’ordinaux (schéma de preuve)
- Si α + γ = β, puisque (α, <) est isomorphe à un segment initial de (α, <) + (γ, <), c’est un segment initialest isomorphme à un segment initial de (β, <) donc α ≤ β
- Si α ≤ β, (β \ α, <) est un ensemble bien ordonné isomorphe à un ordinal γ et (α, <) est le segment initial de β déterminé par α, et dans l’ordre sur β, les élément de α sont suivis par les éléments de β \ α donc β = α + β \ α = α + γ
Propriétés de l’addition à gauche d’ordinaux
Pour tout ordinal α, l’addition à gauche d’α est strictement croissante et continue :
- β < β’ ⇒ α + β < α + β’
- α + λ = supβ<λ (α + β) pour λ limite
Propriétés de l’addition à droite d’ordinaux
Pour tout ordinal β, l’addition à droite d’β est non décroissante et semi-continue inférieurement :
- α ≤ α’ ⇒ α + β ≤ α’ + β
- λ + β ≥ supα<λ (α + β) pour λ limite
Définition récursive de l’addition à gauche d’ordinaux
- α + 0 = α
- α + S(β) = S(α + β)
- α + λ = supβ<λ (α + β) pour λ limite
Comment se définit la multiplication de deux ordinaux ?
Si α et β sont des ordinaux, on définit α × β comme l’unique ordinal γ tel que (γ, ∈) est isomorphe à (α, ∈) × (β, ∈)
Comment se définit l’exponentiation de deux ordinaux ?
Si α et β sont des ordinaux, on définit αβ comme l’unique ordinal γ tel que (γ, ∈) est isomorphe à (α, ∈)(β, ∈)
Propriétés de la multiplication d’ordinaux
- α × 0 = 0 × α = α
- α × 1 = 1 × α = α
- Associativité à gauche par rapport à l’addition ordinale
- Distributivité à gauche par rapport à l’addition ordinale
Propriétés de l’exponentiation d’ordinaux
- α0 = 1
- α1 = α
- Pour β != 0, 0β = 0
- 1β = 1
- αβ+γ = αβ× αγ
- αβ×γ = (αβ)γ
Lien entre la multiplication et l’ordre d’ordinaux
Pour tout ordinal γ vérifiant γ < α × β , il existe un couple d’ordinaux (ρ, σ) avec ρ < α et σ < β vérifiant γ = α × σ + ρ
Propriétés de la multiplication à gauche d’ordinaux
Pour tout ordinal α != 0, la multiplication à gauche d’α est strictement croissante et continue :
- β < β’ ⇒ α × β < α × β’
- α × λ = supβ<λ (α × β) pour λ limite
Propriétés de l’exponentiation de base ordinale
Pour tout ordinal α ≥ 2, l’exponentiation de base α est strictement croissante et continue :
- β < β’ ⇒ αβ < αβ’
- α × λ = supβ<λ (αβ) pour λ limite
Propriétés de la multiplication à droite d’ordinaux
Pour tout ordinal β, la multiplication à droite d’β est non décroissante et semi-continue inférieurement :
- α ≤ α’ ⇒ α × β ≤ α’ × β
- λ × β ≥ supα<λ (α × β) pour λ limite
Définition récursive de l’exponentation à base ordinale
- α0 = 1
- αS(β) = αβ × α
- αλ = supβ<λ (αβ) pour λ limite
Propriétés de l’exponentiation d’exposant ordinal
Pour tout ordinal β, l’exponentiation d’exposant β est non décroissante et semi-continue inférieurement :
- α ≤ α’ ⇒ αβ ≤ α’β
- λβ ≥ supα<λ (αβ) pour λ limite
Définition récursive de la multiplication à gauche d’ordinaux
- α × 0 = 0
- α × S(β) = α × β + α
- α × λ = supβ<λ (α × β) pour λ limite
Comment se définit la division euclidienne de deux ordinaux ?
Pour tout ordinal β et tout ordinal non-nul α, il existe un unique couple d’ordinaux (ρ, σ) avec ρ < α et σ ≤ β vérifiant γ = α × σ + ρ
Proposition de non-injection des ordinaux (énoncé)
Pour tout ordinal infini α, l’ensemble d’ordinaux s’injectant dans α est un ordinal, et c’est le plus petit ordinal ne s’injectant pas dans α
Proposition de non-injection des ordinaux (schéma de preuve)
- Poser Θ l’ensemble des ordinaux qui s’injectent dans α, θ = ⋃Θ et β un ordinal infini de Θ
- Construire f une bijection de β sur S(β) : f(0) = β, f(n) = n - 1 pour n ≥ 1, f(γ) = γ pour ω ≤ γ < β
- Comme β s’injective dans S(β), β ∈ Θ ⇒ S(β) ∈ Θ, donc Θ n’a pas de plus grand élémént et ne contient pas sa borne supérieure θ
- Donc θ ne s’injecte pas dans α et est le plus petit ordinal ayant cette propriété
Comment se définit la suite ωi ?
On pose ω0 = ω et ωi+1 le plus petit ordinal qui ne s’injecte pas dans ωi
Borne supérieure de l’ensemble des ordinaux dénombrables
ω1 qui est le plus petit ordinal qui ne s’injecte pas dans ω
Qu’est-ce que le développement itéré de n en base p
Il s’agit d’exprimer n au moyen des entiers de 1 à p-1, de la somme, des multiplications et de l’exponentiation en base p
Définition des suites de Goodstein
Pour q ≥ p ≥ 2, Tp,q(n) est l’évaluation du développement itéré de n en base p dans lequel on a remplacé partout p par q, une suite de Goodstein à partir de d est alors :
- Gd,2 = d
- Gd,p+1</sup> = Tp,p+1(Gd,p) - 1 si Gd,p est non-nul, 0 sinon
Théorème de Goodstein (énoncé)
Pour tout entier d, la suite Gd,p converge vers 0, c’est-à-dire qu’il existe p tel que Gd,p = 0
Théorème de Goodstein (schéma de preuve)
- Introduire une fonction de développement itéré adapté à l’arithmétique ordinale : Tp,ω(n) est le développement itéré de n en base p dans lequel on a remplacé partout p par ω et q < p par q
- Construire Ĝd,p = Tp,ω(Gd,p) afin d’obtenir une suite d’ordinaux Ĝd,2, Ĝd,3, … pour tout entier d
- Montrer que Ĝd,p = Ĝd,p+1
- Conclure en utilisant le fait qu’il n’existe pas de suite infinie décroissante d’ordinaux et pour tout p et n, Tp,ω(n) < Tp,ω(n + 1)
