Inscription / Connexion Nouveau Sujet
Niveau maths sup
Partager :

Bijection sans point fixe

Posté par
Foxdevil
22-08-21 à 20:28

Salut à tous,

Je galère sur une question. Étant donné une bijection f de \N, sans points fixes, prouver que les deux ensembles suivants sont infinis:

A = \{ n \in \N | n > f(n) \} et B = \{ n \in \N | n < f(n) \}.

Si ça peut aider, cette question vient d'un exercice où on a démontré avant que:

- \forall n \in \N, \ f(n) \le n implique f= Id
- \forall n \in \N, \ f(n) \ge n implique f= Id

Posté par
Sylvieg Moderateur
re : Bijection sans point fixe 22-08-21 à 20:52

Bonjour,
Attention, la dernière ligne est fausse car sans doute incomplète.
f(n) = n+1 est un contre exemple.
Peux-tu donner l'énoncé du 1er au dernier mot sans rien y changer ?

Posté par
Foxdevil
re : Bijection sans point fixe 22-08-21 à 20:59

Bonsoir Sylvieg,

f est de bijection de \N (dans \N)...ton application contre-exemple n'est pas surjective, donc n'est pas bonne...

Posté par
Foxdevil
re : Bijection sans point fixe 22-08-21 à 21:00

Pour la modération, mon niveau à moi est master. Mais l'exercice lui est bien de niveau L1/sup...

Posté par
Ulmiere
re : Bijection sans point fixe 22-08-21 à 21:19

Commence par remarquer que si A et B sont finis, A\cup B est fini donc son complémentaire est infini.
Donc il y a une infinité de n tels que n\geqslant f(n) et n\leqslant f(n)

Maintenant il faut montrer que c'est vrai pour tous les n

Posté par
Foxdevil
re : Bijection sans point fixe 22-08-21 à 21:31

Bonsoir Ulmiere,

Maintenant il faut montrer que c'est vrai pour tous les n Je ne suis pas sûr d'avoir bien compris...

D'autant plus que le complémentaire de cette union est vide...

J'ai réussi à montrer que A ou B est nécessairement infini (j'aurais dû le préciser). Que tous les deux sont non-vides (B contient 0 et A contient l'antécédent de 0).

Posté par
verdurin
re : Bijection sans point fixe 22-08-21 à 21:38

Bonsoir,
on peut regarder f^{-1}(A) et f^{-1}(B).

Posté par
Sylvieg Moderateur
re : Bijection sans point fixe 22-08-21 à 23:12

Bonsoir,
Je n'avais pas compris que f était aussi une bijection dans les questions précédentes.
Je répète qu'un énoncé complet est toujours préférable.

Posté par
Foxdevil
re : Bijection sans point fixe 23-08-21 à 05:42

Bonjour,

Sylvieg @ 22-08-2021 à 23:12

Bonsoir,
Je n'avais pas compris que f était aussi une bijection dans les questions précédentes.
Je répète qu'un énoncé complet est toujours préférable.
Effectivement. J'ai réalisé juste après avoir répondu que mon énoncé pouvait être mal compris... désolé!

verdurin @ 22-08-2021 à 21:38

on peut regarder f^{-1}(A) et f^{-1}(B).
Merci pour la proposition. Mais je ne vois pas trop ce qu'on peut dire de plus...

Posté par
Ulmiere
re : Bijection sans point fixe 23-08-21 à 12:04

Puisque tu es déjà à l'étape suivante, c'est effectivement une bonne idée de regarder les images réciproques/directes de A et B

Si n est dans B alors f(n)>n, donc f(n) est strictement plus grand que son image par f^{-1}. Donc f(B_f) \subseteq A_{f^{-1}}, ce qui s'écrit aussi B_f\subseteq f^{-1}(A_{f^{-1}}).
Symétriquement, on a aussi A_f \subseteq f^{-1}(B_{f^{-1}}), mais surtout, en travaillant avec f^{-1} à la place de f, que A_{f^{-1}}\subseteq f(B_f). Or, nous avons déjà vu que f(B_f) \subseteq A_{f^{-1}} au début de ce paragraphe. Donc f(B_f) = A_{f^{-1}}.

Mais tu as déjà montré que au moins un ensemble parmi A_{f^{-1}} et B_{f^{-1}} était infini. Supposons sans perte de généralité que ce soit A. Alors f(B_f) est infini et son image par la bijection f^{-1}, qui n'est autre que B_f est également infinie. Ce qu'il fallait démontrer.

Posté par
Ulmiere
re : Bijection sans point fixe 23-08-21 à 12:10

Il ne reste plus qu'à établir un lien entre B_f et B_{f^{-1}} ou l'équivalent avec des A ou avec des f^{-1} à la place des f

Posté par
Foxdevil
re : Bijection sans point fixe 23-08-21 à 13:14

Merci Ulmiere pour ton aide. C'est une piste que j'avais exploré également, sans succès. Désolé je n'ai pas pu indiquer toutes mes réflexions, car j'y ai réfléchi sur plusieurs jours et un peu dans tous les sens...et impossible de mon point de vue de savoir si je n'ai simplement pas assez poussé l'une de ces pistes...

Le soucis est que justement en avoir un infini ne dit pas lequel pour chacune des bijection.
Pour f ça peut B mais A pour sa réciproque...etc

Je ne vois pas de lien permettant de conclure quant à l'infinité de B de la réciproque à partir de l'infinité du B de f...

Posté par
Foxdevil
re : Bijection sans point fixe 23-08-21 à 13:19

Si le courage m'en prend, je vais peut-être essayer de présenter celles que je pense le plus fructueuses...

Posté par
GBZM
re : Bijection sans point fixe 23-08-21 à 15:41

Bonjour,

On peut raisonner par l'absurde.

Supposons A fini. Ceci veut dire qu'il existe r \in \N tel que pour tout n\geq r on a f(n)\geq n.
Alors f(r)=r (indication : que peut on dire de l'image par f de l'ensemble - de cardinal r - des entiers strictement plus petits que r ?).

Ceci est valable pour toute bijection f.

Posté par
Foxdevil
re : Bijection sans point fixe 24-08-21 à 15:43

Bonjour GBZM,

Merci pour ton aide.

Citation :
Alors f(r)=r (indication : que peut on dire de l'image par f de l'ensemble - de cardinal r - des entiers strictement plus petits que r ?).
J'ai essayé mais je ne vois pas trop...à priori ils peuvent être tant dans A que dans B...

Posté par
GBZM
re : Bijection sans point fixe 24-08-21 à 15:55

Oublie A et B pour le moment.
N'oublie pas que f est une bijection : tout entier est l'image par f d'un entier et un seul.
Tout entier n supérieur ou égal r s'envoie sur un entier supérieur ou égal à n.
Quels entiers vont bien vouloir s'envoyer sur les entiers < r ??

Posté par
Foxdevil
re : Bijection sans point fixe 24-08-21 à 16:07

GBZM @ 24-08-2021 à 15:55


Quels entiers vont bien vouloir s'envoyer sur les entiers < r ??
Des entiers parmi ceux inférieurs à r du coup

Du coup, l'image de [0;r-1] serait [0;r-1]?

Posté par
GBZM
re : Bijection sans point fixe 24-08-21 à 16:44

Tu sembles être sur les rails, je te laisse poursuivre.

Posté par
Foxdevil
re : Bijection sans point fixe 24-08-21 à 17:15

Ok. Je rédige un peu mieux pour ceux qui seraient intéressés et pour clarifier dans ma tête .

Les images des entiers strictement inférieurs à r sont nécessairement des entiers strictement inférieurs à r. Car
- les entiers inférieurs à r strictement admettent tous un antécédent exactement par f (bijection).
- Ces antécédent ne peuvent être les entiers supérieurs à r, car leurs images sont toutes plus grandes que r.

On a bien f([0;r-1]) = [0;r-1]. Mais r ne peut être atteint par des entiers supérieurs à r strictement, car leurs images sont plus grande que r+1. Donc l'antécédent de r est r. Ce qui est absurde...(f sans points fixes)...

Donc A est infinie quelle que soit la bijection, en particulier pour la réciproque de f. Mais B de f a la même cardinalité que A de la réciproque de f. Donc B est aussi infinie...

Posté par
Foxdevil
re : Bijection sans point fixe 24-08-21 à 17:16

GBZM @ 24-08-2021 à 16:44

Tu sembles être sur les rails, je te laisse poursuivre.
Encore un grand merci pour ton aide!

Posté par
GBZM
re : Bijection sans point fixe 24-08-21 à 17:42

Avec plaisir.



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 1561 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 !