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
179 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$ ?
il y a deux années
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.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par AD.
Re: $\text{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
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$ ?
il y a deux années
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$ ?
il y a deux années
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".



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par pourexemple.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
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$ ?
il y a deux années
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.]



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par Champ-Pot-Lion.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
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.))



Edité 4 fois. La dernière correction date de il y a deux années et a été effectuée par Champ-Pot-Lion.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
@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$ ?
il y a deux années
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$ ?
il y a deux années
Oui, c'est similaire ! Je n'avais pas remarqué. On a d'ailleurs le même mot : « modèle ».



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par AD.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
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$ ?
il y a deux années
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$ ?
il y a deux années
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$ ?
il y a deux années
@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$ ?
il y a deux années
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$ ?
il y a deux années
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$ ?
il y a deux années
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$ ?
il y a deux années
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$ ?
il y a deux années
avatar
Salut

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

Cordialement.



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par AD.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
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 ?



Edité 1 fois. La dernière correction date de il y a deux années et a été effectuée par Champ-Pot-Lion.
Re: Le cardinal $\rm{card}(\{1,2\}^{\{1\}})>2$ ?
il y a deux années
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: 135 807, Messages: 1 311 181, Utilisateurs: 23 811.
Notre dernier utilisateur inscrit ritchi46.


Ce forum
Discussions: 2 045, Messages: 39 710.

 

 
©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