Chapitre 1 Flashcards
Comments les opérations sur les structures mathématiques et les opérations ensemblistes se correspondent-elles ?
- Morphisme naturel ↔ Application
- Isomorphisme ↔ Bijection
Qu’est-ce que l’équipotence ?
A et B sont équipotents s’il existe une bijection de A sur B
Quel type de relation est l’équipotence et comment le montrer ?
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
Quel lien peut-on établir entre la relation entre deux ensembles et leur taille ?
- 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
Théorème de Cantor-Bernstein (énoncé)
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
Théorème de Cantor-Bernstein (schéma de preuve)
- 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
Qu’est-ce qu’un ensemble fini ?
Un ensemble vide ou en bijection avec une intervalle de la forme {1, 2, …, p} de {N}
Qu’est-ce qu’un ensemble dénombrable ?
Un ensemble en bijection avec {N}
Que peut-on dire des injections d’un ensemble fini dans lui même ? (énoncé)
Ce sont toutes des bijections.
Que peut-on dire des injections d’un ensemble fini dans lui même ? (schéma de preuve)
- 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
Qu’est-ce que le cardinal d’un ensemble fini A ?
p tel que A est en bijection avec {1, …, p} une intervalle de {N}
Quand est-ce que deux ensembles finis sont en bijection ?
Lorsque leur cardinaux sont égaux, ou autrement dit lorsqu’ils sont en bijection avec la même intervalle {1, …, p} de {N}
Quand est-ce que l’existence d’une injection de A dans B implique l’existence d’une surjection de B dans 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
Quelles sont les bijections notables ?
- {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
Comment prouver “facilement” qu’il existe une bijection entre deux ensemble ?
En utilisant le théorème de Cantor-Bernstein : il suffit alors de construire deux injections plutôt qu’une bijection
Quelle non-équipotence a été démontrée à l’aide de l’argument diagonal ? (énoncé)
Il n’existe pas de bijection entre {N} et {R}
Quelle non-équipotence a été démontrée à l’aide de l’argument diagonal ? (schéma de preuve)
- 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
Théorème de Cantor (énoncé)
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
Théorème de Cantor (preuve)
- 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
Corollaire du théorème de Cantor : infinité d’infinis
Les ensemble {N}, P({N}), P(P({N})), … sont deux à deux non en bijection
Problème et hypothèse du continu
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
Que peut-on dire d’un ensemble A s’il existe une injection de {N} dans A ?
A est un ensemble infini
Qu’est-ce que l’inclusion ?
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
Qu’est-ce que les parties d’un ensemble ?
Les parties P(A) de l’ensemble de A sont l’ensemble des sous-ensembles inclus dans A
Quelles sont les quatre opérations ensemblistes principales ?
- L’union ∪
- L’intersection ∩
- La différence \
- La différence symétrique △
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
Quel type de relation est l’inclusion et pourquoi ?
L’inclusion est réflexive, transitive et antisymétrique, c’est donc un ordre.
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
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
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
Qu’est-ce qu’une algèbre de Boole ?
Un treillis distributif complémenté
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
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
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
Proposition sur les algèbres de Boole finies (énoncé)
Toute algèbre de Boole finie est isomorphe à une algèbre du type (P(A), ⊆)
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
Quels axiomes forment le système de Cantor ?
- L’axiome extensionnalité
- L’axiome d’extension
- L’axiome de compréhension
Qu’est-ce que l’axiome d’extensionnalité ?
∀ A, A’ : Ensτ, (A = A’ ⇔ ∀ x : τ, (x ∈ A ⇔ x ∈ A’))
Qu’est-ce que l’axiome d’extension ?
∀ a1, …, an : τ, ∃ A : Ensτ, ∀ x : τ, (x ∈ A ⇔ (x = a1 ∨ … ∨ x = an)) pour n > 0
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 τ
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
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
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
Quels axiomes forment le système de Frege ?
- L’axiome extensionnalité
- L’axiome d’extension
- L’axiome de compréhension restreinte
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
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
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
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
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
Proposition concernant l’ensemble de tous les ensembles
Les objets de type ensemble ne forment pas eux-mêmes un ensemble (paradoxe de Russel)
Qu’est-ce que l’axiome de la paire ?
∀ a, b : τ, ∃ A : Ensτ, (a ∈ A ∧ b ∈ A)
Qu’est-ce que l’axiome de l’union ?
∀ A : EnsEnsτ, ∃ B EnsEnsτ, ∀ x : τ, (∃ X : Ensτ, (x ∈ X ∧ X ∈ A) ⇒ x ∈ B)
Qu’est-ce que l’axiome des parties ?
∀ A : Ensτ, ∃ B EnsEnsτ, ∀ X : Ensτ, (X ⊆ A ⇒ X ∈ B)
Quel type unique est considéré dans le système de Zermelo ?
Les ensembles purs
Qu’est-ce qu’un ensemble pur ?
Un ensemble dont les éléments sont eux-mêmes des ensembles purs
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
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 Φ
