Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
Salut
On se place dans ZFC.
On prend $I$ une affirmation indécidable de cette théorie.
On prend $$f \text{ : } \{1\} \rightarrow \{1,2\} \text{ tel que } f(1)=1 \text{ si } I,\ f(1)=2 \text{ si } \text{non}(I)
$$ Alors $f\in \{1,2\}^{\{1\}}$ et n'est pas une fonction classique, non ?
Cordialement.
On se place dans ZFC.
On prend $I$ une affirmation indécidable de cette théorie.
On prend $$f \text{ : } \{1\} \rightarrow \{1,2\} \text{ tel que } f(1)=1 \text{ si } I,\ f(1)=2 \text{ si } \text{non}(I)
$$ Alors $f\in \{1,2\}^{\{1\}}$ et n'est pas une fonction classique, non ?
Cordialement.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Ainsi, si $I$ est indécidable, d'après le théorème de complétude de Gödel, il existe $M,N$ deux modèles de ZFC tels que $M\models I$, $N\models\neg I$. Ainsi, par définition de $f$, on aura $M\models f(1)=1$, $N \models f(1)=2$.
Comme on a l'habitude de pouvoir déterminer par une preuve les valeurs de $f$ lorsque $f$ est si "simple", ça paraît bizarre de se dire que la valeur de $f(1)$ dépende du modèle et ne soit pas déterminable par une preuve, mais ce n'est finalement pas plus bizarre que le fait qu'on ne puisse déterminer "la valeur de vérité" d'une formule (comme $I$, ou encore $f(1)=1$)
I
@Maxtimax : oui, j'ai bien précisé que l'on se plaçait dans la théorie ZFC, et que $I$ est indécidable de cette théorie, se plaçait dans une théorie plus forte, cela revient à changer les règles du jeu en ajoutant des nouvelles, bref ne plus jouer au même jeu, tout en donnant l'impression de toujours jouer au même jeu, c'est ce que l'on appelle "tricher".
Mais après ton interrogation n'est pas inintéressante et je pense qu'il y a plus à dire dessus que ce qu'on dit. Toutes les propositions vont former une catégorie (les flèches sont les implications), et alors certaines propositions « normales » vont être isomorphes à la proposition « vraie », d'autres à la proposition « faux », et pour les autres il va y avoir tout un réseau d'implications alambiqué. Un modèle est alors un foncteur de cette catégorie vers la catégorie formée juste de « vrai » et « faux », fixant « vrai » et « faux ». [Rectification : le foncteur doit être continu et cocontinu.]
@flipflop Je trouve le parallèle que tu fais intéressant, merci pour la remarque.
Histoire de ne pas rester sur des trucs abstraits !
Question très naïve : est ce que la commutativité dans la théorie des groupes est indécidable ?
Laissons cette question en suspens, le tend [temps] d'acquérir le vocabulaire nécessaire pour me faire comprendre, de vous.
Cordialement.
@Shah d'Ock Tu fais fait référence à l'indécidabilité algorithmique ?
Flipflop: en fait le terme approprié serait toujours qu'un énoncé est indépendant d'une théorie. On dit qu'une théorie T est indécidable si le problème D suivant:
Donnée: un énoncé A
Question: est-ce que cet énoncé A est dans la théorie T?
est algorithmiquement indécidable. En particulier, cela implique (si la théorie est récursivement axiomatisée) qu'il y a des énoncés indépendants (sinon l'algorithme consistant, sur l'entrée A, à énumérer toutes les preuves possibles jusqu'à en trouver une dont la conclusion est soit A soit non A, déciderait le problème D). La réciproque n'est pas vraie: il y a des théories incomplètes (ie il y a des énoncés indépendants), mais algorithmiquement décidables.
Par glissement, on dit aussi parfois qu'un énoncé indépendant est indécidable, mais du point de vue de la décidabilité algorithmique tout énoncé est décidable, autrement dit pour tout énoncé A il y a un algorithme qui répond au problème D' suivant:
Entrée: rien du tout
Question: est ce que A est dans T?
L'algorithme en question est... une fonction constante. Évidemment, il y a des cas où on ne peut pas connaître cet algorithme, mais là n'est pas la question.
C'est pourquoi je préfère parler d'indépendance d'un énoncé que de son indécidabilité.