Applications, théorie des ensembles - construire une injecti

[wotan]

Bonjour!

Ce problème fait partie d'un problème plus général qui aurait pu figurer dans la rubrique "Enigme". Mais commençons par là.

Je dispose d'un ensemble X éventuellement infini, et de 2 sous-ensembles A et B.

Soit une bijection de A vers X-A, et une bijection de B vers X-B.

Problème: construire à l'aide de et une injection de A dans B.

Par symétrie on peut de même trouver une injection de B dans A, et par suite cela permet de démontrer qu'il existe toujours une bijection entre A et B.

Merci de votre aide!

[beagle]

avec le cardinal, on se fait moins ch..., mais c'est pas l'exo, n'est-ce pas?

bon, alors on construit f(x) telle que:
1)x appartient à A inter B, f(x)=x

x n'appartient pas à A inter B, mais appartient à A
2)f(x)= fa(x) si appartient à B
3)f(x) =fa(x) puis f-b(x) si fa(x) n'appartient pas à b

les arrivées dans B sont différentes pour 1) et 2)
reste à montrer que les arrivées de 3) ne viennent pas d'un x déjà parti par 1) ou 2)

[Doraki]

J'y arrive pas sans l'axiome du choix.

[wotan]

avec le cardinal, on se fait moins ch..., mais c'est pas l'exo, n'est-ce pas?

Oui, absolument ... Le truc c'est que le cardinal implique d'utiliser l'axiome du choix, le but étant de s'en passer. Je précise que je ne suis pas mathématicien mais que j'ai pu m'intéresser au problème parce qu'il ne fait appel qu'à des notions assez basiques et que je suis un peu curieux...

Merci de t'intéresser à ce problème!

J'étais parti avec la démarche que tu proposes ... Mais je butais sur la dernière étape justement: montrer qu'on ne réutilises pas un x de A. Alors j'ai écrit un petit programme histoire de tester différents cas (avec des ensembles finis bien évidemment :rulaiz: ), et je pense que la construction proposée ne fonctionne pas, exemple avec:
A = { u, v, w }
B = { x, y, w } (w appartient bien à A et B)

fa:
u -> z
v -> y
w -> x

fb:
x -> u
y -> z
w -> v

on a alors:
f(u) = f-b(fa(u)) = y
et f(v) = y

J'ai essayé différentes combinaisons du même accabit pour former une injection générique, mais sans succès. :help:

[Doraki]

j'pensais avoir un truc mais non j'y arrive pas sans axiome du choix.

[chan79]

Oui, absolument ... Le truc c'est que le cardinal implique d'utiliser l'axiome du choix, le but étant de s'en passer. Je précise que je ne suis pas mathématicien mais que j'ai pu m'intéresser au problème parce qu'il ne fait appel qu'à des notions assez basiques et que je suis un peu curieux...

Merci de t'intéresser à ce problème!

J'étais parti avec la démarche que tu proposes ... Mais je butais sur la dernière étape justement: montrer qu'on ne réutilises pas un x de A. Alors j'ai écrit un petit programme histoire de tester différents cas (avec des ensembles finis bien évidemment :rulaiz: ), et je pense que la construction proposée ne fonctionne pas, exemple avec:
A = { u, v, w }
B = { x, y, w } (w appartient bien à A et B)

fa:
u -> z
v -> y
w -> x

fb:
x -> u
y -> z
w -> v

on a alors:
f(u) = f-b(fa(u)) = y
et f(v) = y

J'ai essayé différentes combinaisons du même accabit pour former une injection générique, mais sans succès. :help:

Bonjour
Dans le cas où X est fini, il me semble que (A inter B) et X-(A union B) doivent nécessairement avoir le même nombre d'éléments

[beagle]

Bonjour
Dans le cas où X est fini, il me semble que (A inter B) et X-(A union B) doivent nécessairement avoir le même nombre d'éléments

vi, m'avait gourré encore.
faut renvoyer le 3) les fa(x) qui ne sont pas dans B (dans X-(A union B), les renvoyer sur les images de A inter B, les images de 1)

L'axiome du choix , c'est pour les ensembles infinis?
Quand on dit qu'un sous ensemble inifini d'un ensemble infini est en bijection avec un autre sous-ensemble infini de cet infini, cela nécessite l'axiome du choix aussi?

[wotan]

vi, m'avait gourré encore.
faut renvoyer le 3) les fa(x) qui ne sont pas dans B (dans X-(A union B), les renvoyer sur les images de A inter B, les images de 1)

Oui je pense aussi, mais je n'ai pas trouvé de moyen de combiner fa, fb et leur soeur siamoise respective pour
y arriver. J'ai raté quelque chose?

L'axiome du choix , c'est pour les ensembles infinis?

De ce que j'ai lu sur wikipedia c'est pour les ensembles infinis. Il permet d'affirmer l'existence sans forcer à exhiber l'individu, philosophiquement parlant. Pour le coté math je suis bien mal placé d'en parler.

Quand on dit qu'un sous ensemble inifini d'un ensemble infini est en bijection avec un autre sous-ensemble infini de cet infini, cela nécessite l'axiome du choix aussi?

Je ne sais pas... J'espère que non parce que dans ce cas mon problème n'aurait pas de sens ... Demander de prouver un truc sans utiliser l'axiome du choix sur un objet dont l'existence dépend c'est beaucoup moins sexy du coup.

Par ailleurs je me renseigne directement auprès de la personne de qui je tiens cette énoncé ... Je posterai la réponse si j'en obtiens une toutefois.

Vous trouverez sa page en lien avec ce problème ici, au cas où:
https://dominiczypen.wordpress.com/2012/07/26/basics-on-maps/
Début du 3ème paragraphe: "It turns out that you can construct an injection from A into B ..."

[Doraki]

On prend x0 dans A
on regarde la suite (..., x(-2), x(-1), x0, x1, x2, ...)
où x(2n+1) = fa(x(2n)) ou fa-1(x(2n)), et x(2n-1) = fb(x(2n)) ou fb-1(x(2n)) (selon si x(2n) est dans A ou pas ; dans B ou pas)
Ca donne une énumération d'éléments de A et d'éléments de B.
Le gros problème c'est que selon notre choix de x0, l'orientation de notre suite peut changer, donc il faut faire gaffe à définir un truc qui ne dépende pas de ce choix.

Si pour tout n, xn est dans A\B union B\A, alors ses éléments qui sont dans A sont les éléments d'indice pair, et on peut prendre f(x(2n)) = fa(x(2n)), qui ne dépend pas du choix initial de x0 parmi la chaîne, et qui ne dépend pas du choix de n au cas où x(2n) apparaîtrait aussi ailleurs.

Il faudrait faire le même genre de choses pour tous les genres de suites possibles mais y'a toujours un bug.

Si il y a un bout infini de la suite faite avec que des éléments de A\B union B\A, on peut désigner comme point de repère le premier élément qui n'en fait pas partie, orienter la suite correctement, puis énumérer les éléments de la suite à partir de cet élément pour définir f sur les éléments de la suite.

Si les deux bouts infinis sont fait avec des éléments de A\B union B\A, on peut désigner un élément de référence et une orientation grâce au fait que la suite ne peut pas être symétrique et qu'il y a un nombre de dénombrable de telles suites.

Si il y a des éléments dans (A inter B) union ( X \ A \ B) infiniment souvent des deux cotés, je suis tenté de découper la suite là où il y a des éléments ni dans A ni dans B, pour en faire des petits morceaux finis qui contiennent chacun autant d'éléments de A que d'éléments de B (qui eux non plus ne peuvent pas symétriques) pour définir f, l'ennui étant qu'il y a alors deux manières de faire ce découpage, et qui sont indistingables. du coup ça foire.

[Doraki]

L'exercice provient de la page 19 de ce bouquin
http://books.google.fr/books?id=AVVSdnLemYUC&pg=PR11&hl=fr&source=gbs_selected_pages&cad=3#v=onepage&q&f=false
(ex 117).

A la page 6, il dit qu'il utilise le lemme de Zorn , et qu'il admet le résultat disant que tout ensemble peut être bien ordonné.

Donc l'auteur admet implicitement l'axiome du choix. Du coup je ne pense pas qu'il pensait à une preuve qui n'y faisait pas appel.

Et je suis d'avis que ton bloggueur l'a probablement utilisé sans s'en rendre compte ou alors que sa construction a des ambiguïtés (faut dire que c'est assez subtil comme problème)

[wotan]

Tout d'abord merci à tous les participants à ce petit défi!

Bien vu Doraki... J'ai un peu l'impression de vous avoir fait perdre votre temps à tous, si c'est le cas désolé! Quoiqu'il en soit c'est quand même un problème intéressant.

Ca m'étonne un peu de Dominic-le-blogueur d'avoir fait une erreur pareille. En fait dans un forum privé auquel j'ai accès il affirme pouvoir construire une injection en utlisant les bijections fa et fb, il n'y a pas d'ambiguité dans ce qu'il écrit.

Comme indiqué précédemment, j'ai posté sur ce même forum une demande pour qu'il crache le morceau ... restée sans réponse pour le moment. En tous les cas vous m'avez donné assez d'arguments pour le secouer un peu!

Dès que j'ai une réponse je la posterai quelle qu'elle soit, je vous dois bien ça!

[wotan]

La réponse vient de tomber .. ça n'a pas traîné. Je vous la livre sans l'avoir encore vérifiée (ni comprise .. :soupir2: )

Soit et nos 2 bijections:
et

On construit la suite d'ensembles:




Soit

Notre injection (à vérifier que c'en est bien une):
alors
alors
alors

[Doraki]

Il a l'air de supposer que pour tout a dans M, fa(a) n'est pas dans B, alors qu'il n'y a aucune raison que ce soit vrai.

si je prends X = {1;2;3;4} A = {1,2} B = {2,3} ;
fa : 1 -> 4 ; 2 -> 3
fb : 2 -> 1 ; 3 -> 4

Alors 2 est dans M1 puisque 2 = fb-1(1), 1 est dans A\B, et 2 est dans A.
Donc 2 est dans M et il propose de définir I(2) = fb-1(fa(2)) = fb-1(3), qui n'existe pas.

[wotan]

En effet, j'ai remarqué qu'il y avait un problème avec la construction des Mn en y réfléchissant un peu. Je confirme que je n'ai pas fait d'erreur en recopiant. J'ai posté une réclamation ... let's wait and see ...