Bijection entre N et P(N) ?
Répondre à la discussion
Affichage des résultats 1 à 18 sur 18

Bijection entre N et P(N) ?



  1. #1
    invite18230371

    Bijection entre N et P(N) ?


    ------

    Bonjour,

    Je trouve fascinant les travaux de cantor même si je n'y comprends rien d'un point de vue formel.

    Il me semble qu'on a un résultat démontré disant que
    Le cardinal de l'ensembles des sous ensemble d'un ensemble E est strictement supérieur au cardinal de E.
    card(P(E)) > card(E)

    Toutefois, et J'AI FORCEMENT UNE ERREUR QUELQUE PART...
    J'ai semble-t-il trouvé une bijection entre élément de N et élément de P(N)

    0 j'associe l'ensemble vide.
    1 j'associe l'ensemble N.
    au Mieme nombre de la forme p1^n1*p2^n2... avec N = n1+n2+...
    J'associe le Mieme N-uplet selon une relation d'ordre récursive. (d'autres sont possibles)

    Par exemple pour N(somme des puissances de la décomposition en nombre premier) = 3 (on forme les triplets)
    on a
    2^3 = 1er triplet [0;1;2]
    2^2 * 3 = 2eme triplet [0;1;3]
    2 * 3^2 = 3eme triplet [0;2;3]
    2^2 * 5 = 4eme triplet [1;2;3]
    3^3 = 5eme triplet [0;1;4]
    ect...

    Cela donne :

    Exemple :
    0 : Sous-ensemble = []
    1 : Sous-ensemble = N
    2 : Sous-ensemble = [0]
    3 : Sous-ensemble = [1]
    4 : Sous-ensemble = [0;1]
    5 : Sous-ensemble = [2]
    6 : Sous-ensemble = [0;2]
    7 : Sous-ensemble = [3]
    8 : Sous-ensemble = [0;1;2]
    9 : Sous-ensemble = [1;2]
    10 : Sous-ensemble = [0;3]
    11 : Sous-ensemble = [4]
    12 : Sous-ensemble = [0;1;3]
    13 : Sous-ensemble = [5]
    14 : Sous-ensemble = [1;3]
    15 : Sous-ensemble = [2;3]
    16 : Sous-ensemble = [0;1;2;3]
    17 : Sous-ensemble = [6]
    18 : Sous-ensemble = [0;2;3]
    19 : Sous-ensemble = [7]
    20 : Sous-ensemble = [1;2;3]
    21 : Sous-ensemble = [0;4]
    22 : Sous-ensemble = [1;4]
    23 : Sous-ensemble = [8]
    24 : Sous-ensemble = [0;1;2;4]
    25 : Sous-ensemble = [2;4]
    26 : Sous-ensemble = [3;4]
    27 : Sous-ensemble = [0;1;4]
    28 : Sous-ensemble = [0;2;4]
    29 : Sous-ensemble = [9]
    30 : Sous-ensemble = [1;2;4]
    31 : Sous-ensemble = [10]
    32 : Sous-ensemble = [0;1;2;3;4]
    33 : Sous-ensemble = [0;5]
    34 : Sous-ensemble = [1;5]
    35 : Sous-ensemble = [2;5]
    36 : Sous-ensemble = [0;1;3;4]
    37 : Sous-ensemble = [11]
    38 : Sous-ensemble = [3;5]
    39 : Sous-ensemble = [4;5]
    40 : Sous-ensemble = [0;2;3;4]
    41 : Sous-ensemble = [12]
    42 : Sous-ensemble = [0;3;4]
    43 : Sous-ensemble = [13]
    44 : Sous-ensemble = [1;3;4]
    45 : Sous-ensemble = [2;3;4]
    ...
    30983 : Sous-ensemble = [3339]
    30984 : Sous-ensemble = [2;3;4;10;15]
    30985 : Sous-ensemble = [72;124]
    30986 : Sous-ensemble = [73;124]
    30987 : Sous-ensemble = [8;12;17;20]
    30988 : Sous-ensemble = [9;12;17;20]
    30989 : Sous-ensemble = [7;18;37]
    30990 : Sous-ensemble = [10;12;17;20]
    30991 : Sous-ensemble = [74;124]
    30992 : Sous-ensemble = [6;7;8;10;11;12]
    30993 : Sous-ensemble = [75;124]
    30994 : Sous-ensemble = [76;124]
    30995 : Sous-ensemble = [77;124]
    30996 : Sous-ensemble = [0;2;3;5;6;7;12]

    Quelqu'un voit-il mon erreur ? probablement définition de bijection, de l'ensemble des sous-ensemble,... ?
    Merci,

    -----
    Dernière modification par StrangQuark ; 26/09/2022 à 19h57.

  2. #2
    gg0
    Animateur Mathématiques

    Re : Bijection entre N et P(N) ?

    Bonjour.

    L'erreur est assez simple : Tu ne considères que des parties finies de N et N lui-même. Par exemple le sous-ensemble constitué de tous les entiers pairs n'est pas atteint.
    Je n'ai pas vérifié que tu atteins tous les sous-ensembles finis, mais déjà on voit que la plupart des parties de N ne sont pas atteintes.

    Cordialement.

  3. #3
    invite18230371

    Re : Bijection entre N et P(N) ?

    Ok, Exact !
    Il me manque effectivement BEAUCOUP d'ensemble vu comme ça...
    Je me disais que c'était suffisant d'imaginer qu'un nombre infiniment grand suffirait à générer ces ensembles.
    Avec les mains, on pourrait peut-être se dire que leur "valeur" dépasserait la cardinalité de N. Ce qui serait absurde dans N.

    En fait, c'est aussi un peu le reproche que je fais aux arguments du type diagonal de Cantor. (en vulgarisation du moins)
    Déjà, on arrivera jamais à lister tous les réel de [0;1]
    Puis, on arrivera jamais a venir changer la nieme décimal du nieme nombre.
    Donc, on construira jamais un nombre n’appartenant pas à la liste de départ.

    Mais bon, le niveau d'abstraction nécessaire est bien trop éloigné de mes moyens. Moi qui bloque déjà avec le raisonnement par l'absurde.

    Encore merci pour l'explication GG0 !

    PS : Je viens de faire la fonction qui prends un sous-ensemble finit et le transforme en entier. (l'autre sens)
    Tout marche bien jusqu’à 100 000...
    Dernière modification par StrangQuark ; 26/09/2022 à 21h44.

  4. #4
    GBZM

    Re : Bijection entre N et P(N) ?

    L'argument diagonal de Cantor est en fait parfaitement constructif.
    Si on te donne les n premières décimales des n premiers réels d'une liste de réels de [0,1[, tu fabriques effectivement une suite de n décimales telle que tout réel commençant ainsi sera assurément différent des n premiers réels de la liste (quelle que soit la suite de leurs décimales). Et ceci vaut pour tout entier n, aussi grand soit-il.

  5. A voir en vidéo sur Futura
  6. #5
    gg0
    Animateur Mathématiques

    Re : Bijection entre N et P(N) ?

    En fait, StrangQuark, tu faisais l'erreur habituelle de transposer à l'infini les méthodes qui marchent sur le fini : Si on a un ensemble fini, en prenant les parties à 0 élément, les parties à 1 élément, les parties à 2 éléments, ... on fini par avoir eu toutes les parties. Ce n'est plus vrai pour un ensemble infini.
    Pour l'argument diagonal tu raisonnes aussi en béotien, à commencer par "Déjà, on arrivera jamais à lister tous les réel de [0;1]", qui est justement la conclusion de la démonstration !! Et tu dis "Moi qui bloque déjà avec le raisonnement par l'absurde" alors que c'est généralement ainsi qu'on présente la preuve !! Normal, si tu confonds hypothèses et conclusion !!!
    En fait, pas besoin de preuve par l'absurde, l'argument diagonal de Cantor est que dans toute liste de réels entre 0 et 1 il manque des réels entre 0 et 1. Donc "on n'arrivera jamais à lister tous les réel de [0;1]". Rien de mystérieux.

    Là où tu m'inquiète, c'est que tu écris ensuite "Puis, on n'arrivera jamais a venir (??) changer la n-ième décimale du n-ième nombre." Autrement dit, tu lis une démonstration mathématique comme si c'était un mode d'emploi d'armoire Ikea !!! Il serait temps de te rendre compte qu'on travaille dans l'abstraction. Sinon, ça ne sert à rien de parler maths.

    Cordialement.

  7. #6
    gg0
    Animateur Mathématiques

    Re : Bijection entre N et P(N) ?

    "Je viens de faire la fonction qui prends un sous-ensemble finit et le transforme en entier. (l'autre sens)
    Tout marche bien jusqu’à 100 000... "
    Tu veux dire que tu as écrit un programme ? Et il marche pour tous les entiers ? Tu as testé ?
    Là encore, ça n'est pas des maths.

  8. #7
    GBZM

    Re : Bijection entre N et P(N) ?

    Ben justement, l'argument diagonal de Cantor est comme un mode de montage d'un meuble IKEA, en plus simple.
    Un oracle vous révèle une liste de réels dans de la façon suivante : si vous lui proposez un entier , il vous fournit les premières décimales des premiers réels de sa liste (ça forme un joli tableau carré ). En suivant la notice de fabrication de Monsieur Cantor, vous pouvez lui répondre en donnant les premières décimales d'un réel dont vous pouvez assurer qu'il n'est pas dans sa liste. Cette notice de fabrication dit simplement : prenez la diagonale du tableau et modifiez-la en remplaçant tous les chiffres non nuls par 0 et tous les 0 par 1.

    Il n'y a pas qu'une seule fonction qui réalise une injection de l'ensemble des parties finies de dans . En trouver une relève bien des mathématiques.

  9. #8
    MissJenny

    Re : Bijection entre N et P(N) ?

    Citation Envoyé par GBZM Voir le message
    Il n'y a pas qu'une seule fonction qui réalise une injection de l'ensemble des parties finies de dans . En trouver une relève bien des mathématiques.
    une injection c'est pas dur, une bijection c'est déjà moins évident.

  10. #9
    invite18230371

    Re : Bijection entre N et P(N) ?

    Je suis parfaitement conscient de mon approche Béotienne, et je ne me targue pas de faire des mathématiques.

    Pour l'argument diagonal, il me parait évident que,
    En fini :
    A n décimal, on a 2^n nombres possible (écriture des nombres décimaux en binaire), donc si on écrit n lignes, il est normal qu'il en manque !!! (en tous il en manque 2^n - n)
    L'argument diagonal permet d'en exhiber 1 de manière automatique.
    Super !
    Maintenant si n tends vers l'infini, c'est là que l'abstraction me manque et que je comprends plus.
    J'ai l'impression que c'est juste une extension du cas fini au cas infini, (en tout cas comme présenté dans la vulgarisation).

    Sinon oui j'ai bien 2 fonctions, qui sont réciproque l'une de l'autre (testé jusqu'à de 0 à 100 000).
    La première prends un entier et retourne un ensemble fini d'entier. L'autre fait l'inverse.
    Et par construction, il est certain que je ne n'ai aucun trou.
    C'est bien une bijection de N dans les sous-ensembles fini de N

  11. #10
    GBZM

    Re : Bijection entre N et P(N) ?

    Répéter "je ne comprends pas" ne te fera pas avancer d'un poil.
    Dans l'argument diagonal de Cantor, on n'a pas vraiment besoin d'infini actuel : c'est ce que j'ai raconté plus haut, je ne vais pas le répéter.
    En passant, il vaut mieux éviter d'écrire en binaire, ça ne fait que compliquer les chosesà cause des développements impropres (que des 1). Mais ça peut se régler en prenant les "décimales binaires" deux par deux, c.-à-d. en travaillant en fait en base 4.

    Pour ce qui est d'une bijection de l'ensemble des parties finies de sur , pas sorcier d'en exhiber une : à un ensemble fini d'entiers, on associe l'entier .

  12. #11
    invite18230371

    Re : Bijection entre N et P(N) ?

    Il faudra aussi expliciter la somme de n dans F si F vide.
    On imagine que c'est 0 mais tu n'en parles pas.

    Edit : Béotien: Personnage lourd, peu ouvert aux lettres et aux arts, qui a des goûts grossiers.
    Dernière modification par StrangQuark ; 27/09/2022 à 23h23.

  13. #12
    invite18230371

    Re : Bijection entre N et P(N) ?

    Ben justement, l'argument diagonal de Cantor est comme un mode de montage d'un meuble IKEA, en plus simple.
    As-tu déjà monté un meuble Ikea ?
    Parce que l'argument diagonal de cantor est tellement trivial que monter un meuble IKEA est équivalent (même encore plus simple) ?

    2^n>n me suffit pour dire que la proposition de l'oracle n'est pas complète.
    Mais pour l'infini je suis pas convaincu, et les scientifiques de l'époque, non plus.
    Mais aujourd'hui c'est trivial biensur, un meuble IKEA !
    Quel ironie, ce forum est *devenue* abjecte.

  14. #13
    GBZM

    Re : Bijection entre N et P(N) ?

    Plusieurs trucs à reprendre dans ce que tu écris, StrangQuark.
    Premièrement, le fait qu'une somme de réels indexée par l'ensemble vide est 0 fait partie intégrante de la définition des sommes indexées par un ensemble. Inutile donc de l'ajouter. Tui n'étais pas au courant, ce n'est pas grave, tu as appris quelque chose.
    Deuxièmement, ton "2^n>n me suffit pour dire que la proposition de l'oracle n'est pas complète" montre que tu es pas mal à côté de la plaque. La propriété de l'algorithme de la diagonale de Cantor, c'est qu'étant donné les n premières décimales des n premiers nombres de la liste, il produit les n premières décimales d'un réel qui est assuré de ne pas figurer dans la liste ; ce réel se dévoile au fur et à mesure que l'oracle dévoile sa liste. C'est visiblement ce simple fait que tu ne comprends pas. Je retente une explication, mais ça ne servira sans doute à rien si tu as décidé de ne pas comprendre.
    Un oracle, ou une boîte noire, produit une liste de réels de [0,1[ en remplissant le tableau des n premières décimales des n premiers nombres de la liste pour n=1,2,3,... . Parallèlement, tu modifies la diagonale du tableau selon l'algorithme de la diagonale de Cantor, pour écrire les n premières décimales (n=1,2,3,.. ) d'u n réel dont le développement ne coÎncide avec aucune ligne du tableau.
    Cette présentation évite l'infini actuel ; c'est l'infini actuel que refusait Kronecker, pour des raisons philosophiques et théologiques - pas mathématiques.

    Oui, l'algorithme de la diagonale de Cantor (pourquoi t'obstines-tu à ne pas mettre de majuscule à son patronyme ?) est bien plus simple que la notice de montage d'un meuble IKEA. Et j'ai une longue expérience dans ce domaine !
    Dernière modification par GBZM ; 28/09/2022 à 10h03.

  15. #14
    GBZM

    Re : Bijection entre N et P(N) ?

    "Mais pour l'infini je suis pas convaincu, et les scientifiques de l'époque, non plus."
    Ça c'est largement faux. Comme je l'ai déjà écrit, Kronecker refusait les considérations sur des infinis actuels pour des raisons extra-mathématiques. Mais de nombreux autres mathématiciens ont reconnu très tôt les avancées de Cantor. Tu devrais mieux te renseigner.

  16. #15
    gg0
    Animateur Mathématiques

    Re : Bijection entre N et P(N) ?

    Et on n'est plus au dix-neuvième siècle !

  17. #16
    MissJenny

    Re : Bijection entre N et P(N) ?

    j'ai vu pour la bijection, effectivement ça n'est pas sorcier mais je n'y avais pas pensé.

    personnellement je comprends aussi bien la démonstration de Cantor "avec infini actuel" (sans oracle).

    Est-ce qu'on connaît une autre démonstration élémentaire du fait que [0,1] (ou R) n'est pas dénombrable?

  18. #17
    GBZM

    Re : Bijection entre N et P(N) ?

    J'ai jusqu'ici parlé de l'argument diagonal de Cantor pour la non-dénombrabilité de .
    Mais il y a aussi un raisonnement bien connu (sur le fond pas différent de l'argument diagonal de Cantor) pour montrer que, pour tout ensemble , il n'y a pas de surjection de sur , l'ensemble des parties de .
    Soit une application de dans . Soit l'ensemble des éléments de tels que n'appartient pas à .
    Alors n'appartient pas à l'image de , donc n'est pas surjective.
    En effet, suppososns qu'il existe dans tel que . Alors
    - ou bien n'appartient pas à et donc appartient à , par définition de : absurde.
    - ou bien appartient à et donc n'appartient pas à , par définition de : absurde.

  19. #18
    MissJenny

    Re : Bijection entre N et P(N) ?

    Tiens, une autre preuve de la non dénombrabilité de R : https://talenta.usu.ac.id/jormtt/art...738/3312/15960

Discussions similaires

  1. Bijection entre R^N et r
    Par invitec3143530 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 19/12/2011, 07h29
  2. Bijection entre N et N²
    Par invite856a0e25 dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 27/02/2011, 17h32
  3. bijection entre 2 ensembles
    Par invitef07e911d dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 02/02/2010, 11h51
  4. Bijection entre lR et P(lN)...
    Par invitea77054e9 dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 19/11/2004, 08h18
  5. Bijection entre N et N²
    Par invitedffbb6ef dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/06/2004, 14h18