Chapitre 2 Flashcards

Question

Comment peut-on résumer la structure construite à la somme de deux ensembles bien ordonnés ?

Answer 1

Les deux ensembles sont juxtaposés (mis à la suite l'un de l'autre) : (A, <) + (B, <) peut se voir comme A puis B

Answer 2

- L'addition de deux ensembles bien ordonnés est un ensemble bien ordonné - Associativité

Answer 3

A × B tel que (a, b) ⊏ (a', b') si et seulement si - b < b' - b = b' et a < a'

Answer 4

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

Answer 5

- La multiplication de deux ensembles bien ordonnés est un ensemble bien ordonné - Associativité - Distributivité sur l'addition

Answer 6

Si A a un plus petit élément a₀, un support d'une suite f d'éléments de A est {i | f(i) != a₀}, et A^(B) est le sous-ensemble de A^{B 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))}

Answer 7

- L'exponentation de deux ensembles bien ordonnés donc le premier a un plus petit élément est un ensemble bien ordonné - Distributivité

Answer 8

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

Answer 9

A ⊆ P(A) si et seulement A est transitif

Answer 10

∅ est un ensemble transitif

Answer 11

- 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

Answer 12

Une infinité

Answer 13

Un ensemble α est un ordinal si et seulement si α est transitif et que la restriction de ∈ à α est un bon ordre

Answer 14

- ∀ 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)

Answer 15

∅ est un ordinal

Answer 16

Si α est un ordinal α ∪ {α} est un ordinal

Answer 17

Pour tout ensemble A, S(A) = A ∪ {A}, et pour n un entier naturel, on note _n_ l'ordinal Sⁿ(∅)

Answer 18

Pour tout entier n, l'ordinal _n_ a exactement n éléments, à savoir les ordinaux _k_ pour k < n

Answer 19

Un ordinal strictement inclus dans α

Answer 20

Si A est un ensemble non-vide d'ordinaux, ∩A est un ordinal

Answer 21

Si α et β sont des ordinaux, α est strictement plus petit que β (α < β) si α est un élément de β

Answer 22

C'est l'inclusion : α ⊆ β est vrai si et seulement si soit α ∈ β, soit α = β

Answer 23

Son intersection

Answer 24

Tout ensemble non-vide d'ordinaux est un ensemble bien ordonné

Answer 25

Pour toute paire d'ordinaux α, β - α ∈ β - α = β - β ∈ α

Answer 26

À α lui-même : l'ensemble qui contient tous les ordinaux plus petits que α est α

Answer 27

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 α < θ

Answer 28

Aucun ensemble ne contient tous les ordinaux

Answer 29

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

Answer 30

ω est la borne supérieure des ordinaux _n_ pour n entier, c'est le premier ordinal infini

Answer 31

- Si ∀ β, β < α implique S(β) < α, alors ⋃α = α - Si ∃ β, α = S(β), alors ⋃α = β

Answer 32

- ⋃α ⊆ α car α est un ordinal, α ⊆ ⋃α car β < α ∈ β < α ⇒ β < S(β) < α ⇒ β ∈ S(β) ∈ α ⇒ β ⊆ ⋃α - β ⊆ ⋃α car γ ∈ β ⇒ γ < β ⇒ γ ∈ β ∈ α ⇒ γ ∈ ⋃α, ⋃α ⊆ β car ⋃α = ⋃S(β) = ⋃β ∪ β ⊆ β

Answer 33

Un ordinal non-nul α tel qu'il existe β vérifiant α = S(β)

Answer 34

Un ordinal non-nul α tel que α = ⋃α

Answer 35

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 α

Answer 36

Tout ensemble bien ordonnée est isomorphe à un unique ordinal

Answer 37

- 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

Answer 38

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

Answer 39

En construisant une bijection strictement croissante de A sur B

Answer 40

En construisant une bijection strictement croissante de A sur un segment initial de B

Answer 41

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 α = γ < β

Answer 42

En construisant une injection strictement croissante de A sur B

Answer 43

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 α ≤ β

Answer 44

Si α et β sont des ordinaux, on définit α + β comme l'unique ordinal γ tel que (γ, ∈) est isomorphe à (α, ∈) + (β, ∈)

Answer 45

- α + _0_ = _0_ + α = α - α + 1 = S(α) - Pour α fini, 1 + α = S(α) - Pour α infini, 1 + α = α - Associativité

Answer 46

Pour α, β ordinaux, α < β si et seulement s'il existe γ tel que α + γ = β

Answer 47

- 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 β = α + β \ α = α + γ

Answer 48

Pour tout ordinal α, l'addition à gauche d'α est strictement croissante et continue : - β < β' ⇒ α + β < α + β' - α + λ = sup_β<λ (α + β) pour λ limite

Answer 49

Pour tout ordinal β, l'addition à droite d'β est non décroissante et semi-continue inférieurement : - α ≤ α' ⇒ α + β ≤ α' + β - λ + β ≥ sup_α<λ (α + β) pour λ limite

Answer 50

- α + _0_ = α - α + S(β) = S(α + β) - α + λ = sup_β<λ (α + β) pour λ limite

Answer 51

Si α et β sont des ordinaux, on définit α × β comme l'unique ordinal γ tel que (γ, ∈) est isomorphe à (α, ∈) × (β, ∈)

Answer 52

Si α et β sont des ordinaux, on définit α^β comme l'unique ordinal γ tel que (γ, ∈) est isomorphe à (α, ∈)^{(β, ∈)}

Answer 53

- α × _0_ = _0_ × α = α - α × _1_ = _1_ × α = α - Associativité à gauche par rapport à l'addition ordinale - Distributivité à gauche par rapport à l'addition ordinale

Answer 54

- α^_0_ = _1_ - α^_1_ = α - Pour β != _0_, _0_^β = _0_ - _1_^β = _1_ - α^β+γ = α^β× α^γ - α^β×γ = (α^β)^γ

Answer 55

Pour tout ordinal γ vérifiant γ < α × β , il existe un couple d'ordinaux (ρ, σ) avec ρ < α et σ < β vérifiant γ = α × σ + ρ

Answer 56

Pour tout ordinal α != _0_, la multiplication à gauche d'α est strictement croissante et continue : - β < β' ⇒ α × β < α × β' - α × λ = sup_β<λ (α × β) pour λ limite

Answer 57

Pour tout ordinal α ≥ _2_, l'exponentiation de base α est strictement croissante et continue : - β < β' ⇒ α^β < α^β' - α × λ = sup_β<λ (α^β) pour λ limite

Answer 58

Pour tout ordinal β, la multiplication à droite d'β est non décroissante et semi-continue inférieurement : - α ≤ α' ⇒ α × β ≤ α' × β - λ × β ≥ sup_α<λ (α × β) pour λ limite

Answer 59

- α^_0_ = _1_ - α^S(β) = α^β × α - α^λ = sup_β<λ (α^β) pour λ limite

Answer 60

Pour tout ordinal β, l'exponentiation d'exposant β est non décroissante et semi-continue inférieurement : - α ≤ α' ⇒ α^β ≤ α'^β - λ^β ≥ sup_α<λ (α^β) pour λ limite

Answer 61

- α × _0_ = _0_ - α × S(β) = α × β + α - α × λ = sup_β<λ (α × β) pour λ limite

Answer 62

Pour tout ordinal β et tout ordinal non-nul α, il existe un unique couple d'ordinaux (ρ, σ) avec ρ < α et σ ≤ β vérifiant γ = α × σ + ρ

Answer 63

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 α

Answer 64

- 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é

Answer 65

On pose ω₀ = ω et ω_i+1 le plus petit ordinal qui ne s'injecte pas dans ω_i

Answer 66

ω₁ qui est le plus petit ordinal qui ne s'injecte pas dans ω

Answer 67

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

Answer 68

Pour q ≥ p ≥ 2, T_p,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 : - G_d,2 = d - G_{d,p+1 = T_p,p+1(G_d,p) - 1 si G_d,p est non-nul, 0 sinon}

Answer 69

Pour tout entier d, la suite G_d,p converge vers 0, c'est-à-dire qu'il existe p tel que G_d,p = 0

Answer 70

- Introduire une fonction de développement itéré adapté à l'arithmétique ordinale : T^p,ω(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 = T_p,ω(G_d,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, T^p,ω(n) < T^p,ω(n + 1)