Calculs de cardinal, application injective

Soit E un ensemble à n éléments. On note C l'ensemble des couples de parties de E (c'est-à-dire C= P(E)*P(E) ).

Quel est le cardinal de C?
Soit Ω1 l'ensemble des couple A,B qui recouvrent E:
Ω1={(A,B)∈C,A∪B=E}
calculer le cardinal de Ω1
Soit Ω2={(A,B)∈C,A⊂B}
calculer le cardinal de Ω2
Soit ∂ l'application définie par:
∂: Ω1 → C
(A,B) → $A^c$ ,B).
Montrer que ∂ est injective. Identifier son image. Qu'en pensez-vous?
On tire au hasard un couple de parties (A,B), suivant la loi uniforme sur C. Quelle est la probabilité que l'une des parties soit incluse dans l'autre?

Alors pour la 1 je dirais n*n! c'est ça ?
après je ne vois pas comment faire, pouvez vous m'expliquer s'il-vous-plaît ?

Salut stella,

Non ce n'est pas ça, quel est le cardinal de P(E) ? Tu peux t'aider sur des exemples si tu ne sais plus (un ensemble à 2 éléments, à trois éléments...)
Si tu considères que tu as choisi une partie à k éléments pour A, quelles parties peux-tu choisir pour B ? Combien y a-t-il de parties à k éléments dans A ?

p(E) c'est k parmi n ???

je sais pas tro comment le voir

pour un element c'est 1
pour deux élément c'est 4 1,2,(1,2),(2,1)
pour 3 elements c'est 15
...
c'est bien sa

pour le deux on peut prendre pour $B=A^c$
jsuis perdue dans cette exercice

Alors pas tout à fait,
Pour un ensemble à 1 élément tu as deux parties possibles : l'ensemble vide et le singleton {1}
Pour un ensemble à deux éléments il y a 4 parties possibles : ∅, {1}, {2}, {1,2}. {1,2} et {2,1} sont identiques parce qu'on considère des ensembles et non des uplets (couple, triplets...), l'ordre n'a donc pas d'importance, contrairement à C qui est composé de couples et donc où l'ordre a une importance ( (A,B)≠(B,A) )
De la même manière pour un ensemble à 3 éléments il y a 8 parties possibles.
De manière générale, pour un ensemble à n éléments, P(E) a un cardinal de $2^n$ . Qu'en déduis-tu pour C ?

Pour le 2), effectivement le complémentaire de A convient, mais ce n'est pas le seul !

si $P (E) * P (E) = c a r d (P (E)) * c a r d (P (E)) = 2$ ^n $* 2$ ^n $2^{2n}$

mais vu qu'il y a un ordre il doit y avoir un somme quelque part

Non non c'est ça !
Il faut s'attaquer à la question 2) maintenant. On va donc considérer une partie A de k éléments, donc déjà il faut se demander combien il y a de parties à k éléments pris dans un ensemble à n éléments. Et ensuite on va chercher les ensembles B qui conviennent pour que A∪B=E et les compter !

A∪B=E
donc $A^c$ ⊂ E
B est un surensemble de $A^c$ ⇒ B= $A^c$ ∪A')avec A'⊂A

*tu choisis une partie A de E à k éléments (0kn)
(il y en a n parmi k) $A^c$ est donc fixé
**A étant un ensemble à k éléments A possède $2^k$ sous ensembles ce qui donne $2^k$ choix pour A'
en conclusion le nombre de couples (A,B) de P(E)*P(E)tels que(A∪B=E) est égal à la somme de k=0 à n de k parmi n $2^k$
apres je voit pas comment le calculer

Ok tout ça est très bien !
As-tu déjà vu le binôme de Newton ?

Pour la question 3, le principe sera sensiblement le même...

oui j'ai deja vu le binome de Newton par contre je sais pas calculer la somme de k=0 à n de k parmi n *2k

le jsais pas comment faire

C'est exactement la formule du binôme de Newton pourtant :
$\sum_{0}^{n}{\begin{pmatrix} n\k \end{pmatrix}2^k*1^{n-k}}$
En l'écrivant comme ceci tu verras peut-être mieux...

donc c'est égale à $1+2)^n$ soit $3^n$ c'est bien cela?

pour le 3 je sais pas comment partir

C'est ça !

Pour le 3) tu peux partir pareil, tu choisis une partie A de k éléments, quelles sont les différentes possibilités pour B ?

B est un surensemble de A ⇒ B= (A∪A')avec A'⊂E

*tu choisis une partie A de E à k éléments (0<k<n)
(il y en a n parmi k) A est donc fixé
**A étant un ensemble à k éléments A possède 2k sous ensembles ce qui donne 2k choix pour A'
en conclusion le nombre de couples (A,B) de P(E)*P(E)tels que(A⊂B) est égal à la somme de k=0 à n de k parmi n *2k

c'est bon???

Je ne suis pas d'accord avec ton raisonnement pour A'. A possède $2^k$ parties (attention à l'exposant), mais A' n'est pas nécessairement une partie de A... D'ailleurs la manière dont tu définis A' n'est pas la bonne. En fait ici la contrainte imposé à B est qu'il doit contenir tous les éléments de A, donc B peut se partitionner en deux ensembles : A et A' avec B=A∪A' et A∩A'=∅... Ce sont ces A' là qu'il faudrait compter !

Il y a $2^{2n}$ - $2^k$ partie de A pour connaitre le nombre de partie de A'?
Désoler si je suis nul

:rolling_eyes: non tu n'es pas nul, ce n'est pas un exercice facile, il demande pas mal d'abstraction...

Pour y revenir, ce que tu proposes n'est pas bon, effectivement il s'agit d'avoir une partie de E ne contenant pas les éléments de A mais dans ce que tu m'écris tu comptes toutes les parties de E, sauf les parties à k éléments. Nous ce que l'on veut compter c'est toutes les parties de E ne contenant aucun élément de A...

deja on sait que le nombre d'éléments de E c'est $2^{2n}$
reste a connaitre le nombre de A
donc card(A) se serait n parmi k $2^k$

Alors le nombre de parties de E c'est $2^n$ seulement (E a n éléments). $2^{2n}$ c'est le nombre d'éléments de C.
Le nombre de parties de A est $2^k$ , puisque A est un ensemble de k éléments. Mais ce n'est pas ça qui est important... Parce que si tu retranches le nombre de parties de A au nombre de parties de E tu obtiendras le nombre de parties de E qui n'ont pas k éléments, donc le nombre de parties qui ont plus de k éléments + le nombre de parties qui ont moins de k éléments, sachant que rien n'empêche ces éléments d'appartenir à A, ce n'est donc pas ce qu'il faut chercher !
Ce que l'on cherche est l'ensemble des parties ne contenant aucun élément de A, dans quel ensemble cherche-t-on donc ces parties ?

On cherche donc le nombre d'élément de $A^c$ vu que le élément de $A^c$ ne se trouve pas dans A
Sachant que C c'est l'ensemble des parties de A et $A^c$

apres commet calculer je voit pas

Combien y a-t-il d'éléments dans $A^c$ ? Combien de parties de $A^c$ peuvent exister ?

$2^{2n}$ c'est le nombre d'élément de C
je dirais $2$ ^n $2^{n-k}$ parties vu que c'est les parties de A
apres pour les parties je sais pas

Essaie d'expliquer plus clairement tes raisonnements, ça t'aidera et ce sera plus facile pour t'aider.
tu parles de : $2$ ^n $2^{n-k}$ , c'est le nombre de parties de quoi selon toi ?

Je reprends. On a choisi un ensemble A de k éléments, on sait qu'il y en a k parmi n de ce type. on cherche ensuite une partie B dans laquelle A soit incluse. Donc tous les éléments de A sont forcément dans B, les éléments qui peuvent changer sont donc les éléments qui ne sont pas dans A, donc qui sont dans $A^c$ . On va donc chercher à savoir combien de parties on peut former à partir des éléments de $A^c$ . B sera alors du type : A∪P où P est une partie de $A^c$ .
Il y a k éléments dans A, donc il y en a n-k dans $A^c$ , combien de parties sont formables à partir des éléments de $A^c$ ? (ce n'est pas $2$ ^n $2^{n-k}$ ...)

il y a $2^{n-k}$ parties dans $A^c$
en conclusion le nombre de couples (A,B) de P(E)*P(E)tels que(A⊂B) est égal à la somme de k=0 à n de k parmi n $2^{n-k}$
ce qui fait $3^n$
c bon???

c'est ça !

Vois-tu comment faire pour la 4) ?

le 4 c bon par contre le 5 je sais pas comment faire
il faut déterminer le cardinal de l'ensemble des couples de C tels que l'un des éléments soit dans l'autre
omega2={(A,B)∈C tel que A⊂B}
omega2'={(A,B)∈C tel que B⊂A}

en faisant attention car ces deux ensembles ont en commun les couples (X,X)où X est une partie quelconque de E

card de $omega2=3^n$ d'apres la question 3
je suppose que card de omega2' $3^n$
donc sa serait $3^n$ aussi

Ta supposition est juste mais elle mérite une démonstration ! Et c'est là où la question 4 intervient... Dans un sujet comme ça il est rare d'avoir une question inutile, si on te pose cette question 4 c'est sûrement pour quelque chose !
Donc dans la question 4, quelle image as-tu trouvé ? Qu'en as-tu déduis ?

Sinon je suis d'accord avec ce que tu as dit pour la question 5. Combien y a-t-il de couples du type (X,X) ?

on étudie l'application de C dans C ∂(A,B)→ $A^c$ ,B)
elle est injective<=>(∂(A,B)=∂(A',B')⇒(A,B)=(A',B'))
∂(A,B)=∂(A',B')⇒ $A^c$ ,B)=(A' $^c$ ,B')
⇒ $A^c$ =A' $^c$ et B=B'
or $A^c$ =A' $^c$ ⇒A=A'
donc si les images sont égales, les antécédents sont égaux, donc δ est injective
d'autre part un couple (A,B) quelconque de C est image (A,B)=∂ $A^c$ ,B) puisque donc l'application est surjective l'image de C par ∂ c'est C
ce qui est normal puisque C est un ensemble fini

voila ce que j'ai fait pour la 4)
je ne sais pas combien il y a de couples du type(X,X) mais je dirais n couple

Attention l'ensemble de départ de δ n'est pas C mais Ω1 ! Du coup pour l'injectivité je suis d'accord, mais pour l'ensemble d'arrivée ça change pas mal de choses !

Choisir un couple (X,X) dans C revient à choisir un X dans P(E)...

j'ai quoi à modifier dans mon 4)
pour les couple (X,X) il y en a $2^n$
donc pour le 5 on trouve $3$ ^n $2^n$

Ton ensemble d'arrivée n'est pas bon... Parce que l'ensemble de départ est Ω1, il te faut donc déterminer ce qu'est δ(Ω1).

Pour les couples (X,X) je suis d'accord, mais pas pour le résultat du 5)... Tu as oublié quelque chose ! D'autre part, on te demande un probabilité au final.

la proba du 5 c'st donc $3$ ^n $2*2^n$ / $2^{2n}$ )

on étudie l'application de C dans C ∂(A,B)→(Ac,B)
elle est injective<=>(∂(A,B)=∂(A',B')⇒(A,B)=(A',B'))
∂(A,B)=∂(A',B')⇒(Ac,B)=(A'c,B')
⇒ $A^c$ =A' $^c$ et B=B'
or $A^c$ =A' $^c$ ⇒A=A'
donc si les images sont égales, les antécédents sont égaux, donc δ est injective
d'autre part un couple (A,B) quelconque de C est image (A,B)=∂(Ac,B) puisque $(A$ ^c $^c$ =A donc l'application est surjective l'image de C par ∂ c'est C
ce qui est normal puisque C est un ensemble fini

j'ai rajouter sa $(A$ ^c $^c$ =A p-etre que sa va mieux

Non...
"on étudie l'application de C dans C ∂(A,B)→ $A^c$ ,B) " NON !!

"l'application est surjective l'image de C par ∂ c'est C" Non... Ce n'est pas possible car l'ensemble de départ estΩ1 et non C ! l'image de C par δ n'a pas de sens car δ n'est pas définie sur C (même si elle pourrait l'être bien sûr).

Pour le 5) c'est tout proche, mais tu as fait une petite erreur (puis n'oublie pas les parenthèses !)

Quelles études suis-tu ?

je suis en licence de maths

pour le 5) c'est
P(A⊂B)+P(B⊂A)-P(A=B) car (A⊂B)∩(B⊂A)=(A=B)
donc c'est $3$ ^n $+ 3$ ^n $2^n$
soit $2*3^n$ - $2^n$ c'est sa?

pour le 4)

on étudie l'application de omega1 dans C ∂(A,B)→(Ac,B)
elle est injective<=>(∂(A,B)=∂(A',B')⇒(A,B)=(A',B'))
∂(A,B)=∂(A',B')⇒(Ac,B)=(A'c,B')
⇒Ac=A'c et B=B'
or Ac=A'c⇒A=A'
donc si les images sont égales, les antécédents sont égaux, donc δ est injective
apres je voit pas pour le reste

Pour le 5) ok.

Pour le 4), à quoi correspond l'ensemble des couples $A^c$ ,B) tels que A∪B=E ? Fais un schéma (avec des patates) pour visualiser tout ça !

il faut que $A^c$ ⊂B
ou que $A^c$ =B

Oui ! Et donc l'image de δ est l'ensemble des couple $A^c$ , B) tels que $A^c$ ⊂B (quand tu dis A⊂B ça inclut le cas A=B)

Bon mais là on écrit $A^c$ , mais on pourrait l'appeler comme on veut, par exemple A' et donc si tu l'écris A' quel ensemble reconnais-tu ?

on reconnait donc l'ensemble omega2

En fait il n'y avait pas de lien avec la dernière question, j'avais fumé...

Mais donc qu'est-ce qu'on en déduit sur δ ?

on sait que ∂ est injective,
on en deduit qu'elle est aussi surjective
donc c'est une application bijective
c sa???