bon ordre

GG

bonsoir,

un petit exercice tiré de Johnstone, "Notes on logic and set theory", qui paraît tout bête mais qui finalement n'est pas si trivial que ça :

Soient A et B deux ensembles bien ordonnés. On note 0 = min A.
Montrer que la partie F* de A^B des fonctions de B dans A à support fini est bien ordonnée par l'ordre lexicographique inverse, i.e. f < g <=> f(i) < g(i) où i est le plus grand élément de B pour lequel f et g diffèrent.

Je vois bien intuitivement l'(un) argument qui interdit les chaînes descendantes infinies, mais c'est compliqué à formaliser.

Cela inspire-t-il quelqu'un ?

Je viens de me rendre compte que c'est beaucoup plus simple avec un argument direct en montrant que toute partie non vide de F* a un plus petit élément. On peut laisser tomber le problème.

darw

Pour être un bien ordonné, il faudrait déjà que l'ordre en question soit total. C'est à vérifier, mais avec la définition donnée ici, j'ai du mal à ordonner les deux fonctions de {1,2,3,4} dans lui-même :
f(1)=g(1), f(2)=g(2), f(3)=4, g(3) non défini, f(4) non défini, g(4)=4.

PB

g(3) non défini, f(4) non défini

Si f et g ne sont pas bien définies, il est normal d'avoir du mal à les comparer

darw

Ce sont des fonctions à support fini, si B est de cardinal aleph0, je ne vois pas comment faire autrement que de considérer des fonctions partielles...

PB

Je pense qu'elle sont définies partout mais qu'elle valent 0 presque partout où 0=min(A).

jobherzt

J'avais compris la meme chose que PB....

Bruno

Bonjour.

J'opte pour la même position que PB et Jobhertz ; notamment parce que la notation A^B désigne d'ordinaire l'ensemble des applications (donc partout définies) de B vers A.

Bruno

gb

La bonne interprétation de l'ensemble d'applications considérées est effectivement celle qui fait l'objet des messages précédents.

La réponse est, par exemple, ici, pp. 40-41

Ce bon ordre permet de définir une exponentiation des ordinaux, différente de l'exponentiation des cardinausx.

Bruno

Bonjour gb.



Cette exponentielle est définie par récurrence :

$\alpha^0 = 1$ \\
$\alpha^{\beta + 1} = \alpha^\beta * \alpha$ \\
si $\lambda$ est limite, alors $\alpha^\lambda = \sup_{\beta \in \lambda}\alpha^\beta$.

Bruno

GG

oui, ce sont les deux aspects de l'exponentiation des ordinaux. Je n'avais pas mentionné la finalité de l'exercice dans mon premier post !

gb

Bruno,

Mon message n'était peut-être pas très clair.

$A$ est
\begin{itemize}
\item en tant qu'ensemble, de cardinal $\kappa$ ;
\item en tant qu'ensemble bien ordonné, isomorphe à l'ordinal $\alpha$.
\end{itemize}

$B$ est
\begin{itemize}
\item en tant qu'ensemble, de cardinal $\lambda$ ;
\item en tant qu'ensemble bien ordonné, isomorphe à l'ordinal $\beta$.
\end{itemize}

L'ensemble $A^B$ des applications de $B$ dans $A$ est de cardinal $\kappa^\lambda$.
L'ensemble $F^*$ des applications à support fini, muni de l'ordre lexicographique inverse étudié par GG, est isomorphe à l'ordinal $\alpha^\beta$ (ce qu'on peut prendre comme définition de l'exponentiation des ordinaux), mais que, sauf cas de finitude, $F^*$ n'est pas équipotent à $A^B$.

Même si les ordinaux $\alpha$ et $\beta$ sont des cardinaux, $\alpha^\beta$ n'est pas, en général, un cardinal, et l'on a seulement $\mathrm{Card}\,(\alpha^\beta) \leq \kappa^\lambda$ avec de très rares cas d'égalité.

Bruno

Euh... gb, il ne me semble pas avoir dit de gros mot ! J'ai simplement rappelé la définition (purement formelle) par récurrence de l'exponentielle sur la classe des ordinaux. Je n'ai pas du tout prétendu que ton message n'était pas clair.

Disons les choses autrement : la première fois que j'ai vu les ordinaux, c'était dans le "Set theory" de Kuratowski et Mostovski. Ils étaient effectivement introduits comme types de bon ordre avec le même inconvénient que la définition des cardinaux comme représentants de classe d'équipotence et la définition des opérations nécessitait quelques contorsions pour exhiber un bon ordre ad hoc.

Ensuite, j'ai vu la version de Von Neumann ; dans cette version on définit formellement les opérations d'addition, de multiplication et d'exponentiation par récurrence sur la classe des ordinaux. J'ai simplement rappelé cette dernière définition, qui suppose au passage que l'on ait déjà défini l'addition et la multiplication.

Maintenant, si l'exponentielle définie par les considérations de bon ordre est différente de celle définie par récurrence, je rougirais d'avoir perturbé cette discussion.

Bruno

gb

Bruno;

Rassure-toi, tu n'as pas dit de gros mot, et tu n'as pas besoin de te laver la bouche au savon de Marseille.

J'avais dans la tête le fil suivant Définition axiomatique de R et hypotèse du continu, où il avait été question d'exponentiation cardinale, et je voulais profiter de l'occasion pour rappeler la "petite" différence avec l'exponentiation ordinale.

Bruno

O.K. Tout compris.

Bruno

(Brrr, au savon de Marseille, tu es plus dur que Ma Dalton)