L'ensemble des permutations de IN

COGITO
COGITO
dans Algèbre
L’ensemble IS des permutations de N est-il dénombrable ?..

Je crois qu'on peut construire une application injective de P(IN) vers IS : à chaque partie A de IN on associe une permutation qui soit cyclique sur A et qui coïncide avec l'identité sur (IN \ A) ...Donc sauf erreur de ma part je viens de montrer que IS n'est pas dénombrable. Je me demande alors si on peut aller encore plus loin et trouver le " cardinal " de IS.

Merci d'avance.

Réponses

  • Calli
    Calli
    Bonjour,
    Si A est infini, qu'est-ce qu'un cycle sur A ?
  • marsup
    marsup
    Bonjour,

    Qu'appelles-tu une "permutation cyclique" sur un ensemble infini ?

    Quelle est la permutation "cyclique" que tu associes à $A = \N$ tout entier ?
  • COGITO
    COGITO
    Oups, désolé je n'ai pas fait attention à ça. N'importe quoi.
  • COGITO
    COGITO
    je crois qu'on peut régler ce problème : si A est infini, on associe à A une permutation qui envoie chaque élément de A vers l'élément qui le succède dans A...et qui coïncide avec l'identité ailleurs
  • marsup
    marsup
    Ben non, ta fonction est injective, mais pas surjective. Si $A = \N$, quel est l'antécédent de $0$ ?
  • Calli
    Calli
    Mais on peut quand même faire quelque chose qui ressemble à ce que tu as dit.
  • marsup
    marsup
    Vas-y explique-nous Calli, j'aimerais bien voir une jolie injection de l'ensemble des parties dans l'ensemble des permutations.
  • aléa
    aléa
    Non, l'idée était bonne. A toute partie infinie $A$ de $\N$, on peut associer une involution $i_A$ en groupant deux par deux les éléments de $A$ parcouru dans l'ordre croissant, les autres points étant fixes.
  • COGITO
    COGITO
    aléa ouiii c'est ça ce que j'allais dire
  • Calli
    Calli
    $\mathbb{Z}$ possède un dérangement "décalage" $x\mapsto x+1$. Et toute partie infinie $A$ de $\mathbb{N}$ est en bijection avec $\mathbb{Z}$, donc elle $A$ possède un dérangement similaire. Pour le reste, je reprends la base du raisonnement de Cogito.
  • marsup
    marsup
    Ah oui d'accord.

    Donc si $A \subset \N$, on peut regarder $B_A = (-A-1) \sqcup (A+1) \subset \Z$.
    Il y a une application (automorphisme) "décalage au suivant" sur $B_A$, que $A$ soit fini ou non (si $A$ fini, on "boucle" le dernier sur le premier).

    Donc à $A$, on associe une permutation de $\Z$, qui donne une permutation de $\N$.
  • Calli
    Calli
    Une autre possibilité d'injection $\mathcal{P}(\mathbb{N}) \to \mathfrak{S}(\mathbb{N}) $ : à $A$, on associe la permutation qui échange $2n$ et $2n+1$ si $n\in A$ et les laisse fixes sinon.
  • marsup
    marsup
    Ah ben oui, encore bien mieux : bravo Calli !
  • Calli
    Calli
    Réponse à ceci.

    @marsup : on peut faire ça, si tu veux. Je pensais associer à $A\subset\mathbb{N}$ infini la permutation $n\mapsto f^{-1}(f(n)+1)$ où $f:A\to\mathbb{Z}$ est bijective (et si $A$ est fini, un cycle sur $A$, comme proposé par Cogito).
  • Calli
    Calli
    Je dois être honnête, ce n'est pas moi qui avait trouvé l'injection avec les transpositions, c'est un ami.
  • marsup
    marsup
    Eh bien, je pense que cette injection est imbattable de toutes façons, donc elle doit vraisemblablement remonter à vue de nez au moins à Peano !
  • Chaurien
    Chaurien
    https://math.stackexchange.com/questions/367194/cardinality-of-the-set-of-bijective-functions-on-mathbbn
  • COGITO
    COGITO
    Pour montrer que cet ensemble est équipotent à $\R$, l'application qui associe à une permutation $f$ de $\N$ le réel $\sum_{k=1}^{\infty} f(k)10^{-k} $ est injective (par unicité du développement décimal) ...le théorème de Bernstein permet de conclure.
  • COGITO
    COGITO
    Chaurien, merciii
  • AD
    AD
    Bonsoir Cogito en réponse à http://www.les-mathematiques.net/phorum/read.php?3,1912280,1912324#msg-1912324
    L'argument << par unicité du développement décimal >> ne marche pas car $f(k)$ est en général supérieur à 9, il y a donc des retenues.
    Alain
  • COGITO
    COGITO
    Bonsoir Alain,

    Oui je vois..., j'ai une idée qui pourra marcher mais j'ai du mal à la formuler, pour chaque permutation f j'associe le réel $0,0f(0)0f(1)0f(2)......0f(k)......$, cette application est bien injective.CQFD
  • Calli
    Calli
    La signification de ta formule n'est pas claire (écrit-on f(k) en base 10 ?) .
  • marsup
    marsup
    Ah oui, tu encodes chaque $f(k)$ en binaire, et tu les concatènes en mettant suffisamment de "$0$" entre chaque : ça associe à $f$ une fonction binaire sur $\N$, donc un ensemble.

    Peut-être que ce serait mieux d'encoder seulement avec des $00$ et des $01$, comme ça on peut mettre $11$ comme séparateur.
  • COGITO
    COGITO
    marsup, oui effectivement ...

    Mercii
  • callipiger
    callipiger
    Bonsoir,
    on peut également prendre un série semi-convergente
    et à permutation que l'on construit changer la limite de la série
    et on obtient toutes les valeurs réelles
    ce qui donne une injection.

    correction d'une faute
  • Calli
    Calli
    Quand un élève avait proposé ça à mon prof de maths spé, il avait répliqué que c'est tuer une mouche avec un bazooka (:P)
  • Chaurien
    Chaurien
    convergeante ?
  • callipiger
    callipiger
    j'ai corrigé.
  • raoul.S
    raoul.S
    @Chaurien on dirait que tu dégustes aujourd'hui ;-)
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 20

AleshaCidrolinLudwigRescassolSchumiSutili.zitoussinicolas.patrois +13 Invités