Une bijection sur P([1,n])

jippy13

Bonjour amis matheux,

Je bloque dans la question 3 de l'exercice suivant ([1,n] représente n éléments entiers, et P l'ensemble des parties): 

Dans la question 3, je pars de l'hypothèse qu'il existe un ensemble A, tel que g(A)  $\neq $ f(A), la démo semble simple si n $ \in $ A   , mais dans le cas contraire je bloque. Une idée ?

lourrran

Si $n \in A$ , la démo semble simple. Ok
Si $n \not\in A$, alors la 'récurrence' intervient. 

On veut montrer qu'on a une certaine propriété $X(n)$ ; (il existe une unique fonction $f_n$ ...) 
Et là, on est en train de dire  : si pour un certain $n$, il y a plusieurs fonctions qui conviennent, alors il y a aussi plusieurs fonctions pour le rang $n-1$ .... et donc par descente, il y aurait plusieurs fonctions pour $n_0=1$ 
Or, pour $n_0=1$, on sait qu'il y a unicité.

jippy13

J'ai oublié de préciser que je butais sur la question 3a. Cad montrer que  $\varphi \neq \psi $    ou  $\rho \neq \chi $

lourrran

Par hypothèse, $f \neq g$ ; donc il existe (au moins) une partie $A_0$ de $\mathcal{P}(E)$ telle que $f(A_0) \neq g(A_0)$
Si cette partie $A_0$ contient l'élément $n$, alors $A_0 \cup \{n\} =A_0$ , et donc $\varphi ( A_0) = f(A_0)$,  et $\psi(A_0) = g(A_0)$
Et comme on a choisi $A_0$ tel que $f(A_0) \neq g(A_0)$ , on a donc un $A_0$ tel que $\varphi ( A_0) \neq \psi(A_0)$
Et donc $\varphi \neq \psi$
Et si la partie $A_0$ ne contient pas l'élément $n$ ... un raisonnement similaire va permettre de conclure que $\rho \neq  \chi$

JLT

La méthode de l'exo me paraît compliquée. On cherche $f$ telle que $A\subset g(A)$ où $g(A)=f(A)^c$ (le complémentaire de $f(A)$). Par bijectivité,

$\sum_A |A| = \sum_A |g(A)|$, et comme $|A|\leqslant |g(A)|$ pour tout $A$, on en déduit que $|A|=|g(A)|$ puis $A=g(A)$. Par conséquent $f(A)=A^c$.

Médiat_Suprème

$f([1, n]) = \emptyset$
$|A| = n-1 \Rightarrow f(A) = A^c$

Une petite, pseudo-récurrence fait le job : 
$|A| = n-2 \Rightarrow f(A) \subset A^c \wedge |f(A)| \neq 0  \wedge |f(A)| \neq 1 $ et donc $f(A) = A^c$
etc.

jippy13

@lourrran ".... un raisonnement similaire va permettre de conclure que ρ≠χ  " c'est justement là où je bute.
@JLT OK je suis d'accord... la seule solution est f(A)=complementaire (A ) mais pour revenir à lénoncé comment montrer que  ρ≠χ  (quand n∉A ) ? Merci du retour

lourrran

Euhhhh, et tu ne vois pas que c'est complètement similaire au cas que j'ai détaillé ?
Tu veux que je tape mot à mot, pour pouvoir faire Ctrl-C / Ctrl-V ?  Tu remplaces le symbole $\Cup$ par le symbole $\\$, tu remplaces les noms des fonctions ... et voilà.

jippy13

@lorran je reprends ton raisonnement avec $A_{0}$ en supposant  $f( A_{0}) \neq g( A_{0}) $ . Si n∉$A_{0}$, je ne vois pas comment aboutir à  ρ≠χ ( en   $A_{0}$) car on pourrait avoir $f( A_{0}) =g( A_{0}) \cup  \left\{ n\right\}$ et n∉ g( $A_{0}$) , c'est là où je bloque..

lourrran

Je recopie 'mot à mot' ma précédente démonstration, en l'adaptant à ce second cas :
Si cette partie $A_0$ ne contient pas l'élément $n$, alors $A_0 - \{n\} =A_0$ , et donc $\rho ( A_0) = f(A_0)$,  et $\chi (A_0) = g(A_0)$
Et comme on a choisi $A_0$ tel que $f(A_0) \neq g(A_0)$ , on a donc un $A_0$ tel que $\rho ( A_0) \neq \chi(A_0)$
Et donc $\rho \neq \chi$

jippy13

Le problème c'est que  $\chi (A_0) = g(A_0) \setminus   \left\{ n\right\}$ on sait pas si n appartient à $ g(A_0)$.
Si n appartient à $g(A_0) $ mais pas à $f(A_0) $ ou vice versa, on ne peut conclure ....

NicoLeProf

Bah non lourrran car l'énoncé ne dit pas cela... On a : $\rho(A_0)=f(A_0) \setminus \{n\}$ pas $f(A_0 \setminus \{n\})$... C'est là toute la difficulté de l'énoncé et de jippy13.

Doit-on présumer une éventuelle erreur d'énoncé?  

Pour le moment, avec $\rho$ définie comme dans l'énoncé, je ne suis pas inspiré pour proposer quelque chose d'intéressant...

raoul.S

Comme déjà relevé cet énoncé a l'air plutôt biscornu. Ceci dit voici une façon (tordue) de s'en sortir en respectant les consignes : 

Supposons $n\not\in A_0$. Remarquons que $\varphi$ est injective et donc bijective. Il existe donc $B\subset [\![1,n-1]\!]$ tel que $f(B\cup \{n\})=f(A_0)\setminus \{n\}$. Ceci entraîne que $n\in f(A_0)$, autrement on aurait $f(B\cup \{n\})=f(A_0)$ et de là $B\cup \{n\}=A_0$ et donc $n\in A_0$ ce qui est absurde. Le même raisonnement montre que $n\in g(A_0)$. Vu que $f(A_0)\neq g(A_0)$, on a $f(A_0)\setminus \{n\}\neq g(A_0)\setminus \{n\}$. C'est-à-dire $\rho(A_0)\neq \chi(A_0)$.

jippy13

@raoul.S Au top. Merci !! Il fallait y penser ! Mais comme l'a ecrit @Médiat_Suprème il me semblait plus simple et direct de démontrer que forcément f(A)=complémentaire(A)

jippy13

Chers amis matheux,

Je voudrais exposer dans ce post l'énoncé d'un exercice (déjà évoqué dans un précédent post) ainsi qu'une solution que j'ai rédigée.
Je vous remercie de me dire si cette solution vous semble correcte.

Soit E un ensemble fini. Montrez et trouver la seule bijection f de P(E) sur P(E) telle que 

$f(X)\cap X=\varnothing , \quad \forall X\in P(E)$

On voit facilement que $f(X)=E\setminus X$ répond à la question.

On peut remarquer que la condition s'ecrit aussi $f(E\setminus X) \subset X$

Il est trivial de voir que $f(E) = \varnothing $

De même l'image de E moins un singleton ne peut être égale qu'à ce singleton.

Montrons par récurrence forte descendante sur le cardinal de X tel que $f( X) = E \setminus X$

On le voit facilement  pour  $\left | X\right |=1$  ou   $\left | X\right |=0$.

 

Hypothèse:

$f(X) = E\setminus X$ pour tout X de cardinal $\geq p$

Soit X de cardinal p-1.

Montrons que $f(X) = E\setminus X$

D'après l'hypothèse, à ce stade, tous les éléments de P(E) de cardinal $\leq n-p$ sont déjà image par f.
En effet, si Y de cardinal $\leq n-p$ , son antécédant est son complémentaire de cardinal $\geq p$

Donc X ne peut avoir comme image un Y de cardinal > n-p.

Or $f(X)\cap X=\varnothing $ impose $\left | Y\right | \leq n-p+1$

donc $\left | Y\right | = n-p+1$

et comme $ Y\cap X= \varnothing  $  Y est forcément le complémentaire de X.

Voilà amis lecteur, qu'en pensez vous ?

jippy13

Chers amis matheux,

Je voudrais exposer dans ce post l'énoncé d'un exercice  ainsi qu'une solution que j'ai rédigée.
Je vous remercie de me dire si cette solution vous semble correcte.

Soit E un ensemble fini. Montrez et trouver la seule bijection f de P(E) sur P(E) telle que 

$f(X)\cap X=\varnothing , \quad \forall X\in P(E)$

On voit facilement que $f(X)=E\setminus X$ répond à la question.

On peut remarquer que la condition s'ecrit aussi $f(E\setminus X) \subset X$

Il est trivial de voir que $f(E) = \varnothing $

De même l'image de E moins un singleton ne peut être égale qu'à ce singleton.

Montrons par récurrence forte descendante sur le cardinal de X  que $f( X) = E \setminus X$

On le voit facilement  pour  $\left | X\right |=1$  ou   $\left | X\right |=0$.

 

Hypothèse:

$f(X) = E\setminus X$ pour tout X de cardinal $\geq p$

Soit X de cardinal p-1.

Montrons que $f(X) = E\setminus X$

D'après l'hypothèse, à ce stade, tous les éléments de P(E) de cardinal $\leq n-p$ sont déjà image par f.
En effet, si Y de cardinal $\leq n-p$ , son antécédant est son complémentaire de cardinal $\geq p$

Donc X ne peut avoir comme image un Y de cardinal > n-p.

Or $f(X)\cap X=Y\cap X=\varnothing $ impose $\left | Y\right | \leq n-p+1$ car  $\left | X\right |=p-1$.

donc $\left | Y\right | = n-p+1$

et comme $ Y\cap X= \varnothing  $  Y est forcément le complémentaire de X.

Voilà amis lecteur, qu'en pensez vous ?

jippy13

A l'admin => nouveau problème

[J'ai fusionné deux discussions car elles traitent essentiellement du même problème. --JLT]

zygomathique

salut

je note $A^*$ le complémentaire de A dans E

quand tu vois facilement que $ f(A) = A^*$ quel est l'intérêt d'écrire $f(A^*) \subset A$ puisqu'on a directement $f(A^*) = (A^*)^* = A$ ?

quant à une démo par récurrence je ne crois pas que ce soit le plus pertinent

enfin une injection (ou une surjection) sur un ensemble fini est une bijection (*)

vu la rédaction de l'énoncé : 

a/ j'ai trouvé un candidat
b/ je montre que c'est une bijection (quasi immédiat) avec (*) 
c/ je montre qu'elle est unique