Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
203 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

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

Envoyé par pourexemple 
Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 19:13
avatar
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.



Modifié 1 fois. Dernière modification le 24/04/2017 21:17 par AD.
Re: $\text{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 19:22
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.
Re: $\text{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 21:18
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$)

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 21:54
avatar
@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".



Modifié 1 fois. Dernière modification le 24/04/2017 21:55 par pourexemple.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 22:14
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.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 22:17
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.]



Modifié 1 fois. Dernière modification le 25/04/2017 14:04 par Champ-Pot-Lion.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 22:20
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.))



Modifié 4 fois. Dernière modification le 25/04/2017 14:04 par Champ-Pot-Lion.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 22:37
@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.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 22:40
avatar
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é ?
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
24 avril 2017, 22:43
Oui, c'est similaire ! Je n'avais pas remarqué. On a d'ailleurs le même mot : « modèle ».



Modifié 1 fois. Dernière modification le 24/04/2017 22:51 par AD.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 00:35
avatar
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.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 00:44
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.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 01:38
avatar
J'ai peut-être loupé quelque chose, mais je crois qu'on ne sait toujours pas ce que pourexemple appelle une fonction classique.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 02:04
@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.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 08:44
avatar
Mais j'y connais rien moi spinning smiley sticking its tongue out

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 ?
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 09:30
avatar
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).
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 09:56
avatar
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.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 10:37
avatar
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 ?
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 11:15
avatar
Salut

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

Cordialement.



Modifié 1 fois. Dernière modification le 25/04/2017 20:34 par AD.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 14:02
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 ?



Modifié 1 fois. Dernière modification le 25/04/2017 14:05 par Champ-Pot-Lion.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
25 avril 2017, 16:10
avatar
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é.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 150 629, Messages: 1 528 643, Utilisateurs: 28 092.
Notre dernier utilisateur inscrit Vélocipède2021.


Ce forum
Discussions: 2 570, Messages: 52 459.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page