Chapitre 1 Flashcards

1
Q

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

A
  • Morphisme naturel ↔ Application
  • Isomorphisme ↔ Bijection
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Qu’est-ce que l’équipotence ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A
  • Définir B’ = Im(g) et A0 = A\B’
  • Définir récursivement Ai>0 = g(f(Ai-1))
  • Définir h :
    • h(a) = g(f(a)) si a ∈ ⋃(Ai)
    • h(a) = a sinon
  • Montrer que h est injective et surjective par construction
  • Définir g-1∘h la bijection de A sur B
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Qu’est-ce qu’un ensemble fini ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Un ensemble en bijection avec {N}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

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

A

Ce sont toutes des bijections.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Quelles sont les bijections notables ?

A
  • {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}n avec n fini
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A
  • Poser A = [0, 1] ⊆ {R} et f : {N} → A
  • Poser f(i) le développement en base 3 de i sous la forme 0, ai,0, ai,1, …
  • Poser a le réel dont le développement f(a) est 0, inv(a0,0), inv(a1, 1), …
  • Conclure que f n’est pas surjective
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Théorème de Cantor (preuve)

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Problème et hypothèse du continu

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

A est un ensemble infini

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Qu’est-ce que l’inclusion ?

A

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

24
Q

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

A

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

25
Quelles sont les quatre opérations ensemblistes principales ?
- L'union ∪ - L'intersection ∩ - La différence \ - La différence symétrique △
26
Qu'est-ce que le complémentaire d'un ensemble ?
Soit A un ensemble inclus dans un ensemble de référence Ω, le complémentaire de A dans Ω est Ω \ A
27
Quel type de relation est l'inclusion et pourquoi ?
L'inclusion est réflexive, transitive et antisymétrique, c'est donc un ordre.
28
Qu'est-ce qu'un treillis ?
Un ensemble ordonné d'éléments tel que chaque paire possède une borné inférieure et une borne supérieure
29
Qu'est-ce qu'un treillis distributif ?
Un treillis dans lequel l'opération inf est distributive par rapport à l'opértion sup et inversement
30
Qu'est-ce qu'un treillis complémenté ?
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
31
Qu'est-ce qu'une algèbre de Boole ?
Un treillis distributif complémenté
32
Comment construire une algèbre de Boole à partir d'un ensemble A ?
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
33
Qu'est-ce qu'un atome ?
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
34
Quels sont les atomes d'une algèbre de Boole construire à partir d'un ensemble A ?
Ce sont les singletons de P(A), ils sont les successeurs immédiats de l'ensemble vide par l'opérateur d'inclusion
35
Proposition sur les algèbres de Boole finies (énoncé)
Toute algèbre de Boole finie est isomorphe à une algèbre du type (P(A), ⊆)
36
Proposition sur les algèbres de Boole finies (schéma de preuve)
- 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
37
Quels axiomes forment le système de Cantor ?
- L'axiome extensionnalité - L'axiome d'extension - L'axiome de compréhension
38
Qu'est-ce que l'axiome d'extensionnalité ?
∀ A, A' : Ensτ, (A = A' ⇔ ∀ x : τ, (x ∈ A ⇔ x ∈ A'))
39
Qu'est-ce que l'axiome d'extension ?
∀ a1, ..., an : τ, ∃ A : Ensτ, ∀ x : τ, (x ∈ A ⇔ (x = a1 ∨ ... ∨ x = an)) pour n > 0
40
Qu'est-ce que l'axiome de compréhension ?
∃ A : Ensτ, ∀ x : τ, (x ∈ A ⇔P(x) est vraie) avec P une propriété pertinente pour les objets de type τ
41
Paraoxe de Berry (énoncé)
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
42
Paradoxe de Berry (schéma de preuve)
- Définir N = {n | P(n)} qui contient au plus 27100 nombres - Définir n0 le plus petit nombre qui n'est pas dans N - On peut définir n en moins de 100 caractères donc n0 ∈ N ce qui est paradoxal
43
Conséquences du paradoxe de Berry
Le système Cantor ne peut être conservé puisque son axiome de compréhension permet l'apparition du paradoxe de Berry
44
Quels axiomes forment le système de Frege ?
- L'axiome extensionnalité - L'axiome d'extension - L'axiome de compréhension restreinte
45
Qu'est-ce que l'axiome de compréhension restreinte ?
∀ a1, ..., an : τ, ∃ A : Ensτ, ∀ x : τ, (x ∈ A ⇔ Φ(x, a1, ..., an)) est vraie) avec Φ une propriété exprimée en logique du premier ordre
46
Paradoxe de Russel (énoncé)
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
47
Paradoxe de Russel (schéma de preuve)
- 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
48
Conséquences du paradoxe de Russel
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
49
Qu'est-ce que l'axiome de séparation ?
∀ a1, ..., an : τ, ∀ A : Ensτ, ∃ B : Ensτ, ∀ x : τ, (x ∈ B ⇔ (x ∈ A ∧ Φ(x, a1, ..., an))) avec Φ une propriété exprimée en logique du premier ordre
50
Proposition concernant l'ensemble de tous les ensembles
Les objets de type ensemble ne forment pas eux-mêmes un ensemble (paradoxe de Russel)
51
Qu'est-ce que l'axiome de la paire ?
∀ a, b : τ, ∃ A : Ensτ, (a ∈ A ∧ b ∈ A)
52
Qu'est-ce que l'axiome de l'union ?
∀ A : EnsEnsτ, ∃ B EnsEnsτ, ∀ x : τ, (∃ X : Ensτ, (x ∈ X ∧ X ∈ A) ⇒ x ∈ B)
53
Qu'est-ce que l'axiome des parties ?
∀ A : Ensτ, ∃ B EnsEnsτ, ∀ X : Ensτ, (X ⊆ A ⇒ X ∈ B)
54
Quel type unique est considéré dans le système de Zermelo ?
Les ensembles purs
55
Qu'est-ce qu'un ensemble pur ?
Un ensemble dont les éléments sont eux-mêmes des ensembles purs
56
Qu'est-ce qu'une formule ensembliste ?
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
57
Quels axiomes forment le système de Zermelo fini ?
- 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 Φ