Est-ce que ceci peut t'aider:

Merci pour le lien.

pubmeh utilise dans sa deuxième réponse un renvoi à 4.(a).
"Nous déduisons de 4.(a)"

Cela doit être un renvoi à la pièce jointe. Je ne vois pas la pièce jointe. Vous la voyez ?

Je reprends avec cette idée nouvelle et mes notations :

Donc ou . Jusque là, d'accord.

Mais pourquoi ?

Je pense connaître la réponse.
En effet on dispose du théorème de récurrence et c'est facile de voir que les premiers éléments de sont transitifs.

Encore merci.

Pas plus de détails que ça, je pensais juste que ça pouvait te fournir une piste.

Remarque préliminaire: vu la définition que tu donnes à , si alors il existe tel que ou (sinon il y aurait un cycle et donc il n'existerait qu'un nombre fini d'entiers).

Si , on peut supposer sans perte de généralité qu'il existe tel que .

Supposons que . Alors et donc . Absurde, donc et s est injective

(sinon il y aurait un cylce ...).

en fait c'est pas ça. C'est que tout entier doit avoir un successeur issu de 0, par définition, donc n et m ont un ancêtre commun tel que et .

Si on note et alors
1) , sinon on aurait trivialement...
2) est bien un entier non nul tel que ou .

Pour l'ancêtre commun, on peut bien-sûr prendre k = 0.
Le seul  problème que je vois là, c'est qu'on fait de l'arithmétique alors qu'on est en train de définir

Ta démonstration de l'injectivité par la contraposée est très jolie mais elle me semble plus difficile (moins élémentaire). Faut savoir en prérequis ce que signifie la notion d'application composée ( fois où est un entier, i.e un ensemble à construire...) et aussi la notion d'ensemble fini (au sens de la théorie des ensembles encore).

Le "sens direct" ne nécessite que le théorème de récurrence (qui est immédiat à partir de la définition de ) ainsi que les axiomes qui ont permis de définir .  
Saurais-tu détailler ta démonstration en ce sens ? Comment construire précisément ou et par exemple ?

Je vais détailler la mienne:

Lemme. Les éléments de sont transitifs c'est à dire que chacun de leurs éléments en est aussi une partie.

Preuve. Désignons pour la proposition est transitif :

Alors est vraie puisque ne contient aucun élément : l'implication    est vraie pour tout   (entier ou non d'ailleurs).
Soit , fixé. Supposons vraie. Montrons  que est vraie.
Soit . Alors ou .
Dans le premier cas, l'hypothèse de récurrence nous dit que . Et comme de plus, , on a par transitivité .
Dans le deuxième cas, est bien une partie de par définition. Donc   est vraie.
Finalement,  d'après le théorème de récurrence,   est vraie pour tout entier .

Retour à l'injectivité de s

Soit tel que .
Alors .
En particulier, comme , alors par transitivité de l'inclusion .
Donc donc (par définition de l'union et d'un singleton) . Dans les deux cas,   est une partie de i.e .
De même entraîne  . D'où .

Oups :
Dans mon lemme, dans le cas , j'oubliais de mentionner le fait que .

On va utiliser la notation suivante ci-dessous pour éviter d'utiliser des composées de fonctions : désigne l'ensemble des successeurs de l'ensemble k, ie .
Ou bien si cette définition par récurrence te dérange : et pour tout , .
Puis défini comme .
Ce faisant, est défini en termes d'ensembles alors que est notre ensemble d'entiers naturels habituel.

Tant qu'on y est définissons aussi , l'ensemble des prédécesseurs (stricts) de k.
On pourrait aussi le définir comme l'ensemble . Avec cette seconde définition, on voit immédiatement que si et alors . Il s'agit simplement de la transitivité de l'inclusion: . La définition de comme réunion des trivialise quant à elle le fait que 0 est un prédécesseur de tout entier.
Plus généralement, que si , alors   parce que si , on aura donc .

(Par voie de conséquence, si alors également, puisque )
---

Soient deux entiers différents . Montrons que ou .

Supposons au contraire que . D'après ce qui précède, on a à la fois et . Absurde.


Cela montre effectivement que est totalement ordonné.