Théorie des ensembles Langage formel de la théorie des ensemble
Objectif: On prend le langage de la logique du 1er ordre avec
Définir la notion d’ensemble axiomatiquement
• Comment construire des ensembles ?
les symboles de prédicat
• Qu’est-ce que l’appartenance à un ensemble, l’égalité d’ensembles ? ‘=’ (binaire)
• Comment définir des relations et fonctions ?
’égalité des ensembles, --> à distinguer des autres égalités.
Peut-on éviter les contradictions entre axiomes ?
‘∈’ (binaire)
Y a-t-il un ensemble des ensembles ?
appartenance d’un objet à un ensemble
les variables : x, y, z, x1, x2, …, X, Y, Z, X1, X2, …
Référence
les constantes : a, b, c, a1, a 2, …
R. Cori, D. Lascar. Logique mathématique I et II, Masson, Paris, 1993
Notation: F[x1, …, xn] une formule ouverte où x1, …, xn sont les
variables libres.
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
1 de 21 2 de 21
Théorie de Zermelo Fraenkel (ZF) Axiome d’extensionnalité
Axiome d’extensionnalité (égalité d’ensembles) Deux ensembles sont égaux si et seulement si ils possèdent les mêmes
éléments.
Axiomes de construction :
Même extension :
Axiome de la paire
∀X ∀Y (∀z (z ∈ X ⇔ z ∈ Y) ⇒ X = Y)
Axiome de la réunion
Axiome des parties
Les axiomes de l’égalité fournissent la réciproque
Axiome de compréhension
∀X ∀Y (X = Y⇒ ∀z (z ∈ X ⇔ z ∈ Y))
Axiome de remplacement
Théorie ZFC
Axiome de choix
Et encore...
Axiome de fondation , axiomes de grands cardinaux, …
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
3 de 21 4 de 21
Notion de sous-ensemble Axiome de la paire
on note Avec deux ensembles x1 et x2
X ⊆Y on peut construire un ensemble y qui les contient les deux.
la formule
∀z (z ∈ X ⇒ z ∈ Y) ∀x1 ∀x2 ∃Y ∀z (z ∈ Y ⇔ (z = x1 ∨ z = x2)
par l’axiome : si X ⊆ Y et Y ⊆ X alors X = Y On note {a, b} l’ensemble satisfaisant cette formule pour
x1 = a et x2 = b.
Remarque cruciale
Il n’y a qu’une seule sorte d’objets : les ensembles
Un ensemble peut être élément d’un autre ensemble
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
5 de 21 6 de 21
Paire (suite) Axiome de la réunion
Notation On peut construire
Si a = b, on note {a} la paire {a, a} l’ensemble Y qui est la réunion de tous les ensembles faisant partie
d’un ensemble donné X.
Remarque
∀X ∃Y ∀z (z ∈ Y ⇔ ∃u (u ∈ X ∧ z ∈ u))
{a, b} = {a', b'} ssi a = a' et b = b' ou a = b' et b = a'
(=>) notation : Y = ∪ X
a ∈ {a, b} => a ∈ {a', b'} => a = a' ou a = b'
X
∪X
b ∈ {a, b} => b ∈ {a', b'} => b = a' ou b = b'
si ¬ (a = b ) alors a = a' et b = b' ou bien a = b' et b = a' Q R
M
Q
S R
H S
B M B H
{a} = {a'} ssi a = a' Q M
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
7 de 21 8 de 21
Propriétés de la réunion Axiome de partition
Si X est la paire {a, b}, l’ensemble Y = ∪X satisfait On peut former un ensemble dont les éléments sont tous les sous-
ensemble d’un ensemble donné x. On note cet ensemble P(x).
∀z (z ∈ Y ⇔ ∃u (u ∈ X ∧ z ∈ u), c-à-d
∀X ∃Y ∀Z (Z ∈ Y ⇔ ∀u (u ∈ Z ⇒ u ∈ X))
∀z (z ∈ Y ⇔ z ∈ a ∨ z ∈ b)
On note cet ensemble a ∪ b.
b bc
abc ab
a a, b, c
{a, b} ∪ {c} est noté {a, b, c} X c ac
On a :
P(X)
z ∈ {a, b, c} ⇔ z ∈ {a, b} ∨ z ∈ {c} ⇔ (z = a) ∨ (z = b) ∨ (z = c)
Si x a n éléments, Il y a 2n sous-ensembles
etc.
D’où la notation alternative pour P(x) : 2x
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
9 de 21 10 de 21
Schéma d’axiome de compréhension Une conséquence
Pour former l’ensemble de tous les éléments de X qui satisfont une Si on prend comme formule F[z] : ¬ (z = z)
formule F.
On a
Il s’agit d’une infinité d’axiomes de la forme:
∀X ∃Y ∀z (z ∈ Y ⇔ (z ∈ X ∧ ¬ (z = z)))
∀X ∃Y ∀z (z ∈ Y ⇔ (z ∈ X ∧ F[z]))
Comme aucun z ne peut satisfaire ¬ (z = z)
où F est une formule du langage des ensembles et n est un entier.
• il n’y a aucun élément dans y
• donc il existe un ensemble vide
On note l’ensemble Y par
Par l’axiome d’extensionalité il est unique
{ w ∈ X | F[w]}.
Notation: Ø ou {}
Rem. F peut avoir d’autres paramètres : F[z, v1, v2…, vn]
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
11 de 21 12 de 21
Tentative de simplification de l’ax. de compréhension (suite) Paradoxe de Russel
on a :
∃y∀z (z ∈ y ⇔ F[z]) ∃y∀z (z ∈ y ⇔ z ∉ z)
c’est à dire
y = { w | F[w]} si on prend z = y
on prend y ∈ y ⇔ (y ∉ y).
F[z] = z ∉ z est toujours faux, donc l’axiome est inconsistant
pour définir l’ensemble des ensembles qui ne se contiennent pas eux-
mêmes. Avec l’axiome complet on a :
d’après l’axiome simplifié: • ∀x∃y∀z (z ∈ y ⇔ z ∈ x ∧ z ∉ z)
∃y∀z (z ∈ y ⇔ z ∉ z) • pour z=y: y ∈ y ⇔ y ∈ x ∧ y ∉ y,
• qui est satisfaisable (y ∉ y et y ∉ x).
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
13 de 21 14 de 21
L’ensemble de tous les ensembles … (suite)
Peut-on avoir un ensemble a qui contient tous les autres comme ∀z.z ∈ b ⇔ (z ∈ a ∧ z ∉ z)
éléments ?
MAIS
a doit satisfaire la formule ∀v (v ∈ a)
lorsque z = b on a
l’axiome de compréhension avec la formule z ∉ z est:
b ∈ b ⇔ (b ∈ a ∧ b ∉ b)
∀x ∃y ∀z (z ∈ y ⇔ (z ∈ x ∧ z ∉ z))
comme a contient tout le monde
b ∈ a doit être vrai
ça doit être vrai pour x = a
donc b ∈ b ⇔ (b ∈ a ∧ b ∉ b) = b ∈ b ⇔ (b ∉ b) est faux
donc on a un ensemble b tel que
donc ∀z (z ∈ b ⇔ (z ∈ a ∧ z ∉ z)) est faux
∀z (z ∈ b ⇔ (z ∈ a ∧ z ∉ z))
donc un axiome serait faux !
Donc b ∉ a
Donc a n’existe pas
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
15 de 21 16 de 21
Axiome de remplacement Paires
Formule F[x, y] fonctionnelle si La paire ordonnée (a, b) est l’ensemble
{{a}, {a, b}}
∀x ∀y1 ∀y2 (F[x, y1] ∧ F[x, y2] ⇒ y1 = y2)
On démontre
si (a, b) = (a', b') alors a = a' et b = b'
Schéma d’axiome de remplacement
F[x, y] fonctionnelle ⇒ (∀x ∃y ∀z (z ∈ y ⇔ ∃w (w ∈ x ∧ F[w, z])) {{a}, {a, b}} = {{a'}, {a', b'}}
⇔ ({a} = {a'} ∧ {a, b} = {a', b'}) ∨ ({a} = {a', b'} ∧ {a, b} = {a'})
y est l’image de x par la «fonction» F ⇔ ({a} = {a'} ∧ {a, b} = {a', b'})
⇔ (a = a' et b = b')
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
17 de 21 18 de 21
n-tuples et produits Relations et Applications
triple : (a, b, c) = (a, (b, c)) Relation n-aire sur a : sous-ensemble de a × a × … × a (n fois) = an
n-tuple : (a1, a2, …, an) = (a1, (a 2, …, a n)) = (a1, (a2, (…, an))) = … Relation n-aire sur a1, a 2, …, a n, sous-ensemble de a1 × a2 × …× an
produit cartésien : e1 × e2 × … × en
l’unique ensemble p tel que : Application f : un ensemble de paires ordonnées (x, y) qui satisfait :
∀x (x ∈ p ⇔ ∃x1…∃xn (x1∈ e1 ∧ … ∧ xn ∈ e n ∧ x = (x 1, …, xn))) ∀x ∀y1 ∀y2 ((x, y1) ∈ f ∧ (x, y2) ∈ f ) ⇒ y1 = y2)
domaine (ensemble de départ) de f,
AB (A, C, D)
(A, C, E) { x ∈ ∪ ∪ f | ∃y (x, y) ∈ f }
C × (A, C, K) image (ensemble d’arrivée) de f
... { y ∈ ∪ ∪ f | ∃x (x, y) ∈ f }
(B, C, K) Application de a dans b :
DEK application dont le domaine est a et l’image b
G. Falquet, CUI, Université de Genève G. Falquet, CUI, Université de Genève
19 de 21 20 de 21
Produits et axiome de choix
Si I est un ensemble
Une famille d’ensembles indexée par un ensemble I est une
application dont le domaine est I
a : une famille indexée par I, ai = a(i) = image par a de i ∈ I
Produit Π i ∈ I a i =
l’ensemble des applications f telles que pour tout i ∈ I, f(i) ∈ ai.
Différence (intuitive) avec le produit cartésien: I peut être infini
Axiome de choix
si aucun ai n’est vide alors Π i ∈ I a i est non vide.
Ça à l’air complètement évident mais ça ne l’est pas, on ne peut le
déduire des autres axiomes !
G. Falquet, CUI, Université de Genève
21 de 21
