Les cardinaux et les ordinaux

 

  1. Introduction
  2. Paradoxe de Godel-Turing
  3. Énumérabilité
  4. Décidabilité
  5. Théorie
  6. Les cardinaux
    1. Addition de cardinaux
    2. Produit de cardinaux
  7. Relation d'ordre sur les cardinaux
    1. Auto-plongement
    2. Plongement réciproque
  8. Ensemble infini
  9. Cadinale de l'ensemble des parties
  10. 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
  11. L'infini
  12. Les ordinaux idiomatiques
  13. Les ensembles bien ordonnés
  14. Isomorphisme
  15. Plongement
  16. Addtion d'ordinaux
  17. 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. 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 une contradiction.

Mais il existe un autre paradoxe qui n'est pas résolu par cette distinction. C'est le 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 suivante : "Le successeur du plus grand entier définissable en au plus 15 mots", qui ne contient que 12 mots, contredirait toute proposition de réponse. La contradiction se trouve dans la prémisse de la question qui engendre la contradiction.

2) Paradoxe de Godel-Turing

Mais il existe un autre paradoxe d'une autre nature que ceux de Russel et de Berry, que j'appellerai le paradoxe de Godel-Turing, et 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ée 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 et retournant comme résultat un entier ou l'infini de turing. On fait le choix d'un codage des programmes, c'est à dire le choix d'un programme `G` 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 appartenant à `Omega` et une fonction mathématique de `NN->NNuu{oo}`. 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 tels 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 variables désignant de tels programmes. Étant donné deux tels 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` prend en entrée un entier et retourne comme résultat un entier. Donc il appartient bien à `Omega`. Donc il existe `y` tel que `F"≡"G(y)`. L'entier `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 trancher certain énnoncé. Et donc cela traduit l'inhérente incomplétude des théories finies dès qu'elles sont suffisament complexes pour pouvoir implémenter 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 si et seulement 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 si et seulement 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 si et seulement s'il est énuméré de façon biunivoque, c'est à dire si et seulement s'il existe un programme `F` tel que `A"="F(NN)` et que quelque soit deux entiers `x,y` nous ayons `x"≠"y => F(x)"≠"F(y)`. On dit alors que `F` est un énumérateur biunivoque de `A`.

Le procédé de programmation appelé "minimisation" 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. Ce procédé consiste à lancer un calcul en parallèle dont le parallélisme s'accroit indéfiniment. Cela nécessite une quantité de mémoire non bornée qui correspond au ruban indéfini de la machine de Turing.

On 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 précédement et on retourne les résultats dès qu'ils apparaissent.

`n":="0`
Répéter indéfiniment {
    Lancer le calcul `F(n)` en parallèle
    Si un des cacluls en parallèle s'arrète et donne une réponse `y` alors {
        émettre sur la sortie l'entier `y`
    }
    `n":="n"+"1`
}

On programme ainsi un processus qui va fournire une liste indéfinie d'entiers non nécessairement distincts mais qui à la fin des temps couvrira l'ensemble `A`.

C'est pourquoi, si on s'autorise comme moyen de programmation la minimisation, il n'y a pas de distinction de niveau de calculabilité entre les 3 types d'ensembles {semi-énumérable, énumérable, énumérable biunivoque} et qu'ils forment donc qu'un seul type d'ensemble dit simplement énumérable.

A partir de ce principe de calculabilité on peut définir une notion de quantité d'information calculatoire comme suit : La quantité d'information calculatoire d'un ensemble énumérable correspond à la taille minimale du programme qui l'énumère. La quantité d'information calculatoire d'un élément est la taille minimale du calcul qui le produit. Et la quantité d'information calculatoire d'une proposition logique est la taille minimale de ses démonstrations.

Par contre, le complémentaire de l'ensemble `A` que l'on note `"∁"A= NN-A` n'est pas forcement énumérable. En effet, iI n'y a pas de procédé général pour transformer un énumérateur de `A` en un énumérateur du complémentaire de `A`. Car, pour être sûr qu'un élément `x` n'appartiennent pas à `A`, il faut passer en revue l'énumération complète de `A` ce qui demanderait un temps infini.

4) Décidabilité

Étant donné un sous-ensemble `A` de `NN`.

`A` est dit décidable s'il est énumérable et que son complémentaire `"∁"A` est énumérable.

`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)` et quelque soit des entiers `x,y` nous ayons `x"⩽"y => F(x)"⩽"F(y)`. On dit alors que `F` est un énumérateur croissant de `A`. Noter que l'on peut transformer sans difficulté un énumérateur croissant en un énumérateur strictement croissant.

Lorsque `A` est infini, on remarque que tout énumération croissante énumère en même temps son complémentaire. On peut donc construire à partir d'un énumérateur croissant infini, l'énumérateur du complémentaire. Et donc `A` est décidable. Il n'y a pas de distinction d'incalculabilité entre les 2 types d'ensembles énumérable croissant et décidable. Ils forment qu'un seul type d'ensemble dit simplement décidable.

II n'y a pas de procédé général pour transformer un énumérateur en un énumérateur croissant. Et de même, il n'y a pas de procédé général pour transformer un énumérateur en un énumérateur du complément. Car pour être sûr qu'il n'y a pas de résultat plus petit, il faut passer en revue l'énumération complète. Et pour être sûr qu'un élément n'appartient pas à l'ensemble `A`, il faut passer en revue l'énumération complète de `A`.

Conclusion, il existe une distinction de niveau de calculabilité entre ensemble énumérable et ensemble décidable.

5) 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émonstration, c'est à dire dans un langage des propositions énumérable avec une relation de déduction qui est déterminée mécaniquement par le système de démonstration.

On appelle théorie, un ensemble fini de propositions écrites dans ce langage des propositions et qui correpspond à leur conjonction. Ainsi, il n'y a pas de différence entre proposition et théorie.

La relation de déduction `"⊢"` 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. L'ensemble des tautologies se note `"<"⟙">"`. Ces principes sont posés dans le système de démonstration. Et donc ces deux ensembles `"<"⟘">"` et `"<"⟙">"` 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 des proposition tandis que le symbole de démontrabilité `"⊢"` ne fait pas partie du langage des propositions, mais d'un méta-langage qui nous sert à décrire le système de démonstration.

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 posés dans le système de démonstration, 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 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 posé dans le système de démonstration. 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 le langage propositionnelle est suffisament riche et le système de démonstration suffisament puissant pour pouvoir implémenter 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 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. Le système de démonstration est donc incomplet. Voila pourquoi le paradoxe de Godel-Turing dévoile l'inhérente incomplètude des théories finies (et même énumérable).

Etant donné une théorie `A` quelconque. La théorié `A`, qui complète en quelque sorte le système de démonstration 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">"}`

6) 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. Considérons deux ensembles `A` et `B`. On note `(A"↔"B)` l'ensemble des bijections de `A` vers `B`. Les cardinaux de ces deux ensembles sont égaux si et seulement si il existe une bijection de `A` vers `B`.

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

En considérant 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 alors 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`

6.1) Addition de cardinaux

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

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

Cette addition est commutative et associative comme l'est l'union disjointe représentée par le symbole `"+"`. 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`

6.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` `aleph^2 = alephaleph = aleph`
`NN"×"NN"×"NN` est équipotent à `NN` `aleph^3 = alephalephaleph = aleph`

7) 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)`

Une application `f` est identifiée à son graphe `f={(x,y) "/" x"∈Dép"(f) "et" y"="f(x)})`. Ainsi, sous l'hypothèse que `f` est une application de `A"→"B`, nous avons :

`f "∈" (A"↪"B) <=>  f "∈" (A"↔"f(A))`

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)`

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ée. 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))`

7.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"↔"(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`.

7.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`

8) 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`, et que tout les autres cardinaux 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 `a` appartenant à `A"-"g(A)`. Alors il est facile de construire un plongement de `NN` dans `A` : on assosie `a` à `0`, puis `g(a)` à `1`, puis `g^2(a)` à `2`, etc.. Cela forme l'application suivante :

`{n"↦"g^n(a) "/" EEn "∈" NN} `

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

`a∈A"-"g(A)`
`g(a)∈g(A"-"g(A))`
`g^2(a)∈g^2(A"-"g(A))`
`...`
`g^n(a)∈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(a)∈g^n(A) - g^(n+1)(A)`

Alors puisque `a,g(a),g^2(a),...,g^n(a),...` sont distincts, on en conclue que `{n"↦"g^n(a) "/" EEn "∈" NN} ` est une injection de `NN"↪"A`.

9) Cardinal de l'ensemble des parties

Étant donné un ensemble quelconque `A`, l'ensemble des parties de `A` se note `ccP(A)`. On démontre 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".

---- 11 janvier 2020 ----

 

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