Les cardinaux et les ordinaux
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.
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, ou qui permet de construire une réponse qui engendre une contradiction.
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 calcul `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->NN"∪"{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.
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 si l'ensemble énuméré est infini. 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 fournir une liste indéfinie d'entiers non nécessairement distincts mais qui atteint chaque élément de l'ensemble `A` en un temps fini.
C'est pourquoi, si on s'autorise comme moyen de programmation la minimisation, il n'y a pas de distinction de domaine de calculabilité entre les 3 types d'ensembles infinis {semi-énumérable, énumérable, énumérable biunivoque} et qu'ils forment donc qu'un seul type d'ensemble infini dit simplement, infini et é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 demande un temps infini.
Étant donné un sous-ensemble `A` de `NN`.
`A` est dit décidable s'il est énumérable et que son complémentaire, que l'on note `"¬"A`, est également énumérable. Les ensembles finis sont évidement énumérables.
`A` est dit énumérable croissant s'il est énumérable dans l'ordre par une application croissante de `NN"→"A`. 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`. Notez alors que `A` n'est pas nécessairement infini car la monotonie n'est pas stricte. Notez que si `A` est infini, 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, l'énumérateur du complémentaire. Et donc `A` est décidable. Il n'y a pas de distinction de domaine de calculabilité 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 infini 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 infini 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, ce qui demande un temps infini. 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`, ce qui demande un temps infini.
Conclusion, il existe une distinction de domaine de calculabilité entre ensemble énumérable infini et ensemble décidable infini.
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, qui est énumérable, que l'on munie d'une relation de déduction notée `"⊢"`, qui est déterminée mécaniquement par un système de démonstration.
On appelle théorie, un ensemble fini de propositions écrites dans ce langage des propositions et qui correspond à leur conjonction. Ainsi, il n'y a pas de différence entre une proposition et une 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 toutes 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 => "⟙"`
`"⟘" => 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 vrais et propositions fausses, mais entre tautologies, antilogies et indécidables. L'ensemble des propositions se partitionne en 3 parties :
des tautologies
démontrables
des antilogies
de négation démontrable
des indécidables
à la fois indémontrables
et de négation indémontrable
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.
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 :
affirmable par `A`
réfutable par `A`
indécidables par `A`
où `"¬<"A">" = {"¬"varphi "/" varphi "∈<"A">"}`
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`, autrement dit, si et seulement si l'ensemble `(A"↔"B)` n'est pas vide.
`"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 infinis dénombrables.
`"Card"(NN)=aleph`
La somme de deux cardinaux est le cardinal 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 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`
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 l'ensemble des couples d'éléments `A"×"B = {(a,b) "/" a"∈"A "et" b"∈"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`
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 utilise aussi le terme de plongement pour désigner une injection. 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 :
`(("Card"(A)"⩽""Card"(B) ),( "Card"(A)"⩾""Card"(B) )) => "Card"(A)"=""Card"(B)`
C'est à dire :
`((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))`
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)` :
On considère alors la bijection suivante, l'identité restreinte à `A"-"Omega` :`f"|"_Omega in (Omega "↔" (Omega"-"D))`
`"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`.
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`
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`.
É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 égal 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 ».
On définit la puissance de cardinaux comme suit : Étant donnés deux ensembles `A` et `B`. Le cardinal de `B` élevé à la puissance du cardinal de `A` est défini comme étant le cardinal de l'ensemble des applications de `A"→"B`.
`"Card"(B)^("Card"(A)) = "Card"(A"→"B)`
Lorsque les cardinaux sont finis, l'élèvation à la puissance coïncident avec celle définie sur les entiers. Le cas particulier de `0^0` se résoud en comptant les applications de `Ø"→"Ø`. Et il y en a une, qui est l'application définie par son graphe vide. Ainsi, selon les cardinaux `0^0"="1`.
Etant donné un entier non nul `n`. L'ensemble `sfN^n` est l'ensemble des `n`-uplets d'entiers non nuls. C'est aussi l'ensemble des applications de `{1,2,3,...,n}` vers `sfN`. De la même façon qu'il existe une bijection de `sfN` sur `sfN"×"sfN`, il existe une bijection de `sfN` sur `sfN^n`. Ces ensembles sont donc tous équipotants à `sfN`.
`aleph^n = aleph = "Card"(sfN^n) = "Card"({1,2,...,n}->sfN) = "Card"(sfN)`
Parcontre, l'élévation à une puissance infini d'un cardinal au moins égale à `2` produit un cardinal infini nécessairement plus grand que `aleph`. Car le cardinal de l'ensemble des applications de `A` vers `{0,1}` est égale au cardinal de l'ensemble des parties de `A`.
`"Card"(A"→"{0,1})="Card"(ccP(A))`
On représente une sujection `f` de `A` sur `B` par son graphe `{(a,b) "/" f(a)"="b}` qui est un ensemble de couples.
`f = {(a,b) "/" f(a)"="b}`
Si l'ensemble `A` est muni d'un ordre `"⩽"`, cet ensemble de couples peut être ordonné selon la première composante selon cet ordre. Et un ensemble ordonné peut s'écrire sous forme de liste étendue :
`f = (b_a)_(a in A)` avec `AA a "∈" A, b_a "=" f(a)`
La puissance du continu abuse de son nom. Car la continuité est définissable sans utiliser cette puissance du continu. On définie la continuité dans l'ensemble des nombres rationnels `QQ` qui est un ensemble dénombrable.
La puissance du continu doit s'appeler en faite la puissance de l'incalculable. Les nombres incalculables sont ceux distincts du point de convergence de toute suite rationnelle calculable de cauchy. Une suite rationnelle calculable est une application calculable de `sfN"→"QQ` notée :
`(a_i)_(i "∈" sfN) = (a_1,a_2,a_3,....,a_n,...)`
C'est à dire qu'il existe un programme de calcul de taille finie qui va énumérer cette suite. Et cette suite est dite de Cauchy si et seulement si quelque soit `n "∈" sfN`, il existe un indice `k "∈" sfN` tel que quelque soit `i">"k` et quelque soit `j">"k`, nous ayons toujours `|a_i-a_j|"<"1"/"n`. Notez que l'on utilise `sfN` l'ensemble des entiets strictement positifs.
La puissance de l'incalculable ne nous sert pas. On choisit alors un nouveau paradigme, dit élémentarien, qui se restreint aux seuls objets calculables. Les calculs étant par nature dénombrable, l'ensemble de ces objets est nécessairement dénombrable.
L'ensemble des parties calculables de `sfN`, noté pareillement `ccP(sfN)` est donc dénombrable. Les mêmes notations sont utilisée, seul le paradigme change. Soit on est dans le domaine de l'incalculable..., soit on partage l'approche des élémentariens en ne retenant que ce qui est calculable.
A chaque application `f` calculable de `sfN"→"sfN`, correspond une partie calculable de `sfN` définie comme l'image de `f`. De même, à chaque application `g` calculable de `{0,1}"→"sfN`, correspond une partie calculable de `sfN` définie comme un noyau de `g`.
`ccP(sfN) = {f(sfN) "/" EE f in sfN"→"sfN}\= {g^-1(1) "/" EE g in {0,1}"→"sfN}`
Vous aurez remarqué que cette égalié est valable dans les deux paradigmes, dans le cas des puissances incalculables, et dans le cas dénombrable où les ensembles `ccP(sfN)`, `sfN"→"sfN`, `{0,1}"→"sfN` sont restreints à leur seuls éléments calculables et sont donc dénombrables.
Le théorème de Löwenheim-Skolem affirme que, si une théorie du premier ordre écrite dans un langage mathématique dénombrable est réalisable dans un monde infini, alors elle est réalisable dans un monde dénombrable. C'est pourquoi, en logique du premier ordre, on choisira la solution la plus simple qui consiste à récuser les infinis autres que ceux équipotents à `sfN`, puisqu'ils n'apportent aucune modification sur le caractère de démontrabilité des propositions. Et dans les logiques d'ordre supérieur, on ne peut compter sur aucun fondement..., en dehors du calcul par essence dénombrable.
Le même raisonnement permet de définir la restriction calculable de l'ensemble des applications, qui ne retient que les applications calculables, et qui forme donc un ensemble énumérable.