Les cardinaux et les ordinaux

 

  1. Introduction
  2. Paradoxe de Godel-Turing
  3. Énumérabilité
  4. Théorie
  5. Les cardinaux
    1. Addition de cardinaux
    2. Produit de cardinaux
  6. Relation d'ordre sur les cardinaux
    1. Auto-plongement
    2. Plongement réciproque
  7. Ensemble infini
  8. Cadinale de l'ensemble des parties
  9. Logique respectueuse de l'indépendance
    1. L'équipotence est une propriété exprimable en logique RI du premier ordre
    2. L'infinitude est une propriété exprimable en logique RI du premier ordre
  10. L'infini
  11. Les ordinaux idiomatiques
  12. Les ensembles bien ordonnés
  13. Isomorphisme
  14. Plongement
  15. Addtion d'ordinaux
  16. Produit d'ordinaux

1) Introduction

Les entiers peuvent se définir comme étant une caractéristique particulière des ensembles finis. Le même processus psychogénétique qui permet à l'enfant de découvrir le concept de nombre entier est à l'oeuvre. Le nombre apparait comme un invariant. Il se distingue du bruit ambient parce qu'il est invariant. Et l'invariance se définie par rapport à un système de transformations, des transformations qui laissent invariante une caractéristique particulière. Et ces transformations doivent être réversibles pour pouvoir répéter l'expérience, car nul science exacte si l'expérience n'est pas répétable. Un système de transformations réversibles s'appelle un groupe.

Classiquement, il n'existe pas d'ensemble de tous les ensembles, à cause du paradoxe de Russel : l'impossibilité de répondre à cette question « L'ensemble des ensembles ne se contenant pas (comme élément), se contient-il ? ». Ce paradoxe démontre que toute définition utilisée comme compréhension pour sélectionner des ensembles, définie un objet plus général qu'un ensemble que nous appelons catégorie, car cette sélection s'exerce dans la catégorie des ensembles. Par contre, si cette sélection s'exerce dans un ensemble, alors elle définie un sous-ensemble qui constitue bien un ensemble. Donc on parlera de la catégorie des ensembles, de la catégorie des ensembles ne se contenant pas. Et on parlera aussi de la catégorie des groupes. Et on habille les catégories d'une copie de la théorie des ensembles avec comme distinction qu'elle s'applique aux catégories et pas aux ensembles. Ainsi la catégorie des ensembles ne se contenant pas, ne se contient pas puisque dans ce cas ce n'est pas un ensemble. Et le procédé se réitère, la catégorie des catégories n'est pas une catégorie mais constitue un autre type d'object mathématique.

La distinction entre ensemble, catégorie, supercatégorie, etc.. découle du paradoxe de Russel ainsi que du paradoxe de Berry : "quel est le plus grand entier définissable en au plus 15 mots français". Il n'y en a pas, car la phrase "Le successeur du plus grand entier définissable en au plus 15 mots" qui ne contient que 12 mots, contredirait toutes propositions. Cela montre qu'une compréhension quelqu'elle soit, doit s'appliquer à un ensemble pour produire un ensemble, à une catégorie pour produire une catégorie, etc.. sinon elle se mord la queue et produit le cas échéant une contradiction.

2) Paradoxe de Godel-Turing

Mais il existe un autre paradoxe d'une autre nature que ceux de Russel et de Berry, qu'est le paradoxe de Godel-Turing qui dévoile le monde du calcul effectif et des programmes informatiques grâce à un modèle de machine qu'est la machine de Turing. Un programme `m` appliqué à une donnée `x` lance un calcul noté `m(x)`. Et ce calcul peut produire au bout d'un temps fini un résultat `y` ce qui se note `m(x)"="y`, ou bien ne jamais s'arrêter et donc ne jamais donner de résultat ce qui se note `m(x)"="oo` l'infini de Turing.

Existe-t-il un programme `P` qui prend en entré un programme `m` et une donnée `x` et qui détermine en un temps fini si le caclul `m(x)` s'arrête ou non en un temps fini ? C'est à dire tel que :

`P(m,x)"="0  <=>  m(x)"="oo`
`P(m,x)"="1  <=>  m(x)"≠"oo`

La réponse à cette question est non. Et c'est Alan Turing qui le démontre par l'absurde en supposant l'existence du programme `P`, en codant les programmes de machine de Turing par des entiers, et en utilisant le procédé de la diagonal de Cantor. On considère l'ensemble `Omega` des programmes prenant en entrée un entier. On fait le choix d'un codage des programmes, c'est à dire le choix d'un programme `G` qui énumère tous les programmes prenant en entrée un entier, c'est à dire qui énumère tous les programmes appartenant à `Omega`.

`Omega = {G(0),G(1),G(2),G(3),...}`

Il est important de bien comprendre la distinction entre un programme et une fonction (mathématique). La fonction ne s'intéresse qu'au résultat, alors que le programme décrit le processus qui atteint à ce résultat. Ainsi deux programmes distincts peuvent calculer une même fonction. C'est pourquoi on utilisera un autre symbole que l'égalité, le symbole `≡`, pour désigner une égalité (de code) entre deux programmes. Étant donné deux programmes `A, B` appartenant à `Omega`, nous avons évidement :

`A"≡"B    =>    AAx"∈"NN, A(x)"="B(x)`

Mais la réciproque n'est en général pas vrai.

Reprenons la suite de notre démonstration. L'étape suivante consiste à construire un programme `F` par le procédé de la diagonale de Cantor, tel que pour tout entier `x`, nous ayons :

`F(x) = P(G(x),x)`

Le programme `F` peut s'écrire comme suit :

`F ≡ x"↦"P(G(x),x)`

Le programme `F` appartient bien à `Omega`, donc il existe `y` tel que `F"≡"G(y)`. Et `y` est calculable, il suffit de les passer en revue en les testant à chaque fois jusqu'à tomber sur le bon `y` vérifiant l'égalité `F "≡" G(y)`, ce qui se fait en un temps fini. Soit un tel entier `y`. Nous avons :

`F≡G(y)`

On constate alors l'existence d'une contradiction :

`F(y)"="0 <=> P(G(y),y)"="0  <=> P(F,y)"="0 <=> F(y)"="oo`

Raisonner c'est calculer, faire une démonstration c'est faire un calcul. L'inexistence du programme `P` se traduit en terme logique par l'inexistence de démonstration pour certain énnoncé. Et donc cela traduit l'inhérente incomplétude des théories finie dès qu'elles sont suffisament complexes pour pouvoir définir tous les programmes d'une machine de Turing, c'est à dire en terme logique, dès qu'elles contiennent l'arithmétique.

3) Énumérabilité

Considérons un sous-ensemble `A` de `NN`.

`A` est dit semi-énumérable s'il existe un programme `F` tel que `A"="F(NN)` ou bien `A"+"{oo}"="F(NN)`. Notez que cette dernière expression signifie que `F` n'est pas d'arrêt sûr. On dit que `F` est un semi-énumérateur de `A`.

`A` est dit énumérable s'il existe un programme `F` tel que `A"="F(NN)`. Notez que cette expression signifie que `F` est d'arrêt sûr. On dit que `F` est un énumérateur de `A`.

`A` est dit énumérable biunivoque s'il est énuméré de façon biunivoque, c'est à dire s'il existe un programme `F` tel que :

`A"="F(NN)`
`AAxAAy, F(x)"="F(y) => x"="y`

On dit alors que `F` est un énumérateur biunivoque de `A`.

`A` est dit énumérable croissant s'il est énuméré dans l'ordre c'est à dire s'il existe un programme `F` tel que :

`A"="F(NN)`
`AAxAAy, x"<"y => F(x)"<"F(y)`

On dit que `F` est un énumérateur croissant de `A`.

Le procédé de programmation appelé "minimalisation" fait qu'il est possible de transformer un semi-énumérateur `F` en un énumérateur `G` et aussi de le transformer en un énumérateur biunivoque et aussi de le transformer en un énumérateur croissant.

Le procédé de minimalisation consiste à lancer un calcul en parallèle dont le parallélisme s'accroit pour couvrir progressivement tout `NN`. Le programme `H` lance le calcul de `F(0),F(1),F(2),...` en parallèle progressivement sans attendre le résultat des calculs `F(x)` lancés, et dès qu'un tel résultat apparait, `H` compare un compteur interne initialisé à zéro avec son entré et si égale retourne le résultat sinon incrémente ce compteur interne et attend qu'un autre résultat surgisse tout en continuant de lancer en parallèle des calculs `F(x"+"1)`. Le procédé de minimalisation nécessite une quantité de mémoire non bornée qui correspond au ruban indéfini de la machine de Turing. Puis on perfectionne ce procédé en ne mémorisant que les résultats distincts, ce qui programme un énumérateur biunivoque. Puis on perfectionne ce procédé en ordonnant les résultats, ce qui programme un énumérateur croissant.

C'est pourquoi il n'y a pas de distinction d'incalculabilité entre ces 4 types d'ensembles {semi-énumérable, énumérable, énumérable biunivoque, énumérable croissant} et qu'ils forment donc qu'un seul type d'ensemble dit simplement énumérable.

A partir de ce principe de calculabilité on définie une notion de quantité d'information comme suit : La quantité d'information d'un ensemble énumérable correspond à la taille minimale du programme qui l'énumère.

4) Théorie logique

Pour définir ce qu'est une théorie au sens général, on se place dans un système formel de déduction, c'est à dire un langage formel d'alphabet fini, et une règle de production. Autrement dit on se place dans une méta-théorie de la déduction qui décrit un langage formel et un procédé de construction des déductions. Et on appelle théorie, un ensemble fini de propositions écrites dans ce langage. Ainsi, il n'y a pas de différence entre proposition et théorie.

La relation de déduction, appelée aussi relation de démontrabilité, `"⊢"` est énumérable puisque elle est définie par un procédé calculatoire. Cela signifie que le graphe de la relation `"⊢"` qui est un sous-ensemble de couple de propositions, est énumérable.

L'expression `A"⊢"B` signifie que la théorie `A` démontre la théorie `B`.

L'ensemble des propositions déductibles d'une théorie `A` se note `"<"A">"` et est énumérable puisque `"⊢"` est énumérable.

L'antilogie la plus simple se note `"⟘"` et signifie le faux. La tautologie la plus simple se note `"⟙"` et signifie le vrai. L'ensemble des propositions se note `"<"⟘">"` puisque elles sont démontrées par le faux, ce principe étant introduit dans la méta-théorie. L'ensemble des tautologies se note `"<"⟙">"`. Et ces deux ensembles sont chacun énumérable.

Une théorie `A` implique une théorie `B` si `A` démontre `B`, et réciproquement si `A⊢B` alors on démontre que `A=>B`. Pourtant ce n'est pas la même chose, car le symbole d'implication `=>` fait partie du langage tandis que le symbole de démontrabilité `⊢` ne fait pas partie du langage, mais du méta-langage qui d'écrire la méta-théorie de la déduction.

Toutes propositions `P` admet une proposition négative `"¬"P` qui obéït au principe d'exclusion `"¬"(P" et ¬"P)` et au principe du tiers exclu `(P" ou ¬"P)`. Ces principes sont préalablement introduit dans la méta-théorie, et ont pour conséquence que les opérateurs logiques coïncident avec les opérateurs booléens.

Donc la proposition `"¬"(A=>B)` que nous écrivons `A⇏B` est équivalente à `A" et ¬"B`. Par contre la méta-proposition `"¬"(A⊢B)` qui se note `A⊬B` signifie autre chose. Elle signifie qu'il n'existe pas de démonstration partant de `A` pour aller à `B`, et si la méta-théorie est complète alors elle signifie que `A⊢"¬"B`.

Nous avons `"⟘" <=> "¬⟙"`. Par symétrie, l'ensemble des antilogies `{"¬"varphi "/" varphi "∈<"⟙">"}` que l'on note `"¬<"⟙">"` est donc également énumérable.

La relation de démonstration est transitive. Ce principe est préalablement introduit dans la méta-théorie. Cela a pour conséquence l'équivalence suivante : `A` démontre `B` si et seulement si tout ce qui est démontrable par `B` est démontrable par `A`. Et dans ce cas, la théorie `A` est plus riche que la théorie `B` :

`"<"⟘">" ⊇ "<"¬B">" ⊇ "<"¬A">" ⊇ "<⟙>"`
`"⟘"   =>   "¬"B   =>   "¬"A   =>   "⟙"`
`"⟘"    =>    A    =>    B    =>    "⟙"`
`"<"⟘">" ⊇ "<"A">" ⊇ "<"B">" ⊇ "<⟙>"`

Si la méta-théorie, tout en étant non contradictoire, est suffisament riche pour pouvoir programmer une machine de Turing, c'est à dire en termes logique si elle contient l'arithmétique, alors le paradoxe de Godel-Turing fait que l'ensemble des propositions indécidables c'est à dire dont on ne peut pas démontrer ni l'affirmation ni la réfutation, n'est pas énumérable. Car sinon tout serait prédictible en temps fini, et en particulier, l'arrêt en un temps fini ou non d'un programme appliqué à une donnée serait prédictible en un temps fini.

C'est pourquoi les propositions ne se répartissent pas entre propositions vrai et propositions fausses, mais entre tautologies, antilogies et indécidables. L'ensemble des propositions se partitionne en 3 parties :

Ensemble
des tautologies
`"<"⟙">"`
Ensemble des propositions
démontrables
Énumérable
Ensemble
des antilogies
`"¬<"⟙">"`
Ensemble des propositions
de négation démontrable
Énumérable
Ensemble
des indécidables
`"<"⟘">"-("<"⟙">"+"¬<"⟙">")`
Ensemble des propositions
à la fois indémontrables
et de négation indémontrable
Non énumérable

L'ensemble des indécidables n'est pas énumérable, et donc n'est pas vide. La méta-théorie est donc incomplète. Voila pourquoi le paradoxe de Godel-Turing dévoile l'inhérente incomplètude des théories.

Etant donné une théorie `A` quelconque. La théorié `A`, qui complète en quelque sorte la méta-théorie dont l'ensemble des déductions est `"<⟙>"`, partitionne de la même façon l'ensemble des propositions en 3 parties :

`"<"A">"`
Ensemble des propostions
affirmable par `A`
Énumérable
`¬"<"A">"`
Ensemble des propostions
réfutable par `A`
Énumérable
`"<"⟘">"-("<"A">"+"¬<"A">")`
Ensemble des propositions
indécidables par `A`
Non énumérable

`"¬<"A">" = {"¬"varphi "/" varphi "∈<"A">"}`

5) Les cardinaux

Un cardinal est une catégorie d'ensembles, dans laquelle les ensembles sont liables deux à deux par des bijections. Et on dit alors qu'ils sont équipotents. Autrement dit, un cardinal est un ensemble à bijection près.

 `"Card"(A)"=""Card"(B)  <=>   EEh "∈" (A"↔"B)`

On note `(A"↔"B)` l'ensemble des bijections de `A` vers `B`.

En considéant l'ensemble comme une structure munie d'aucun opérateur ni prédicat, nous pouvons définir les cardinaux comme une catégorie de structures à isomorphisme près. Deux ensembles sont isomorphes si et seulement si ils sont en bijection. La catégorie des cardinaux est la catégorie des ensembles.

Par exemple le cardinal `3` représente la catégorie des ensembles `E` tel qu'il existe une bijection entre `E` et `{1,2,3}`. Autrement dit, le cardinal `3` représente la catégorie des ensembles qui sont composés d'exactement `3` éléments distincts.

`"Card"(Ø)=0`
`"Card"({a})=1`
`"Card"({a,b})=2`
`"Card"({a,b,c})=3`

Le cardinal `aleph` (prononcez aleph) représente la catégorie des ensembles `A` tel qu'il existe une bijection entre `A` et `NN`. C'est la catégorie des ensembles dénombrables.

`"Card"(NN)=aleph`

5.1) Addition de cardinaux

La somme de deux cardinaux est le cadinal de la somme disjointe des ensembles :

`"Card"(A) + "Card"(B) = "Card"(A"+"B)`

Cette addition est commutative et associative comme l'est l'union disjointe. Par exemple, on remarque qu'il existe une bijection de `NN` vers `NN"+"{a,b,c}`, donc le cadinal de `NN` augmenté de `3` est encore égale au cardinal de `NN`.

`aleph + 1 = aleph`
`aleph + 2 = aleph`
`aleph + 3 = aleph`

On note `NN + NN`, l'union disjointe de `NN` et d'une copie de `NN` disjointe de `NN`. On remarque qu'il existe une bijection de `NN` vers `NN+NN`. Donc le cardinal de `NN` ajouté au cardinal de `NN` est encore égale au cardinal de `NN`.

`aleph + aleph = aleph`
`aleph + aleph + aleph = aleph`

5.2) Produit de cardinaux

On définie le produit sur les cardinaux comme suit : Étant donné deux ensembles `A` et `B`. Le cardinal de `A` multiplié par le cardinal de `B` est défini comme étant le cardinal de `A"×"B`.

`"Card"(A) + "Card"(B) = "Card"(A"×"B)`

Ce produit est commutatif et associatif (principe du n-uplet aplati) comme l'est le produit d'ensembles. Par exemple, on remarque qu'il existe une bijection de `NN` vers `NN"×"{a,b,c}`. Donc le cardinal de `NN` multiplié par `3` est encore égale au cardinal de `NN`.

`Ø"×"NN = Ø` `0aleph = 0`
`{a}"×"NN` est équipotent à `NN` `1aleph = aleph`
`{a,b}"×"NN` est équipotent à `NN` `2aleph = aleph"+"aleph"= aleph`
`{a,b,c}"×"NN` est équipotent à `NN` `3aleph = aleph"+"aleph"+"aleph=aleph`

On remarque qu'il existe une bijection de `NN` vers `NN"×"NN`. Donc le cardinal `NN` multiplié par le cardinal de `NN` est encore égale au cardinal de `NN`.

`NN"×"NN` est équipotent à `NN` `alephaleph = aleph`
`NN"×"NN"×"NN` est équipotent à `NN` `alephalephaleph = aleph`

6) Relation d'ordre sur les cardinaux

L'ensemble des bijections de `A` vers `B` se note `(A"↔"B)`. L'ensemble des injections de `A` dans `B` se note `(A"↪"B)`. On remarque que `A` se plonge dans `B` si et seulement si il existe une partie de `B` qui est en bijection avec `A`. Nous avons :

`(EE f "∈" (A"↪"B))  <=>  EEX"⊆"B, EE h "∈" (A"↔"X)`

On définie une relation d'ordre partielle sur les cardinaux comme suit : Etant donné deux ensembles `A` et `B`, le cardinal de `A` est inférieur ou égal au cardinal de `B` si et seulement si il existe une injection de `A` dans `B`.

`"Card"(A)"⩽""Card"(B) <=>  EE f "∈" (A"↪"B)`

On note `(A"↪"B)` l'ensemble des injections de `A` dans `B`.

Cette relation est bien réflexive et transitive, reste à montrer qu'elle est antisymétrique pour que cela soit une relation d'ordre, comme annoncé. Autrement dit, il convient de démontrer :

`((EE f "∈" (A"↪"B)) , (EE g "∈" (B"↪"A)))  =>  "Card"(A)"=""Card"(B)`

C'est à dire :

`((EE f "∈" (A"↪"B)) , (EE g "∈" (B"↪"A)))  =>  (EEh "∈" (A"↔"B))`

C'est à dire :

`((EEY"⊆"B", "EE f "∈" (A"↔"Y)), (EEX"⊆"A", "EE g "∈" (B"↔"X)))  =>  (EEh "∈" (A"↔"B))`

6.1) Auto-plongement

On commence par démontrer que si un ensemble `A` est en bijection avec une de ses parties, alors il est en bijection avec toute partie qui la contient. Considérons une partition quelconque `A "=" B"+"C"+"D`. Supposons qu'il existe une bijection `f` de `A` vers `B`. Il nous faut démontrer qu'il existe une bijection de `A` vers `B"+"C`. Et on va le faire en la construisant.

Considérons alors l'ensemble `Omega` suivant :

`Omega = Duuf(D)uuf^2(D)uu...uuf^n(D)uu...`    

`Omega = sum_(n in N)f^n(D)`

On remarque que `Omega` est disjoint de `C`, que `f(Omega)` est disjoint de `D` , que `f(Omega)"="Omega"-"D`, et que la bijection `f` restreinte à `Omega` est une bijection de `Omega` vers `Omega"-"D` :

`f_(|Omega) in (Omega "↔" (Omega"-"D))`

On considère alors la bijection suivante, l'identité restreinte à `A"-"Omega` :

`"id"_(|A-Omega) in ((A"-"Omega) "↔" (A"-"Omega))`

Ces deux bijections sont disjointes. La somme des deux bijections forment une bijection de `Omega "+" (A"-"Omega)` vers `(Omega"-"D) "+" (A"-"Omega)` c'est à dire de `A` vers `A"-"D`, c'est à dire de `A` vers `B"+"C`.

`(f_(|Omega) + id_(|A-Omega)) in (A"↔"(B"+"C))`

Concrètement, on construit cette bijection de `A` vers `B"+"C` comme suit : Si `x"∈"Omega` alors sont image est `f(x)`, et si `x"∉"Omega` alors son image est `x`.

6.2) Plongement réciproque

On considère deux plongements :

`f "∈" (A"↪"B)`

`g "∈" (B"↪"A)`

Donc `g"∘"f "∈" (A"↪"A)`  et nous avons `(g"∘"f)(A) sube g(B) sube A`

Donc d'après cet auto-plongement il existe une bijection `h` de `A` vers `g(B)` qui est égale à :

`h = (g"∘"f)_(|Omega) + id_(|A-Omega)`

`Omega = sum_(n in NN) (g"∘"f)^n(A-g(B))`

Et donc il existe une bijection de `A` vers `B` qui est `g^-1"∘"h`

7) Ensemble infini

Un ensemble est infini, si et seulement s'il contient une infinité d'éléments. Cela signifie que l'on peut y extraire une infinité d'éléments distincts à l'aide d'un énumérateur, et donc cela signifie qu'il existe un plongement de `NN` dans l'ensemble en question.

`A " infini"   <=>   (EE f "∈"(NN"↪"A))`

Cette définition fait que le plus petit des cardinaux infini est `aleph`. Tout les autres cadinaux infinis sont nécessairement comparable à `aleph` et sont plus grand que `aleph`.

Dedekind propose une autre définition de l'ensemble infini, qui ne fait pas intervenir `NN`. Un ensemble est infini si et seulement si il se plonge en lui-même de façon stricte :

`A " infini"   <=>   (EE X "⊂"A, EEf "∈" (A"↔"X))`

Où le symbole `"⊂"` signifie une inclusion stricte c'est à dire que l'expression `X"⊂"A` est équivalente à l'expression `X"⊆"A" et "X"≠"A`.

Il convient de démontrer qu'il s'agit là, de la même définition. Considérons un plongement `f` de `NN` dans `A`. Soit c'est une bijection, et comme `NN` se plonge en lui-même de façon stricte, il en est de même pour `A`. Soit c'est un plongement strict, et alors il est facile de construire un plongement de `A` dans lui-même de façon stricte. Voici comment : Si `x` appartient à `f(NN)` on choisie comme image `f(f^-1(x)"+"1)` et si `x` appartient à `A"-"f(NN)`, on choisie comme image `x` :

`"id"_(|A-f(NN))+(f"∘"(x↦x"+"1)"∘"f^-1)_(|f(NN))`

Réciproquement. Considérons un plongement `g` de `A` dans lui-même avec `g(A)"≠"A`. Donc il existe au moins un élément `x` appartenant à `A"-"g(A)`. Alors il est facile de construire un plongement de `NN` dans `A` : on assosie `x` à `0`, puis `g(x)` à `1`, puis `g^2(x)` à `2`, etc.. Cela forme l'application suivante :

`(n↦g^n(x))`

Les éléments `x,g(x),g^2(x),...,g^n(x),...` sont forcement distincts deux à deux car nous avons :

`x∈A"-"g(A)`
`g(x)∈g(A"-"g(A))`
`g^2(x)∈g^2(A"-"g(A))`
`...`
`g^n(x)∈g^n(A"-"g(A))`

Et comme `g` est injectif, nous avons les règles suivantes :

`AA(X,Y)"∈"ccP(A)^2`
       `g(X"+"Y) = g(X)"+"g(Y)`
       `g(X"-"Z) = g(X)"-"g(Z)`

`AAn"∈"NN, g^n" injectif"`

donc :

       `g^n(x)∈g^n(A) - g^(n+1)(A)`

Alors puisque `x,g(x),g^2(x),...,g^n(x),...` distincts, on en conclue que `(n↦g^n(x))` est une injection.

8) Cardinal de l'ensemble des parties

Étant donné un ensemble quelconque `A`, l'ensemble des parties de `A` se note `ccP(A)`. On va démontrer qu'en toute circonstance `ccP(A)` possède un cardinal strictement plus grand que `A`.

On remarque que `A` se plonge dans `ccP(A)` avec l'injection `x|->{x}`, ce qui prouve que le cardinal de `A` est plus petit ou égale au cardinal de `ccP(A)`. Et on démontre par l'absurde qu'il n'existe pas de bijection de `A` vers `ccP(A)` comme suit :

Supposons qu'il exise une bijection `f : A-> ccP(A)`.

On défini l'ensemble des éléments x qui n'appartiennent pas à `f(x)`:

`B = {x "∈" A" / " x"∉" f(x)}`

`B` est un élément de `ccP(A)`. Considérons son antécédent `b` via `f`. Nous avons `f(b) = B`. Il apparaît alors une contradiction :

Ce qui prouve qu'il n'existe pas de bijection entre `A` et `ccP(A)` et comme nous avons une injection de `A` vers `ccP(A)`, nous avons :

`"Card"(A) < "Card"(ccP(A))`

Ainsi nous avons un moyen de construire des ensembles de cardinaux infinis toujours strictement plus grand. Et en particulier le cardinal de `ccP(NN)` est strictement plus grand que `aleph`. Autrement dit `ccP(NN)` n'est pas dénombrable. On note son cardinal par `c`, et il est appelé la "puissance du continu".

9) Logique respectueuse de l'indépendance

La logique respectueuse de l'indépendance (RI), de terme anglophone « Logical Independence-Friendly » (IF), est une extension de la logique standart du premier ordre, qui a été conçue en 1989 par Jaakko Hintikka, logicien et philosophe finlandais (1929 Vantaa - 2015 Porvoo) et Gabriel Sandu, logicien et philosophe finlandais, professeur de philosophie théorétique à l'université de Helsinki.

On utilise soit les quantificateurs de Henkin, ou soit une notation explicitant les dépendances. Par exemple :

Notation utilisant les quantificateurs de Henkin
`AAx EEu AAy (EEv"/"AAx), P(x,u,y,v)`
Notation explicitant les dépendances exlicites
`AAxEEu(x)AAyEEv(y), P(x,u,y,v)`
Forme skolèmisée en notation classique `EEu"(.)" EEv"(.)" AAx AAy, P(x,u(x),y,v(y))`
Négation de la forme skolèmisée en notation classique
`AAu"(.)" AAv"(.)" EEx EEy, P(x,u(x),y,v(y))`

Cette proposition signifie littéralement : « Quelques soit `x`, il existe `u`, quelque soit `y`, il existe `v` indépendament de `x` tel que `P(x,u,y,v)` ».

La logique RI du premier ordre étend la logique classique du premier ordre, sans atteindre complètement la logique du second ordre.

9.1) L'équipotence est une propriété exprimable en logique RI du premier ordre

L'équipotence de deux ensembles `A` et `B` est définie par :

`AAxAAy(EEtta"/"AAx)(EEttb"/"AAy), (((x "∈" A) => (ttb"∈"B)),((y"∈"B)=>(tta"∈"A)),((ttb"="y)<=>(tta"="x)))`

Ce qui signifie littéralement « Quelques soit `x`,`y`, il existe `a` indépendant de `x`, et il existe `b` indépendant de `y` tels que si `x` appartient à `A` alors `b` appartient à `B`, et si `y` appartient à `B` alors `a` appartient à `A`, et si `b"="y` alors `a"="x` », et si `a"="x` alors `b"="y` ». Néanmoins, c'est bien la forme skolémisée qui nous sera la plus familière :

La forme skolèmisée est :

`EEf"(.)"EEg"(.)"AAxAAy, (((x "∈" A) => (f(x)"∈"B)),((y"∈"B)=>(g(y)"∈"A)),((f(x)"="y)<=>(g(y)"="x)))`

Ce qui signifie littéralement « Il existe deux applications `f` et `g` telles que quelques soit `x,y`, si `x` appartient `A` alors `f(x)` appartient à `B`, et si `y` appartient `B` alors `g(y)` appartient à `A`, et si `f(x)"="y` alors `g(y)"="x`, et si `g(y)"="x` alors `f(x)"="y` ». Autrement dit, il existe une application de `A"→"B` et une application de `B"→"A`, qui sont inverses l'une de l'autre.

9.2) L'infinitude est une propriété exprimable en logique RI du premier ordre

L'infinitude d'un ensemble `A` est défini par :

`EEttcAAxAAy(EEtta"/"AAy)(EEttb"/"AAx), ((ttc"∈" A),(tta"≠"ttc),((x "∈" A) => (tta"∈"A)),((tta"="ttb)=>(x"="y)))`

La forme skolèmisée est :

`EEttcEEf"(.)"AAxAAy, ((ttc"∈" A),(f(x)"≠"ttc),((x "∈" A) => (f(x)"∈"A)),((f(x)"="f(y))=>(x"="y)))`

Ce qui signifie littéralement « Il existe un élément `c` appartenant à `A`, et il existe une applications `f` telles que quelques soit `x,y`, on a `f(x)"≠"ttc`, et si `x` appartient `A` alors `f(x)` appartient à `A`, et si `f(x)"="f(y)` alors `x"="y`. Autrement dit, il existe un élément `c` de `A`, et il exsite une injection de `A"↪"A"-"{c}`.

10) L'infini

Lorsque l'on explore les ensembles infinis, la théorie des ensembles devient vite incapable de répondre à de nombreuses questions à cause de son inhérente incomplétude. Délors, on la complète de différentes façons. C'est pourquoi il existe une multitude de théories des ensembles toutes autant cohérentes les une que les autres, autant que l'arithmétique peut l'être. Le choix de la théorie des ensembles détermine la signification profonde de ce qu'est un ensemble infini, et même, ce qu'est un ensemble, dans ses éventuelles définitions récurcives. Il s'agit donc avant tout d'un choix politique.

Avec les seuls axiomes minimaux communément admis, il n'est pas possible de démontrer que les cardinaux sont toujours comparables. C'est à dire, étant donné deux ensembles `A` et `B`. On ne peut pas démontrer qu'il existe toujours, soit au moins une injection de `A` dans `B`, ou au moins une injection de `B` dans `A`, simplement par faute de moyen de construction et de définition.

Se peut-il qu'il existe deux ensembles `A` et `B` tels que :

`(A"↪"B)=Ø`
`(B"↪"A)=Ø`

Dans certaine théorie des ensembles cette propriété est démontrable, dans d'autres elle est indécidable, et dans d'autre encore sa négation est démontrable.

En physique, on est amené à concevoir des grandeurs infiniment petites et des grandeurs infiniment grandes de différents ordres qui complètent ainsi l'ensemble des grandeurs. Comment donner un sens mathématique exacte à ces notions d'infini qui sont toujours comparables deux à deux, sans risquer de se mettre des oeillères ? On scinde le problème en deux, l'infiniment petit et l'infiniment grand. Et on commence par rechercher les infiniments grands entiers sous forme d'une catégorie.

On cherche donc à construire une catégorie des grandeurs entières pouvant être infinies et au delà c'est à dire transfinies. Elles sera appelée la catégorie des ordinaux. Et on souhaite que cette catégorie obéisse à 3 règles :

Et il y a plusieurs voix de recherche possibles. Soit on reste dans la théorie des ensembles et on cherche par le haut en tâtonnant, une catégorie d'ensembles ayant ces 3 propriétés. Soit on se détache de la théorie des ensembles, et on utilise la seul logique pour construire par le bas une structure des ordinaux. Puis il y a les puristes qui définissent les structures à la lettre, selon le sens de notre langue, sans se préoccuper de savoir si la structure résultat possède des propriétés intéresssantes ou pas.

Méthode par le haut :

Les caractèristiques des ensembles que nous allons retenir vont déterminer le comportement de leur catégorie. Classiquement, on choisie comme représentation des ordinaux, les ensembles bien ordonnées, c'est à dire des ensembles munie d'une relation d'ordre totale et tel que tout sous-ensemble non vide possède un élément minimal. Cette condition est quand même extrêmement forte !. C'est pourquoi, il est certainement possible de définir des ordinaux plus généraux, avec une condition plus faible que celle du bon ordre.

Méthode par le bas :

On considère une structure possédant ces trois propriétées :

`S = ("<"0, s"(.)>", ⩽ )" / "{`
       `"⩽ est une relation d'ordre totale",`
       `0 " est minimal pour ⩽" ,`
       `s " est l'opérateur successeur direct pour ⩽"`
`}`

Cette structure libre représente les entiers naturels, mais muni seulement d'une relation d'ordre totale `⩽` , d'un plus petit élément `0`, et d'un opérateur successeur direct `s"(.)"`. Et on s'intéresse à toutes les extensions élémentaires qu'il est possible de faire sur cette structure.

Définition des puristes :

Il existe une autre définition des ordinaux plus terre-à-terre, dites idiomatiques, qu'est la catégorie des ensembles totalement ordonnées possèdant un élément minimum et un opérateur successeur direct définie partout sauf pour l'éventuel élément maximum. Autrement dit, un ordinal idiomatique est un ensemble totalement ordonné avec un élément minimum et un opérateur successeur direct définie partout sauf pour l'éventuel élément maximum, à isomorphime près, c'est à dire à bijection près respectant l'ordre, l'élément minimal, l'éventuel élément maximum, et l'opérateur successeur directe. Mais avec cette définition, il n'est pas garantie que les ordinaux soient tous comparables.

11) Ensemble bien ordonné

L'ensemble des parties non vides de `E` est noté `ccP_(">"0)(E)`.

Un ensemble bien ordonné est un ensemble `E` munie d'une relation d'ordre totale `"⩽"` tel que tout sous-ensemble non vide possède un élément minimal. On remarquera que cet élément minimal est nécessairement unique. On dit que `(E,"⩽")` est un ensemble bien ordonné, et cela s'écrit formellement comme suit :

`AA A "∈"ccP_(">"0)(E),EEa"∈"A,AAb"∈"A,`
`AA(x,y,z)"∈"E^3,`

`x"⩽"x`
`"⩽"` est reflexive
`"⩽"` est une
 relation d'ordre
`x"⩽"y ∧ y"⩽"x => x"="y`
`"⩽"` est antisymétrique
`x"⩽"y ∧ y"⩽"z => x"⩽"z`
`"⩽"` est transitive
`x"⩽"y ∨ y"⩽"x`
`"⩽"` est totale
`a"⩽"b`
`a` est l'élément minimum de `A`

On veut pouvoir définir une fonction de `ccP_(">"0)(E)->E` qui associe à chaque partie non vide de `E`, son élément minimum. Mais, dés que l'on manipule des objets de taille infinie, il convient de formaliser précisement les axiomes qui nous permettent de faire cette manipulation, de faire ce raisonnement, car le caractère infini rend non trivial toutes les moindres transformations.

L'axiome qui permet de construire cette fonction est « l'axiome du choix unique », appelé aussi « l'axiome de définition d'une application » qui dit textuellement :

S'il existe une relation `R"(.,.)"` de `A` vers `B` définissable c'est à dire qui peut s'écrire dans le langage prédicatif en cours, et si cette relation est une fonction c'est à dire qui satisfait `AAx"∈"A, EE!b, R(a,b)`, alors il existe une fonction qui produit cette image `b` pour chaque élément `a` de l'ensemble `A` et qui se définit en appliquant cette axiome.

Notez que l'expression `EE!x, P(x)` signifie textuellement qu'il existe un unique `x` tel que `P(x)`, c'est à dire que:

`EE!x, P(x)  <=>  EEx, P(x) "et" AAy, P(y) => (y"="x)`

L'existence d'une relation `EER"(.,.)"` définissable, signifie qu'il existe une définition de cette relation `R"(.,.)"` dans le langage prédicatif en cours. Cela n'est pas si restrictif que cela car il est toujours possible d'ajouter au langage prédicatif un nouveaux prédicat générateur `R"(.,.)"` , rendant de faite `R` définissable, sans que nous ayons posé aucune condition sur ce prédicat, seul le langage prédicatif c'est agrandit ainsi que le pouvoir d'expression du langage prédicatf en cours.

Cet axiome se note formellement comme suit :

Axiome du choix unique :
`AA "R(.,.)", (AAx,EE!y,R(x,y) )  =>  EEm"(.)",AAx,R(x,m(x))`
Axiome de définition d'une application :

Par contre la définitiopn de la fonction `m` ainsi produite n'a pas encore d'écriture directe. L'écriture directe pourrait être `m="fonction"(R)` car ils ont le même graphe, et l'un est un opérateur unaire, et l'autre est un prédicat binaire. Le méta-opérateur `"fonction"` transformerait ainsi une relation fonctionnelle de `A` vers `B` en un opérateur de `A` dans `B`.

La réciproque ne pose pas de difficulté, car étant donné une fonction `m"(.)"`, on peut toujours définir une relation comme suit : `R(x,y) <=> (y"="m(x))`.

Avec cet axiome, nous pouvons déduire que si `(E,"⩽")` est un ensemble bien ordonné, alors il existe une fonction `m` de `ccP_(">"0)(E)->E` qui associe à chaque partie non vide de `E` l'élément minimum. Et cela se note formellement comme suit :

`(E,"⩽") "bien ordonné"   =>   EEm"(.)", AAA "∈"ccP_(">"0)(E), AAa "∈" A,  m(A)"∈"E "et"  m(A)"⩽"a`

On définit la relation suivante :

`R (A,a)   =   a "∈"A  "et"  AAx"∈"A, a"⩽"x`

Cette relation est bien fonctionnelle. Puis on définit l'opérateur comme suit :

`m = "fonction" (R)`

---- 17 février 2019 ----

 

 

 

 

 

 

 

 

 

Cette dernière condition est identique à la propriété qu'il n'existe pas de suites infinies d'éléments strictement décroissante commençant par cet élément. Cette condition est quand même extrêmement forte !. C'est pourquoi, il est certainement possible de définir des ordinaux plus généraux, avec une condition plus faible que celle du bon ordre.

 

 

11) Les ordinaux

Un ordinal est une catégorie d'ensembles totalement ordonnés avec un élément minimum et une fonction successeur direct définie partout sauf pour l'éventuel élément maximum, dans laquelle les ensembles sont liables deux à deux par des isomorphismes c'est à dire des bijections respectant l'ordre, l'élément minimum et l'opérateur successeur directe.

Un ordinal idiomatique est un ensemble totalement ordonné avec un élément minimum et un opérateur successeur directe définie partout sauf pour l'éventuel élément maximum, à isomorphisme près. Il y a donc deux types d'ordinaux, ceux avec un élément maximum, noté `1`, et ceux sans élément maximum.

  `(A,"⩽", 0, 1, s(A"-"{1})) " ensemble totalement ordonné avec élément minimum "0" élément maximum "1" et successeur directe "s"(.)"`  
  `(B,"⩽", 0, 1, s(B"-"{1})) " ensemble totalement ordonné avec élément minimum "0" élément maximum "1" et successeur directe "s"(.)"`  
  `"Ord"(A)"=""Ord"(B)   <=>   ((EEh "∈" (A"↔"B)), (AAxAAy‚ x"⩽"y <=> h(x)"⩽"h(y)), (h(0)=0), (h(1)=1), (AAx‚ h(s(x))=s(h(x))))`  

 

---- 15 février 2019 ----

  `(A,"⩽", 0, s"(.)") " ensemble totalement ordonné avec élément minimum 0 et successeur directe s(.)"`  
  `(B,"⩽", 0, s"(.)") " ensemble totalement ordonné avec élément minimum 0 et successeur directe s(.)"`  
  `"Ord"(A)"=""Ord"(B)   <=>   ((EEh "∈" (A"↔"B)), (AAxAAy‚ x"⩽"y <=> h(x)"⩽"h(y)), (h(0)=0), (AAx‚ h(s(x))=s(h(x))))`  

Notez que dans cette expression on utilise l'inférence de type. Ainsi la fonction `s"(.)"` est celle de la structure `A` si elle utilise comme argument un élément typé comme apartenant à `A`, et elle est celle de la structure `B` si elle utilise comme argument un élément typé comme apartenant à `B`. La variable `x` évolue dans un domaine restreint à l'ensemble des éléments de `A` si elle est utilisé comme argument de `h"(.)"` et elle diffère de l'élément maximal si elle est utilisé comme argument de `s"(.)"`. L'élément `0` est celui de la structure `A` si il est utilisé comme argument de `h"(.)"`, et il est celui de la structure `B` si il est égale à une image de `h"(.)"`. Et dans la dernière expressions  `h(s(x))=s(h(x))`, l'inférence de type entraine que `x` est restreint à un domaine tel que `x in Dép(h)`, c'est à dire `x in A`, et tel que `h(x)` n'est pas maximum et tel que `x` n'est pas maximum.

12) Les ensembles servant d'ordinaux

Il convient de définir ce qu'est un ensemble pouvant servir d'ordinal. C'est d'abord un ensemble munie d'une relation d'ordre totale, que l'on note `"⩽"`. On ajoute comme propriété qu'il doit posséder un élément minimum, que l'on note `0`. Puis on ajoute la propriétété qu'il possède une fonction successeur directe `s` définie sur tous les éléments `x` autre que l'éventuelle élément maximum.

Le qualificatif directe signifie que pour tout élément `x` qui n'est pas l'éventuel élément maximum, nous avons `x"<"s(x)`, et il n'existe pas d'élément `y` pouvant s'insérer comme suit `x"<"y"<"s(x)`.

On distingue donc à première vue deux sortes d'ordinaux ; ceux qui ont un élément maximum et ceux qui n'en ont pas. Mais, à l'aide du mécanisme d'inférence de type, on veut pouvoir définir ces deux sortes d'ensemble en une même structure.

 

---- 14 février 2019 ----

 



Dominique Mabboux-Stromberg