bijections N <-> ensemble des suites finies d'entiers

**acx01b** · 08/09/2010, 19h33

Bonjour je profite de mes vacances pour me poser des questions tordues, en l'occurence :

est-ce qu'il y aurait quelque part sur le net un texte qui parlerait de l'ensemble des bijections de $\text{[math]}$ dans $\text{[math]}$

où $\text{[math]}$ est l'ensemble des suites finies d'entiers dont la dernière valeur est non nulle

cet ensemble des bijections $\text{[math]}$ dans $\text{[math]}$ est intéressant car l'une de ces bijections correspond à la décomposition en facteurs premiers,
d'autres bijections existent qui n'ont a priori aucun rapport avec les nombres premiers, donc en gros je me demandais si on sait "construire" toutes ces bijections, quel est le cardinal de $\text{[math]}$ , si on peut faire des classes d'équivalences intéressantes sur ces bijections, etc...

merci

**Seirios** · 08/09/2010, 19h40

Bonsoir,

Déjà, pour le cardinal, on peut dire que c'est le même que $\text{[math]}$ , donc $\text{[math]}$ .

**acx01b** · 08/09/2010, 19h41

petite erreur de notation

je parle bien sûr de l'ensemble des bijections de $\text{[math]}$ dans $\text{[math]}$ privé de $\text{[math]}$

**Médiat** · 08/09/2010, 19h56

Pourquoi privé de 1 ?

Il est plus simple de parler de suites à "support fini", c'est à dire les suites U tels que l'ensemble des n tels que Un != 0 est fini, du coup pas de problème, on peut établir une bijection entre l'ensemble des suites à support fini de IN et IN*, sans se préoccuper des 0 à la fin, et cela permet de prendre en compte la suite constante égale à 0 dont l'image est 1.

De là à les étudier toutes cela met en jeu une combinatoire infinie ...

A voir en vidéo sur Futura · Aujourd'hui

invité576543 · 08/09/2010, 20h05

Envoyé par Phys2

Déjà, pour le cardinal, on peut dire que c'est le même que $\text{[math]}$ , donc $\text{[math]}$ .

Pourquoi ?

**Médiat** · 08/09/2010, 20h07

Envoyé par Michel (mmy)

Pourquoi ?

A cause de la bijection dont j'ai esquissé la définition, mais je peux développer.

**Médiat** · 08/09/2010, 20h11

Je viens de me rendre compte que je n'ai pas posté le premier message que j'avais préparé et du coup je n'ai rien esquissé du tout.
Sinon pour à une suite à support fini u on fait correspondre $\text{[math]}$ , $\text{[math]}$ étant le n^ième nombre premier

**Seirios** · 08/09/2010, 20h14

Sinon, on peut utiliser $\text{[math]}$ .

EDIT : Finalement, c'est plutôt une bijection pour l'ensemble des suites presque nulles plutôt que pour les suites à support finie, puisqu'on ne prend pas en compte correctement les zéros...

invité576543 · 08/09/2010, 20h16

La question s'adressait à Phys2.

Question pour tout le monde : on parle bien du cardinal de l'ensemble des bijections entre A et N moins un ensemble fini, non ?

N'est-il pas nécessairement égal au cardinal de l'ensemble des bijections de N dans N ?

Et en composant la fonction parité, cela semble au moins aussi grand que les fonctions de N dans {0,1}, non?

invité576543 · 08/09/2010, 20h28

Envoyé par Michel (mmy)

Et en composant la fonction parité, cela semble au moins aussi grand que les fonctions de N dans {0,1}, non?

Après réflexion, non...

Mais cela me paraît curieux que l'ensemble des bijections de N dans N ne soit que dénombrable, sans arriver à le montrer ou son contraire.

**Médiat** · 08/09/2010, 20h46

Il y a clairement moins de bijection de IN dans IN que d'application de IN dans IN, donc ce cardinal est inférieur ou égal à $\text{[math]}$ .

A chaque sous ensemble E de IN dont le complémentaire n'est pas un singleton on fait correspondre une bijection qui laisse invariants les éléments de E et bouge ceux de IN- E (qui établit une bijection différente de l'identité sur IN - E) ce qui est toujours possible si le complémentaire de E n'est pas un singleton.

On a construit ainsi $\text{[math]}$ bijections, le cardinal cherché est donc supérieur ou égal à $\text{[math]}$ .

cqfd.

**acx01b** · 08/09/2010, 21h47

oups pardon j'étais mal réveillé, le cardinal de $\text{[math]}$ est évidemment $\text{[math]}$

maintenant comme l'a suggéré Mediat $\text{[math]}$ peut aussi être l'ensemble des suites d'entiers où le nombre de valeurs non nulles est fini ou encore comme le suggère wikipedia l'ensemble des polynomes à coefficients entiers

on établit donc des bijections entre $\text{[math]}$ et $\text{[math]}$

l'ensemble des ces bijections est noté $\text{[math]}$

sur la page http://fr.wikipedia.org/wiki/Ensemble_d%C3%A9nombrable
on peut trouver une définition de la bijection notée B (astuce des blocs) :

De la même façon l'ensemble des suites finies d'entiers (cela revient à prendre des mots sur un alphabet dénombrable), est dénombrable. On peut utiliser pour bloc les suites de longueur plus petite ou égale à n d'entiers plus petits ou égaux à n où n apparait nécessairement si la suite est de longueur strictement inférieure à n-1. Chaque bloc s'ordonne lexicographiquement.

(pour moi cette bijection utilise le même genre d'astuce que lorsque qu'on donne un exemple de bijection entre $\text{[math]}$ et $\text{[math]}$ où on fait des blocs avec la somme p+q)

comme dit précédemment, une bijection complétement différente est la décomposition en facteur premier (c'est une forme "différente" d'astuce), notée P

si j'ai bien compris ce qu'a dit Mediat, on peut avec ça fabriquer un très grand nombre ( $\text{[math]}$ ) de bijections supplémentaires en utilisant une permutation de $\text{[math]}$ . ces bijections sont de la forme "astuce + permutation de $\text{[math]}$ "

comment caractériser les bijections "intéressantes" des autres (compter les astuces) ?
si on se restreint par exemple aux bijections $\text{[math]}$ qui respectent pour tout $\text{[math]}$ et $\text{[math]}$

$\text{[math]}$

où $\text{[math]}$
(pour l'écriture les polynomes sont plus pratiques ici, A est donc l'ensemble des polynomes à coefficients entiers)

les bijections bloc (B) et facteurs premiers (P) respectent bien cet ordre, mais dans la bijection bloc pour chaque bloc on veut aussi interdire d'utiliser un "ordre différent" dans chaque bloc,
pour éviter ça on pourrait aussi imposer que la bijection soit calculable (dans les deux sens) par un programme (déterministe) de longueur finie ?

je pense que ça restreint pas mal le nombre de bijection. est-ce que la bijection P est complétement différente de toutes les autres, est-elle unique en son genre ?

j'espère que j'ai réussi à me faire comprendre

**Médiat** · 08/09/2010, 21h59

J'avoue que je ne sais pas où vous voulez en venir, mais il y a une relation d'équivalence intéressante entre bijections de IN* dans IN :
f est equivalente à g si f(x) != g(x) seulement pour un nombre fini de x.

**acx01b** · 08/09/2010, 22h10

(si un modérateur voulair bien ajouter le signe +, mon ordinateur a refusé de l'ajouter

(C'est fait : Médiat)

$\text{[math]}$

où je veux en venir : je trouverais ça joli si on pouvait trouver une relation d'équivalence entre ces bijections où d'un côté on aurait celles qui utilisent l'astuce des blocs, et de l'autre celles qui utilisent la décomposition en facteur premier

mais pour ça il faut d'abord montrer que toutes les bijections qui respectent par exemple l'inégalité que j'ai mis sont bien soit dans la classe B soit dans les classe P, et qu'il n'y pas d'autres classes ...

**acx01b** · 09/09/2010, 16h53

Bonjour

C'est peut être aussi simple de ne regarder que les bijections qui conservent l'ordre suivant :

soit deux polynomes à coefficients entiers $\text{[math]}$ et $\text{[math]}$ que l'on complète avec des $\text{[math]}$ pour que $\text{[math]}$

si $\text{[math]}$ et $\text{[math]}$
alors $\text{[math]}$

on sait construire deux bijections (B et P) qui respectent cet ordre, combien il y en a-t-il en tout ?

bijections N <-> ensemble des suites finies d'entiers

bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Re : bijections N <-> ensemble des suites finies d'entiers

Discussions similaires

methode des differences finies

quand doit on effectuer la recherche des limite finies et des limites infinies

Propriétés d'un ensemble d'entiers

[topologie] Montrer qu'un ensemble est fermé à l'aide de suites

cardinal du groupe des bijections d'un ensemble dénombrable