Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?

pourexemple · April 2017

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.

Champ-Pot-Lion · April 2017

C'est quoi une « fonction classique » ? Tu ne peux pas montrer d'énoncé de la forme $f(1) = a$, de la même manière que tu ne peux pas montrer d'énoncé du genre $I$ est vrai, ou $I$ est faux. Mais tu peux manipuler cette fonction comme toute les autres. Ce n'est pas pour autant que $f(1) \neq 1$ et $f(1) \neq 2$ comme tu l'insinues peut-être.

Maxtimax · April 2017

Pour aller dans le sens de Champ-Pot-Lion, n'oublie pas que la vérité d'une formule close dépend du modèle dans laquelle elle est interprétée.

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

pourexemple · April 2017

@Champollion : les fonctions classiques sont dans notre cas : u(1)=1 et v(1)=2.
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".

Champ-Pot-Lion · April 2017

Ok, eh bien oui, $f$ est une fonction classique puisqu'elle vérifie $f(1)=1 \lor f(1)=2$. Mais on ne peut prouver ni $f(1)=1$, ni $f(1)=2$, bien qu'on puisse prouver leur disjonction. Ça n'a rien de surprenant comme l'explique bien Maxtimax.

Champ-Pot-Lion · April 2017

Le fait qu'on ne puisse pas prouver $f(1)=1$ ne veut pas dire qu'on peut prouver $f(1)\neq 1$.

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

Champ-Pot-Lion · April 2017

Donc oui, il n'y a pas de « troisième valeur de vérité » qui serait « indécidable », mais il va y avoir tout un réseau de valeurs de vérités. On peut alors avoir $A \implies B$ sans que $B \implies A$, sans que $A$ ni $B$ ne soient décidables, par exemple. (Bon, en fait on a un foncteur (canonique) de notre catégorie vers la catégorie constituée de trois objets « faux », « indécidable » et « vrai », avec « faux implique indécidable » et « indécidable implique vrai ». Donc en quelque sorte si , il y a une troisième valeur « indécidable ». (edit : Ouais bon c'est nul ce que je dis.))

Poirot · April 2017

@pourexemple : visiblement tu confonds théorie et modèle. Travailler dans ZFC ne veut pas dire qu'on en a choisi un modèle (si tant est qu'un tel modèle existe). L'énoncé $f(1)=1$" est indécidable, et si on se place dans un modèle satisfaisant $I$, alors dans ce modèle, $f(1)=1$, c'est tout.

flipflop · April 2017

Ton groupe universel, c'est un peu comme ta catégorie de proposition (un truc, ou y'a de l'ambiguïté) ? Ensuite, tu prends une représentation (un modèle) et là plus d'ambiguïté ?

Champ-Pot-Lion · April 2017

Oui, c'est similaire ! Je n'avais pas remarqué. On a d'ailleurs le même mot : « modèle ».

pourexemple · April 2017

Non, la question est le statut (classique ou non) de la fonction $f$ dans ZFC, c'est à dire pour tout modèle vérifiant ZFC.

Poirot · April 2017

On a déjà répondu. Selon le modèle, la nature de $f$ change. Dans tous les cas, $f$ est une fonction bien définie.

Shah d'Ock · April 2017

J'ai peut-être loupé quelque chose, mais je crois qu'on ne sait toujours pas ce que pourexemple appelle une fonction classique.

Champ-Pot-Lion · April 2017

@pourexemple Tu peux déjà simplifier ta question je pense : est-ce que $I$ est une « proposition classique » ? Ensuite, tout dépend de ce que tu appelles une proposition classique en effet…

@flipflop Je trouve le parallèle que tu fais intéressant, merci pour la remarque.

flipflop · April 2017

Mais j'y connais rien moi (:P)

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 ?

Shah d'Ock · April 2017

Oui au sens ou elle n'est pas prouvable (puisqu'il y a des groupes non commutatifs), ni sa négation (il y a des groupes comlutatifs).

Shah d'Ock · April 2017

Ceci dit, le mot "indecidable" est quelque peu imprécis car il est peu être employé dans différents contextes dans lesquels il n'a pas exactement le même sens. Ici, il serait plus précis de dire qje la commutativité est indépendante de la théorie des groupes.

flipflop · April 2017

Merci Shah d'Ock, pour ma culture dernière question ... Est-ce que tu as un exemple concernant la différence entre indépendante et indécidable ?

pourexemple · April 2017

Salut

Laissons cette question en suspens, le tend [temps] d'acquérir le vocabulaire nécessaire pour me faire comprendre, de vous.

Cordialement.

Champ-Pot-Lion · April 2017

J'ai dit une bêtise. N'importe quel foncteur n'est pas un modèle, il faut qu'il soit continu et cocontinu. Par exemple, on ne peut pas envoyer à la fois une proposition indécidable et son contraire sur vrai.

@Shah d'Ock Tu fais fait référence à l'indécidabilité algorithmique ?

Shah d'Ock · April 2017

Champ-pot-lion: oui.

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

Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24