Démonstration Card(E) = n implique Card(P(E)) = 2^n

[ignacioc]

Bonjour,

J'ai des difficultés pour savoir si mon raisonnement est correct logiquement. Le problème est le suivant:

Démontrer par recurrence que pour tout n entier naturel, Card(E) = n implique Card(P(E)) = 2^n

Initialisation: Card(E) = 1. P(E) = ((1),(vide)). Card(P(E)) = 2 = 2^1. propriété vraie pour n = 1.

Hérédité (ici j'ai quelques doutes sur la validité de mon raisonnement) :

Supposons Card(E) = n implique Card(P(E)) = 2^n

Card(E) = n implique Card(P(E)) = 2^Card(E)

Card(E') = n + 1 implique Card(P(E')) = 2^(n+1)

Card(P(E')) = 2^Card(E')

Donc Card(E) = n + 1 implique Card(P(E)) = 2^n+1

Fin du raisonnement

(J'ai l'impression que tout le raisonnement est une tautologie, et je ne sais pas si ce raisonnement démontre la propriété. Je me suis inspiré de cette vidéo https://www.youtube.com/watch?v=RnRvPYsV494. Le raisonnement de cette vidéo aussi me semble une tautologie, mais si c'est un prof de math ça doit être correct.)


Merci
-----

[ThM55]

Je n'en suis pas sûr, mais j'ai l'impression que vous utilisez la propriété à démontrer dans la démonstration.

Je partirais par exemple de la proposition Card(P(E))=2^Card(E) pour tout ensemble de cardinal <= n.

Ensuite soit un ensemble E' de cardinal n+1. Soit a appartenant à E'. On peut écrire P(E') = P(E'\{a}) U Q et c'est une réunion disjointe, donc Card(P(E')) = Card(P(E'\{a})+Card(Q).

P(E'\{a}) est l'ensemble des parties de E' qui ne contiennent pas a. Par l'hypothèse de récurrence, son cardinal est 2^n, puisque Card(E'\{a})=n. Q est l'ensemble des parties de E' qui contiennent a. Si je prends un élément K de Q, alors K\{a} est dans P(E'\{a}). Donc Card(Q) est inférieur ou égal à Card( P(E'\{a}). Ensuite soit L un élément de P(E'\{a}). L'ensemble L U {a} est dans Q. Donc Card(P(E'\{a}) est inférieur ou égal à Card(Q). On obtient donc Card(Q) = Card(P(E'\{a}) = 2^n. On obtient finalement Card(P(E')) = 2^n + 2^n = 2^{n+1}.

(sans relecture, j'espère qu'on ne trouvera pas d'erreur dans ma preuve).

[ThM55]

Il faut un minimum de prudence avec la preuve par récurrence. On peut par exemple "démontrer" que tous les nombres d'un ensemble d'entiers sont égaux. En effet, cas initial: dans un singleton, tous les entiers sont égaux (trivial, il n'y a qu'un seul nombre). Supposons que ce soit vrai pour un ensemble à n éléments. Soit un ensemble à n+1 éléments. J'en enlève un, que j'appelle A, il me reste un ensemble à n éléments. D'après l'hypothèse de récurrence ces n nombres restants sont tous égaux. Je rajoute A et je retire cette fois un autre élément B. J'ai la même situation, tous les n éléments restants sont égaux, donc A est égal à tous les autres et la propriété est vraie pour n+1.

Evidemment c'est complètement faux et absurde. L'erreur est évidente, c'est que la manip où on enlève A puis on le remet et on enlève B ne marche pas pour un ensemble à 2 éléments, elle mène à une conclusion fausse. On raisonne sur deux ensembles disjoints comme si leur intersection était non vide.

Mais je pense que ma preuve pour card(P(E)) ne soufre pas de ce genre de défaut.

[gg0]

Bonjour Ignacioc.

Hérédité (ici j'ai quelques doutes sur la validité de mon raisonnement) :

Supposons Card(E) = n implique Card(P(E)) = 2^n OK

Card(E) = n implique Card(P(E)) = 2^Card(E) réécriture de la supposition, OK

Card(E') = n + 1 implique Card(P(E')) = 2^(n+1) ?? D'où sort cette ligne ? Où est la preuve de cette ligne ?

En fait, tu t'es contenté de faire semblant de rédiger une preuve par récurrence, mais comme il n'y a pas de preuve, ça vaut 0.
Et ce n'est en rien une tautologie ! C'est une tricherie (affirmation sans preuve). Ton travail est de prouver que si les ensembles à n éléments ont 2^n parties, alors tous les ensembles à n+1 éléments ont 2^(n+1) parties. Il va donc falloir parler de ces ensembles à n+1 éléments. Ce que fait ThM55.

Cordialement.

[A voir en vidéo sur Futura]