card (AxB) = max(card(A); card(B))

remy C

bien le bonjour à tous !

voila, y a t'il quelqu'un ici qui connaitrait la preuve de :

soit A et B deux ensembles, A de cardinalité infinie, B non vide.
alors card (AxB) = max ( card(A); card(B)).
c'est assez important comme theoreme mais pas moyen de trouver une preuve sur le net ...
enfin, pas moyen d'en trouver une utilisant le theoreme de Cantor-Bernstein ( A et B equipotents ssi il existe une injection de A dans B, et une injection de B dans A) ( parrait qu'une telle preuve existe ...)

un lien internet ou une preuve vite fais sur le forum, et vous sauveriez une vie ...

merci à tous !
vive le 42

Foys0

On utilise le fait que si $X$ est infini alors $card(X)=card(X^2)$ et le théorème de Cantor-Bernstein: Il est clair que $max(card(A),card(B)) \leq card(A\times $ et réciproquement,
$card(A\times \leq max(card(A),card(B))^2 \leq max(card(A),card(B))$.

AD

Bonjour Rémi

{\bf Cela se fait directement} :
D'abord $Card(A) \leq Card(A\times $ par l'injection $a\mapsto (a,b_0)$, où $b_0\in B \neq\emptyset$
De même $Card(B) \leq Card(A\times $ puisqu'on sait trouver $a_0\in A$ qui est de cardinal infini.
Donc $\max\big(Card(A), Card(B)\big) \leq Card(A\times $

{\bf Réciproquement} :
1) Supposons $Card(B) \leq Card(A)$ donc on a une injection $B\xrightarrow{\ f\ } A$
Alors $Card(A\times \leq Card(A\times A)$ par l'injection $(a,b)\mapsto \big(a,f(b)\big)$
Mais $A$ est infini donc $Card(A\times A)=Card(A)$.
Soit au final $Card(A\times \leq Card(A) = \max\big(Card(A), Card(B)\big)$
2) Supposons $Card(A) \leq Card(B)$ en particulier $B$ est de cardinal infini. Le 1) en permutant les rôles de$A$ et $B$ donne $Card(A\times \leq Card(B) = \max\big(Card(A), Card(B)\big)$
Dans les deux cas $Card(A\times \leq \max\big(Card(A), Card(B)\big)$

{\bf Finalement} $Card(A\times = \max\big(Card(A), Card(B)\big)$

Alain

PS : Il reste le {\bf Lemme} $A$ infini alors $Card(A) = Card(A\times A)$ http://fr.wikipedia.org/wiki/Nombre_cardinal#Cardinal_infini

[Edit grillé, par Foys, qui donne une démo plus concise (:P) Alain]

christophe c

Ca dépend si tu supposes l'axiome du choix ou pas.

L'énoncé: pour tout E, il existe une bijection entre $E$ et $E\times E$ (1)

entraine l'axiome du choix.

Si tu veux bien de servir de AC, les posts de Foys ou AD te répondent en admettant (1).

Pour prouver (1), tu peux faire l'exo suivant:

1) Soit e un ordinal infini. Prouver qu'il existe une injection de e² dans e

Commence par: "soit e la plus petite éventuelle exception"

2) prouver que tout ensemble est en bijection avec un ordinal


Et tu peux décomposer 1) en:

cas1.1: e est un ordinal limite

cas1.2: e est un ordinal successeur.

et pour 1.1: tu peux traiter séparément le cas où e est un ordinal qui n'est pas un cardinal et le cas où e est un cardinal

Et seul le cas où e est un cardinal te fera un peu galérer

mpif0

Le cardinal d'un ensemble est le plus petit ordinal en bijection avec un ensemble (ça existe grâce à l'axiome du choix), un cardinal est un ordinal qui est le cardinal d'un ensemble (on a alors $\mathrm{card}(\kappa)=\kappa)$. On montre qu'un cardinal est l'ensemble de tous les types d'ordres (i.e. ordinaux) strictement plus petit que le cardinal.

On le montre le théorème que vous citez par induction transfinie sur les cardinaux. Soit $\kappa$ un cardinal infini. Supposons que pour tout cardinal $\alpha<\kappa$ (infini) on a montré la proposition, i.e. $\mathrm{card}(\alpha\times\alpha)=\alpha$.

On a alors :
\[
\mathrm{card}(T\times T)<\kappa,\quad\text{pour tout ordinal $T<\kappa$.}
\]
(c'est vraie dans le cas $T$ fini car $\kappa$ est infini, c'est aussi vraie dans le cas $T$ infini par l'hypothèse de récurrence)

On défini un bon ordre sur $\kappa\times\kappa$ (le produit cartésien) par $(\alpha,\beta)<(\gamma,\delta)$ si l'une des assertion suivante est satisfaite
\begin{enumerate}
\item $\max(\alpha,\beta)<\max(\gamma,\delta)$.
\item $\max(\alpha,\beta)=\max(\gamma,\delta)$ et $\alpha<\gamma$.
\item $\max(\alpha,\beta)=\max(\gamma,\delta)$ et $\alpha=\gamma$ et $\beta<\delta$.
\end{enumerate}

Pour $(\alpha,\beta)\in\kappa\times \kappa$, on note $X(\alpha,\beta)=\{(\gamma,\delta)\in\kappa\times\kappa|(\gamma,\delta)<(\alpha,\beta)\}$. C'est un ensemble bien ordonné (pour la restriction de l'ordre), on note $\tau(\alpha,\beta)$ le type d'ordre de $X(\alpha,\beta)$. Pour $(\alpha,\beta)<(\gamma,\delta)$, on a $X(\alpha,\beta)\subsetneq X(\gamma,\delta)$, donc $\tau(\alpha,\beta)<\tau(\gamma,\delta)$.

Soit $(\alpha,\beta)\in\kappa\times \kappa$, posons $T=\max(\alpha,\beta)+1$, c'est un ordinal et $T<\kappa$. Il est facile de voir que $X(\alpha,\beta)\subseteq T\times T$, de plus $\mathrm{card}(T)<\kappa$. On obtient alors :
\[
\mathrm{card}(X(\alpha,\beta))\le\mathrm{card}(T\times T)<\kappa.
\]
Donc $\tau(\alpha,\beta)<\kappa$. Ainsi $\tau\colon\kappa\times\kappa\to\kappa$ est bien défini et strictement croissante, donc injectif. Donc $\mathrm{card}(\kappa\times\kappa)\le\kappa$. L'autre inégalité est par ailleurs évidente. On obtient donc par induction la proposition voulue.

christophe c

Je serai toujours admiratif des intervenants comme mpif qui ont le courage de taper toutes ces lettres grecques par respect des usages... Quand je clique sur "latex", j'ai le vertige devant un tel courage, faut que je me trouve un smiley:

ev

Bonsoir Christophe

CC a écrit:

Bon je paie mon tribu alors...

Tu fais trop de probas en ce moment, à mon avis. ça vous fiche une orthographe en l'air, ça !

amicalement,

e.v.

egoroff

Je voie pa deu coi tue parl

christophe c

mais "payer son tribu-t/e/? ça s'écrit comment?

remy C

merci à tous !!!
j'ai pas le niveau assez élevé pour comprendre qqch sur les ordinaux ...
mais la preuve d'AD me convient !
un grand merci !
à plus tout le monde!

ev

A tribute (hommage) en anglais, un tribut en français (tributaire). Attention à l'orthographe aléatoire mon cher Dmitri.

amicalement,

e.v.

mpif0

Je viens de remarquer que ma preuve que $\tau(\alpha,\beta)<\tau(\gamma,\delta)$ est fausse. En fait il ne suffit pas de constater que $X(\alpha,\beta)\subsetneq X(\gamma,\delta)$. (on a par exemple $\{n\in\omega|n>1\}\subsetneq\omega$ mais leurs types d'ordres sont les mêmes.

Cependant dans notre cas ça marche quand même car $(\alpha,\beta)\in X(\gamma,\delta)$, de plus $(\alpha,\beta)$ est strictement plus grand que tout les éléments de $X(\alpha,\beta)$, du coup $\tau(\gamma,\delta)\ge \tau(\alpha,\beta)+1>\tau(\alpha,\beta)$.

christophe c

J'ai mis une synthèse dans le fil suivant, à toutes fins utiles.

http://www.les-mathematiques.net/phorum/read.php?16,583210,583210#msg-583210