Bonjour,

Je suis en train de faire un exercice qui porte sur la récurrence. La, je dois montrer qu'un ensemble E possède 2^n éléments par récurrence. Dans la correction, 2 Phrases me semblent contradictoires :

J'ai bien compris qu'au final, Dans l'ensemble E, il y a le sous ensemble qui contient a ( composé de 2^n sous ensemble, hypothèse de récurrence ) et le sous ensemble qui ne contient pas a ( également composé de 2^n éléments ) donc au final on a 2^n + 2^n = 2^n+1 sous éléments pour l'ensemble E, mais concernant les phrases annotées d'un trait rouge, elles se contredisent non ? Ou alors je comprend pas le sens

Tu fais une confusion sur les ensembles je pense, là t'es en train de manipuler un ensemble d'ensembles et pas un ensemble d'éléments

Là tu considères l'ensemble des sous ensembles de E. Dans ces sous ensembles, soit il y a a soit il n'y pas a. S'iIl y a 2^n ensembles différents qiui ne continnent pas a ( par récurrence ) et pour former un ensemble qui ontient a, il suffit de faire {a} U un sous ensemble de E - {a} ne continent pas a et a donc 2^n elements.

finalement le nombre de sous ensemble de E c'est le nombre de sous ensembles qui conntinnent a + le nombre de ceux qui ne contiennent pas a , ça fait 2^n+1

Le 28 août 2017 à 17:28:40 the_ff3_fan a écrit :
Tu fais une confusion sur les ensembles je pense, là t'es en train de manipuler un ensemble d'ensembles et pas un ensemble d'éléments

Là tu considères l'ensemble des sous ensembles de E. Dans ces sous ensembles, soit il y a a soit il n'y pas a. S'iIl y a 2^n ensembles différents qiui ne continnent pas a ( par récurrence ) et pour former un ensemble qui ontient a, il suffit de faire {a} U un sous ensemble de E - {a} ne continent pas a et a donc 2^n elements.

finalement le nombre de sous ensemble de E c'est le nombre de sous ensembles qui conntinnent a + le nombre de ceux qui ne contiennent pas a , ça fait 2^n+1

SI on faisait un schéma représentatif de la situation, on aurait quoi du coup ?
Un carré vert ( qui représente l'ensemble E ) avec dedans un carré rouge ( qui contient a ) et un carré bleu ( qui contient pas a ) ou autre chose?

Le 28 août 2017 à 17:42:47 ServeurPrive a écrit :

Le 28 août 2017 à 17:28:40 the_ff3_fan a écrit :
Tu fais une confusion sur les ensembles je pense, là t'es en train de manipuler un ensemble d'ensembles et pas un ensemble d'éléments

Là tu considères l'ensemble des sous ensembles de E. Dans ces sous ensembles, soit il y a a soit il n'y pas a. S'iIl y a 2^n ensembles différents qiui ne continnent pas a ( par récurrence ) et pour former un ensemble qui ontient a, il suffit de faire {a} U un sous ensemble de E - {a} ne continent pas a et a donc 2^n elements.

finalement le nombre de sous ensemble de E c'est le nombre de sous ensembles qui conntinnent a + le nombre de ceux qui ne contiennent pas a , ça fait 2^n+1

SI on faisait un schéma représentatif de la situation, on aurait quoi du coup ?
Un carré vert ( qui représente l'ensemble E ) avec dedans un carré rouge ( qui contient a ) et un carré bleu ( qui contient pas a ) ou autre chose?

En fait, la manière la plus simple de visualiser, c'est de faire un arbre à deux branches initiales (une démo moins rigoureuse peut se faire par principe dichotomique d'ailleurs). Tu notes a1,a2,...an les n élements de ton ensemble En que tu places sur chaque ligne de ton arbre. Pour chacun de ses élements tu as 2 possibilités, soit il appartient au sous ensemble, soit non. Donc le nombre total des sous-ensemble différents possibles correspond au nombre total de branches à la fin de ton arbre (je sais pas si c'est très clair ).
Ça se fait aussi directement par dénombrement en raisonnant de la même manière.