Chapitre 1

Question 1

Comments les opérations sur les structures mathématiques et les opérations ensemblistes se correspondent-elles ?

Answer 1

• Morphisme naturel ↔ Application
• Isomorphisme ↔ Bijection

Question 2

Qu’est-ce que l’équipotence ?

Answer 2

A et B sont équipotents s’il existe une bijection de A sur B

Question 3

Quel type de relation est l’équipotence et comment le montrer ?

Answer 3

L’équipotence est une relation d’équivalence :
- réflexivité : l’identité est une bijection
- symétrie : l’inverse d’une bijection est une bijection
- transivité : la composition de deux bijections est une bijection

Question 4

Quel lien peut-on établir entre la relation entre deux ensembles et leur taille ?

Answer 4

• Si A et B sont en bijection, on peut faire correspondre les éléments donc ils sont de la même taille
• Si A s’injecte dans B, A est au plus aussi grand que B

Question 5

Théorème de Cantor-Bernstein (énoncé)

Answer 5

Soient A et B deux ensembles, s’il existe f : A → B et g : B → A deux injections, alors il existe h : A → B une bijection

Question 6

Théorème de Cantor-Bernstein (schéma de preuve)

Answer 6

• Définir B’ = Im(g) et A₀ = A\B’
• Définir récursivement A_i>0 = g(f(A_i-1))
• Définir h :
  
  • h(a) = g(f(a)) si a ∈ ⋃(A_i)
  • h(a) = a sinon
• Montrer que h est injective et surjective par construction
• Définir g^-1∘h la bijection de A sur B

Question 7

Qu’est-ce qu’un ensemble fini ?

Answer 7

Un ensemble vide ou en bijection avec une intervalle de la forme {1, 2, …, p} de {N}

Question 8

Qu’est-ce qu’un ensemble dénombrable ?

Answer 8

Un ensemble en bijection avec {N}

Question 9

Que peut-on dire des injections d’un ensemble fini dans lui même ? (énoncé)

Answer 9

Ce sont toutes des bijections.

Question 10

Que peut-on dire des injections d’un ensemble fini dans lui même ? (schéma de preuve)

Answer 10

• Se rapporter aux intervalles {1, …, p}
• Récurrence sur p :
  
  • Supposer que ok pour p - 1
  • Définir q = f(p) et g qui vaut f(i) pour i < q, f(i) - 1 pour i > q
  • Montrer que g bijective, puis que f bijective

Question 11

Qu’est-ce que le cardinal d’un ensemble fini A ?

Answer 11

p tel que A est en bijection avec {1, …, p} une intervalle de {N}

Question 12

Quand est-ce que deux ensembles finis sont en bijection ?

Answer 12

Lorsque leur cardinaux sont égaux, ou autrement dit lorsqu’ils sont en bijection avec la même intervalle {1, …, p} de {N}

Question 13

Quand est-ce que l’existence d’une injection de A dans B implique l’existence d’une surjection de B dans A ?

Answer 13

Lorsque A et B sont finis et A est non vide : soit f : A →B injective, on peut g : B → A surjective avec g(b) = f_-1(b) si b ∈ Im(f), g(b) = a ∈ A

Question 14

Quelles sont les bijections notables ?

Answer 14

• {N} et {N}×{N}
• {N}, {Z} et {Q}
• P({N}) et P({N})×P({N})
• P({N}), {R}, {N}^{N} et {0, 1}^{N}
• {R}, {R}×{R} et {R}ⁿ avec n fini

Question 15

Comment prouver “facilement” qu’il existe une bijection entre deux ensemble ?

Answer 15

En utilisant le théorème de Cantor-Bernstein : il suffit alors de construire deux injections plutôt qu’une bijection

Question 16

Quelle non-équipotence a été démontrée à l’aide de l’argument diagonal ? (énoncé)

Answer 16

Il n’existe pas de bijection entre {N} et {R}

Question 17

Quelle non-équipotence a été démontrée à l’aide de l’argument diagonal ? (schéma de preuve)

Answer 17

• Poser A = [0, 1] ⊆ {R} et f : {N} → A
• Poser f(i) le développement en base 3 de i sous la forme 0, a_i,0, a_i,1, …
• Poser a le réel dont le développement f(a) est 0, inv(a_0,0), inv(a_{1, 1}), …
• Conclure que f n’est pas surjective

Question 18

Théorème de Cantor (énoncé)

Answer 18

Il n’y a pas de surjection de A dans P(A) ni d’injection de P(A) dans A, les ensembles et leurs parties ne sont donc pas en bijection

Question 19

Théorème de Cantor (preuve)

Answer 19

• Supposer l’existence d’une surjection f de A dans P(A)
• Poser D = {x ∈ A | x !∈ f(x)}
• Poser D = f(b)
• Si b ∈ D, b ∈ f(x), b !∈ D
• Si b !∈ D, b !∈ f(x), b ∈ D

Question 20

Corollaire du théorème de Cantor : infinité d’infinis

Answer 20

Les ensemble {N}, P({N}), P(P({N})), … sont deux à deux non en bijection

Question 21

Problème et hypothèse du continu

Answer 21

Tout sous-ensemble infini de {R} est-il soit en bijection avec {N} soit avec {R} ? Faire l’hypothèse du continu revient à répondre positiviement à cette question

Question 22

Que peut-on dire d’un ensemble A s’il existe une injection de {N} dans A ?

Answer 22

A est un ensemble infini

Question 23

Qu’est-ce que l’inclusion ?

Answer 23

Si A et B sont des ensembles, A ⊆ B (A est inclus dans B) si tout élément de A est un élément de B

Question 24

Qu’est-ce que les parties d’un ensemble ?

Answer 24

Les parties P(A) de l’ensemble de A sont l’ensemble des sous-ensembles inclus dans A

Question 25

Quelles sont les quatre opérations ensemblistes principales ?

Answer 25

• L’union ∪
• L’intersection ∩
• La différence \
• La différence symétrique △

Question 26

Qu’est-ce que le complémentaire d’un ensemble ?

Answer 26

Soit A un ensemble inclus dans un ensemble de référence Ω, le complémentaire de A dans Ω est Ω \ A

Question 27

Quel type de relation est l’inclusion et pourquoi ?

Answer 27

L’inclusion est réflexive, transitive et antisymétrique, c’est donc un ordre.

Question 28

Qu’est-ce qu’un treillis ?

Answer 28

Un ensemble ordonné d’éléments tel que chaque paire possède une borné inférieure et une borne supérieure

Question 29

Qu’est-ce qu’un treillis distributif ?

Answer 29

Un treillis dans lequel l’opération inf est distributive par rapport à l’opértion sup et inversement

Question 30

Qu’est-ce qu’un treillis complémenté ?

Answer 30

Un treillis qui possède un minimum 0 et un maximum 1 et dans lequel tout élément possède un complément tel que le couple formé par l’élément et son complément à 1 comme borne supérieure et 0 comme borne inférieure

Question 31

Qu’est-ce qu’une algèbre de Boole ?

Answer 31

Un treillis distributif complémenté

Question 32

Comment construire une algèbre de Boole à partir d’un ensemble A ?

Answer 32

L’ensemble P(A) muni de l’opération d’inclusion est une algèbre de boole dont l’opération de borne supérieure est l’union, celle de borne inférieure est l’intersection, le maximum est A et le minimum est l’ensemble vide

Question 33

Qu’est-ce qu’un atome ?

Answer 33

Dans un ensemble A muni d’une relation d’ordre ≤ et d’un minimum 0, un atome de (A, ≤) est un successeur immédiat de 0

Question 34

Quels sont les atomes d’une algèbre de Boole construire à partir d’un ensemble A ?

Answer 34

Ce sont les singletons de P(A), ils sont les successeurs immédiats de l’ensemble vide par l’opérateur d’inclusion

Question 35

Proposition sur les algèbres de Boole finies (énoncé)

Answer 35

Toute algèbre de Boole finie est isomorphe à une algèbre du type (P(A), ⊆)

Question 36

Proposition sur les algèbres de Boole finies (schéma de preuve)

Answer 36

• Soit (B, ∧, ∨, 0, 1, ^c) une algèbre de Boole
• Pour tout élément b de B, on construit une chaîne maximale décroissante jusqu’à 0 et on note l’atome trouvé au bout de la chaîne
• A est l’ensemble fini des atomes ainsi trouvés

Question 37

Quels axiomes forment le système de Cantor ?

Answer 37

• L’axiome extensionnalité
• L’axiome d’extension
• L’axiome de compréhension

Question 38

Qu’est-ce que l’axiome d’extensionnalité ?

Answer 38

∀ A, A’ : Ens_τ, (A = A’ ⇔ ∀ x : τ, (x ∈ A ⇔ x ∈ A’))

Question 39

Qu’est-ce que l’axiome d’extension ?

Answer 39

∀ a₁, …, a_n : τ, ∃ A : Ens_τ, ∀ x : τ, (x ∈ A ⇔ (x = a₁ ∨ … ∨ x = a_n)) pour n > 0

Question 40

Qu’est-ce que l’axiome de compréhension ?

Answer 40

∃ A : Ens_τ, ∀ x : τ, (x ∈ A ⇔P(x) est vraie) avec P une propriété pertinente pour les objets de type τ

Question 41

Paraoxe de Berry (énoncé)

Answer 41

Si la propriété P(n) est “n peut être défini par une phrase française d’au plus cent caractères”, il ne peut pas exister d’ensemble des entiers possédant la propriété P

Question 42

Paradoxe de Berry (schéma de preuve)

Answer 42

• Définir N = {n | P(n)} qui contient au plus 27¹⁰⁰ nombres
• Définir n₀ le plus petit nombre qui n’est pas dans N
• On peut définir n en moins de 100 caractères donc n₀ ∈ N ce qui est paradoxal

Question 43

Conséquences du paradoxe de Berry

Answer 43

Le système Cantor ne peut être conservé puisque son axiome de compréhension permet l’apparition du paradoxe de Berry

Question 44

Quels axiomes forment le système de Frege ?

Answer 44

• L’axiome extensionnalité
• L’axiome d’extension
• L’axiome de compréhension restreinte

Question 45

Qu’est-ce que l’axiome de compréhension restreinte ?

Answer 45

∀ a₁, …, a_n : τ, ∃ A : Ens_τ, ∀ x : τ, (x ∈ A ⇔ Φ(x, a₁, …, a_n)) est vraie) avec Φ une propriété exprimée en logique du premier ordre

Question 46

Paradoxe de Russel (énoncé)

Answer 46

Supposer l’existence d’un type Ens général et d’un ensemble de tous les ensembles qui ne sont pas éléments d’eux-mêmes esdit contradictoire

Question 47

Paradoxe de Russel (schéma de preuve)

Answer 47

• Définir A = {X : Ens| X !∈ X}
• Si A ∈ A, A !∈A
• Si A !∈A, A ∈ A
• Conclure la contradiction de l’existence de A

Question 48

Conséquences du paradoxe de Russel

Answer 48

Le système de Frege ne peut être conservé puisque son axiome de compréhension restreinte permet l’apparition du paradoxe de Russel, il doit être remplacé par l’axiome de séparation

Question 49

Qu’est-ce que l’axiome de séparation ?

Answer 49

∀ a₁, …, a_n : τ, ∀ A : Ens_τ, ∃ B : Ens_τ, ∀ x : τ, (x ∈ B ⇔ (x ∈ A ∧ Φ(x, a₁, …, a_n))) avec Φ une propriété exprimée en logique du premier ordre

Question 50

Proposition concernant l’ensemble de tous les ensembles

Answer 50

Les objets de type ensemble ne forment pas eux-mêmes un ensemble (paradoxe de Russel)

Question 51

Qu’est-ce que l’axiome de la paire ?

Answer 51

∀ a, b : τ, ∃ A : Ens_τ, (a ∈ A ∧ b ∈ A)

Question 52

Qu’est-ce que l’axiome de l’union ?

Answer 52

∀ A : Ens_Ensτ, ∃ B Ens_Ensτ, ∀ x : τ, (∃ X : Ens_τ, (x ∈ X ∧ X ∈ A) ⇒ x ∈ B)

Question 53

Qu’est-ce que l’axiome des parties ?

Answer 53

∀ A : Ens_τ, ∃ B Ens_Ensτ, ∀ X : Ens_τ, (X ⊆ A ⇒ X ∈ B)

Question 54

Quel type unique est considéré dans le système de Zermelo ?

Answer 54

Les ensembles purs

Question 55

Qu’est-ce qu’un ensemble pur ?

Answer 55

Un ensemble dont les éléments sont eux-mêmes des ensembles purs

Question 56

Qu’est-ce qu’une formule ensembliste ?

Answer 56

Une formule obtenue en assemblant seulement des négations, conjonctions, disjonctions, implications et quantifications ainsi que des formules de la forme x = y et x ∈ y

Question 57

Quels axiomes forment le système de Zermelo fini ?

Answer 57

• 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 Φ