Scribd
Importer
7 vues2 pages

Correct LT e

Le document présente des solutions à des exercices de logique et de théorie des ensembles, incluant des traductions de quantificateurs, des preuves concernant les ensembles de parties, et des exemples de relations d'équivalence. Il aborde également les notions d'injections et de bijections entre ensembles, ainsi que des propriétés des unions et des quantificateurs. Chaque exercice est accompagné d'analyses et de démonstrations détaillées.

Transféré par

aelisee09
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
7 vues2 pages

Correct LT e

Le document présente des solutions à des exercices de logique et de théorie des ensembles, incluant des traductions de quantificateurs, des preuves concernant les ensembles de parties, et des exemples de relations d'équivalence. Il aborde également les notions d'injections et de bijections entre ensembles, ainsi que des propriétés des unions et des quantificateurs. Chaque exercice est accompagné d'analyses et de démonstrations détaillées.

Transféré par

aelisee09
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Logique et Théorie des Ensembles — Solutions des

exercices de haut niveau

Exercice 1 — Quantificateurs imbriqués


1. Traduction : Pour tout élément x de E, il existe un élément y de E tel que, pour tout
élément z de E, si x est en relation avec y (c’est-à-dire xRy), alors y est en relation
avec z (c’est-à-dire yRz).
2. Négation :
∃x ∈ E, ∀y ∈ E, ∃z ∈ E, (xRy et ¬(yRz)).
3. Interprétation : Il existe un élément x dans E tel que, pour tout y dans E, on peut
trouver un z dans E vérifiant : x est en relation avec y, mais y n’est pas en relation
avec z.

Exercice 2 — Ensemble des parties


1. Preuve : Supposons par l’absurde qu’il existe une bijection f : E → P(E). Considé-
rons B = {x ∈ E : x ∈
/ f (x)}. Alors B ⊂ E, donc il existe b ∈ E tel que f (b) = B. On
a alors :
b ∈ B ⇐⇒ b ∈ / f (b) ⇐⇒ b ∈ / B,
ce qui est une contradiction. Donc il n’existe pas de bijection de E vers P(E).
2. Preuve : S’il existait une injection g : P(E) → E, alors en composant avec l’injection
canonique h : E → P(E) définie par h(x) = {x}, on obtiendrait une bijection entre
E et P(E) par le théorème de Cantor-Bernstein, ce qui contredit le point 1. Donc il
n’existe pas d’injection de P(E) dans E.
3. Remarque : L’hypothèse de finitude n’est pas utilisée dans les preuves ci-dessus, qui
sont valables pour tout ensemble E. Dans le cas fini, on peut aussi utiliser l’argument
cardinal : |P(E)| = 2|E| > |E|.

1
Exercice 3 — Relation d’équivalence non classique
√
1. Contre-exemple à la transitivité : Prenons (0, 0), (1, 0) et (1 + 2, 0). Alors :

(0, 0) ∼ (1, 0) car (0 − 1)2 + (0 − 0)2 = 1 ∈ Q,


√ √
(1, 0) ∼ (1 + 2, 0) car (1 − (1 + 2))2 + (0 − 0)2 = 2 ∈ Q,
√ √ √ √
(0, 0) ∼ (1 + 2, 0) car (0 − (1 + 2))2 + (0 − 0)2 = (1 + 2)2 = 3 + 2 2 ∈
/ Q.

Donc la relation n’est pas transitive, donc n’est pas une relation d’équivalence.
2. Si la relation était d’équivalence, la classe d’équivalence d’un point (x0 , y0 ) serait l’en-
semble des points (x, y) tels que (x − x0 )2 + (y − y0 )2 ∈ Q, c’est-à-dire l’union des
cercles centrés en (x0 , y0 ) dont le rayon au carré est rationnel.
3. La question sur le quotient n’a pas de sens puisque la relation n’est pas d’équivalence.

Exercice 4 — Unions et quantificateurs


S S
1. Preuve : Par définition, i∈I Ai = {x
S ∈ E : ∃i ∈ I, x ∈ A i }. Donc l’égalité i∈I Ai =
E équivaut à : pour tout x ∈ E, x ∈ i∈I Ai , c’est-à-dire ∀x ∈ E, ∃i ∈ I, x ∈ Ai .
2. Négation : La négation de l’équivalence est :
[ [
Ai = E et ∃x ∈ E, ∀i ∈ I, x ∈/ Ai ou Ai 6= E et ∀x ∈ E, ∃i ∈ I, x ∈ Ai .
i∈I i∈I

Cependant, comme l’équivalence est toujours


S vraie par définition, sa négation
S est tou-
jours fausse. En pratique, la négation de i∈I Ai = E est simplement i∈I Ai 6= E, ce
qui équivaut à ∃x ∈ E, ∀i ∈ I, x ∈
/ Ai .

Vous aimerez peut-être aussi