Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Licence Maths 1e ann AnalyseTopics traitant de analyse [tout]Lister tous les topics de mathématiques
Niveau Licence Maths 1e ann
Partager :

Dénombrabilité - Bijection de NxN -> N

Posté par
River 17-09-11 à 18:45

Bonjour, je vais vous poser l'énoncé qui m'est donné avant de vous expliquer mes difficultés, ce sera plus simple !

Montrer que l'application f: \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N} définie par f(n,m) = 2^n(2m+1)-1 est une bijection.
En déduire que \mathbb{Q} est dénombrable.

Bien entendu, il suffit de montrer que \mathbb{Q} est en bijection avec \mathbb{N} \times \mathbb{N} par la réciproque de f (définition de dénombrabilité de mon cours de S5).

Seulement, je ne sais trop comment m'y prendre pour démontrer la bijection de manière rigoureuse. Ce qui m'embête le plus est que la fonction prenne un couple d'arguments.

Pour l'injection, je pensais montrer que f(n,0) = f(m,0) \Longrightarrow n=m puis que f(0, n) = f(0, m) \Longrightarrow n=m. Mais cela est-il suffisant ?

Par contre pour la surjection, y a-t'il un moyen de la montrer rigoureusement ?

Posté par
MatheuxMatoure : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 18:47

bonsoir

non ! ce n'est pas suffisant !

il faut montrer que f(n,m)=f(n',m') n=n' et m=m'
pour avoir l'injectivité

Posté par
MatheuxMatoure : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 18:50

déjà parti ?
bon

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 18:53

Désolé j'étais plongé dans le problème, je ne m'attendais pas à une réponse aussi rapide ! ^^
Merci pour la précision en tout cas, je me suis rappelé que cette technique pour l'injection ne fonctionne que si f(0,n)+f(m,0)=f(m,n), ce qui n'est pas le cas.
Mais je vais continuer à chercher avec ces quatre variables, merci encore !

Posté par
MatheuxMatoure : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 18:54

ok

cela n'est pas trop dur... pose bien le problème et si tu as un doute donne ta méthode ici je reste encore un quart d'heure

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 18:57

Ok je vais me concentrer sur la chose alors !

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 19:09

Je pense avoir trouvé quelque chose :
En posant 2^n(2m+1)-1 = 2^q(2r+1)-1, on trouve après manipulation : 2^{n-q} = \frac{2m+1}{2r+1}.
Or, un entier pair ne peut s'écrire comme fraction d'entiers impairs.
Donc nécessairement, il faut que n=q et que m=r pour avoir 1 de chaque côté de l'équation.

Je pense que c'est le bon raisonnement, mais que faire pour la surjection afin de la montrer de manière rigoureuse ?

Posté par
MatheuxMatoure : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 19:12

c'est plutôt mal expliqué mais l'idée est là...

évite de diviser et travaille sur les entiers avec le théorème de Gauss

2n(2m+1)=2q(2r+1)
et (2m+1) impair est premier avec 2q donc 2m+1 divise 2r+1
de même on montre 2r+1 divise 2m+1
donc 2m+1=2r+1
donc m=r
continue

Posté par
MatheuxMatoure : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 19:16

pour la surjection, considère une ntier N et trouve lui un couple (n,m) antécédent

indication : distingue deux cas : N pair et N impair

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 19:18

D'accord, je vais me débrouiller avec ces indications, et surtout réviser mon programme de terminale spé parce que pour avoir oublié le théorème de Gauss, je mérite une punition sévère... ^^"

Merci pour tout en tout cas, je publie la solution dès que je la trouve !

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 20:27

Bon voici donc ma solution :

INJECTIVITÉ :

Soient n,m,q,r \in \mathbb{Q} tels que : f(n,m) = f(q,r).

On a donc : 2^n(m+1) = 2^q(r+1). [*]

Remarquons que pgcd(m+1;2^q) = 1, donc (m+1) divise (r+1) selon le théorème de Gauss.

De plus, pgcd(2^n;r+1) = 1, donc (r+1) divise (m+1).

Ainsi, on a : r+1 = m+1 et donc m=r.

De ce résultat, l'équation [*] donne 2^n = 2^q, donc nécessairement n=q.

Il y a donc injectivité de f.


SURJECTIVITÉ :

Notons N = f(n,m) = 2^n(2m+1)-1 \in \mathbb{N}, et trouvons un couple antécédent à N ;

Au vu de la forme de f(n,m), étudions selon la parité de N :

Pour N pair :

N+1 = 2^n(2m+1). Comme (N+1) est impair, pgcd(N+1;2^n)=1 et (N+1) divise (2m+1) par théorème de Gauss.

De plus, (2m+1) divise (N+1), donc N = 2m = f(0,m).

Pour N impair :

N+1 = 2^n(2m+1). Comme (N+1) est pair, pgcd(N+1;2m+1)=1 et (N+1) divise (2^n) par théorème de Gauss.

De plus, (2^n) divise (N+1), donc N = 2^n -1 = f(n,0).


COUPLES ANTÉCÉDENTS DE N : \left\lbrace\begin{array}l (n,0) \mbox{ si N impair} \\ (0,m) \mbox{ sinon} \end{array}

Puisque \mathbb{N} \times \mathbb{N} = \{ (n,0) + (0,m)  | n,m \in \mathbb{N} \}, l'application est surjective.

On en déduit que f : \mathbb{N} \times \mathbb{N} \longrightarrow \mahtbb{N} est bijective.

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 20:42

Pour montrer que \mathbb{Q} est dénombrable :

On écrit \mathbb{Q} = \{(n,m) \in \mathbb{N*} \times \mathbb{N*} \} \cup \{ 0 \} \cup \{(-n,m) \in \mathbb{N*} \times \mathbb{N*} \} = E_1 \cup \{0\} \cup E_2.

L'ensemble E_1 est en bijection avec \mathbb{N} par l'application f : \mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N} vue précédemment. Il est donc dénombrable.

L'ensemble \{0 \} est fini, donc dénombrable.

L'ensemble E_1 est en bijection avec \mathbb{N} par l'application g : (n,m) \longrightarrow f(-n,m), où n est par construction négatif. Il est donc aussi dénombrable.

L'union d'ensembles dénombrables est dénombrable, donc \mathbb{Q} est bien dénombrable.

Posté par
Foxdevilre : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 22:16

Bonsoir,

Alors pas tout à fait River pour la conclusion (considère le couple (1,2) et (2,4)). \mathbb{Q} est un quotient d'un sous ensemble de \mathbb{N} \times \mathbb{N} (\mathbb{N} \times \mathbb{N}^* plus exactement), ce qui nous donne bien évidemment que le cardinal de \mathbb{Q} est inférieur ou égal à celui de \mathbb{N} \times \mathbb{N} (\mathbb{Q} s'injecte dans \mathbb{N} \times \mathbb{N}, en donnant par exemple l'unique couple qui forme la fraction irréductible p/q où p et q sont premiers entre eux). Or vu que \mathbb{N} s'injecte trivialement dans \mathbb{Q} et que \mathbb{N} \times \mathbb{N} a la même cardinalité que \mathbb{N}, on prouve ainsi que \mathbb{Q} a la cardinalité de \mathbb{N} (la cardinalité de \mathbb{Q} est en somme bloquée entre celle de \mathbb{N} et celle....de \mathbb{N}!)

Posté par
MatheuxMatoure : Dénombrabilité - Bijection de NxN -> N 17-09-11 à 22:52

river :

dans ta démo de l'injectivité tu oublies les "2" (2m+1) à la place de (m+1)

quant à ta démo de la surjectivité, elle est un peu "farfelue" puisque tu supposes plus ou moins le résultat acquis ! et tu obtiens le résultat curieux que tout nombre pait est une puissance de 2 ... curieux non ?

donc à refaire !

si N est impair il est bien du type 2m+1 donc antécédent (0,m) ... OK
si N est pair ... N=2K
à toi de jouer maintenant

Posté par
Riverre : Dénombrabilité - Bijection de NxN -> N 18-09-11 à 10:28

Ok ben merci pour vos précisions, surtout sur la surjectivité cela m'aidera à l'avenir !

Et oui, il m'arrive d'oublier des lettres dans une équation quand je me force encore à travailler le soir ! ^^"


Rechercher
Menu
Espace membre
13 visiteurs
Changer d'île

Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :

Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1736 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !