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
303 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
 
 
 
 
 

Logique bivalente et décidabilité

Envoyé par Homo Topi 
Logique bivalente et décidabilité
il y a six semaines
La logique mathématique "classique" se veut bivalente : chaque énoncé possède une valeur de vérité, et une seule, qui est soit "vrai", soit "faux".

Mais là, je me dis... il existe des énoncés indécidables, comme l'hypothèse du continu dans ZFC par exemple. En logique classique, ça veut dire, HC possède une valeur de vérité, mais on peut démontrer qu'on ne peut pas déterminer laquelle dans ZFC. Dans un certain sens, ça me paraît contradictoire... comment HC pourrait-il avoir une valeur de vérité "absolue" dans ZFC si, dans ZFC, on peut prouver que cette valeur de vérité est impossible à déterminer ? Surtout que, si j'ai bien suivi, on peut supposer HC vraie et ne pas aboutir à une incohérence, et on peut supposer HC fausse sans aboutir à une incohérence non plus. Ça me donne envie de dire que la valeur de vérité de HC n'est ni "vrai", ni "faux" du coup... Mais ça ne devrait pas marcher dans un système logique bivalent.

Qu'est-ce que je fais de faux là-dedans ?

“Les mathématiques ne connaissent ni races, ni frontières géographiques. Pour les mathématiques, le monde de la culture est un seul et même pays.” - David Hilbert
Re: Logique bivalente et décidabilité
il y a six semaines
Tu confonds "vrai/faux" et "prouvable/non prouvable". Le tiers exclu nous dit "HC est vraie ou HC n'est pas vraie". C'est en particulier un théorème de ZFC: pour prouver un résultat, si tu sais le prouver en supposant HC et en supposant non HC, tu l'as prouvé sans hypothèse supplémentaire.

Sémantiquement, ça veut dire que si tu fixes un modèle de ZFC (un univers), HC y est vraie, ou elle y est fausse. Seulement, l'option qui est vérifiée (vraie ou pas) va dépendre du modèle/univers que tu fixes : c'est le contenu des théorèmes d'indécidabilité de Cohen et Gödel.

En particulier, ni HC ni non HC n'est prouvable, bien que HC ou non HC le soit. De la même manière que "tout groupe est abélien ou non abélien" est prouvable, pour autant ni "tout groupe est abélien" ni "tout groupe est non abélien" n'est prouvable.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Logique bivalente et décidabilité
il y a six semaines
Donc en gros, une fois que j'ai fixé un modèle de ZFC (j'ai encore vraiment du mal à comprendre ce que ça veut dire), je fixe aussi la valeur de vérité "au sein du modèle" de tous les énoncés ZFC-indécidables, c'est ça ?

Mais est-ce que la valeur de vérité va être identifiable dans le modèle, ou pas forcément ?

“Les mathématiques ne connaissent ni races, ni frontières géographiques. Pour les mathématiques, le monde de la culture est un seul et même pays.” - David Hilbert
Re: Logique bivalente et décidabilité
il y a six semaines
Oui, dans un modèle fixé, tous les énoncés ont une valeur de vérité ($0$ ou $1$) fixée. De là à dire qu'on peut la déterminer, c'est une autre question : si je te donne un groupe (disons avec une présentation finie) tu n'as pas forcément de procédure pour déterminer si $\exists x, x\neq e$ y est vérifié ou pas (pourtant, cette formule y est vérifiée, ou ne l'est pas : le groupe est trivial ou pas)

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Logique bivalente et décidabilité
il y a six semaines
@Homo Topi : ta question de l'identifiabilité de la vérité est trop vague. En tout cas, du point de vue algorithmique on connaît beaucoup de situations où on peut dire qu'on ne peut pas "identifier" quelle est la valeur de vérité de certaines formules, par exemple la formule proposée par Maxtimax, ou dans le même genre, le problème du mot dans un groupe finiment présenté.
Re: Logique bivalente et décidabilité
il y a six semaines
Précision : il n'est vraiment ABSOLUMENT exact de dire même en classique qu'un groupe présenté par blabla est où n'est pas trivial. Ça dépend de l'univers (souvent tacite) où la question est posée. Idem pour les équations diophantiennes. De mon téléphone (je suscité éventuellement curiosité et répondrai en deuxième temps si besoin).

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi



Edité 1 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Logique bivalente et décidabilité
il y a six semaines
Christophe : bien sûr, mais il est ou n'est pas trivial. La question de savoir si la réponse dépend de l'univers est une question tout à fait distincte

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Logique bivalente et décidabilité
il y a six semaines
Bin non, certains univers le voient trivial et d'autres non. Ou alors je n'ai pas compris ta remarque et comme GG, tu évoques d'hypothétiques "vrais entiers", mais j'ai un tel mal au dos, que je préfère fuir au lit qu'attendre une réponse à cette haute question philosophique, car elle stresse son monde.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a six semaines
Non pas du tout, l'énoncé "$G$ est trivial ou ne l'est pas" est juste vrai dans tout univers grinning smiley On n'échange pas $\forall$ et $\lor$ par contre; mais c'est une question différente.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Logique bivalente et décidabilité
il y a six semaines
Oui je pensais que tu disais autre chose. Mais si moi j'ai été conduit au bord sujet c'est que peut être il sera utile que je fasse un post d'un PC pour EXPLICITER car je vois une homonymie possible si on ne précise pas le contexte.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a six semaines
Voici la phrase que j'avais loupée.

Citation
homo topi
Donc en gros, une fois que j'ai fixé un modèle de ZFC

@Homo topi: un modèle est PAR DEFINITION une fonction qui à chaque phrase associe un élément de $\{vrai; faux\}$.

J'ai souvent dit et je répète qu'il est mieux de regarder les modèles comme des théories complètes qui nomment*** tous leurs individus. L'illusion sémantique peut conduire à des contre-sens.

Ce qui signifie que si un modèle $M$ est tel que $M(\exists xR(x))=vrai$ alors il existe un nom $a$ tel que $M(R(a)) = vrai$.

Citation
homo topi
mais on peut démontrer qu'on ne peut pas déterminer laquelle dans ZFC. Dans un certain sens, ça me paraît contradictoire... comment HC pourrait-il avoir une valeur de vérité "absolue" dans ZFC si, dans ZFC, on peut prouver que cette valeur de vérité est impossible à déterminer ?


C'est très simple: $P$ est démontrable dans $ZFC$ quand pour tout modèle $M$ de ZFC: $M(P)=vrai$.

En ce qui concerne HC, ce que tu as est la chose suivante:

1/ il existe un modèle de ZFC $M_1$ tel que $M_1(HC)=vrai$
2/ il existe un modèle de ZFC $M_2$ tel que $M_2(HC)=faux$

C'est tout.

Ceci n'a rien à voir avec l'intuitionnisme.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a six semaines
@christophe c (ou qui veut me répondre) désolé de m'incruster mais j'aimerais comprendre moi aussi.

J'aimerais comprendre ces phrases.
Citation
cc
...il est mieux de regarder les modèles comme des théories complètes qui nomment*** tous leurs individus... Ce qui signifie que si un modèle $M$ est tel que $M(\exists xR(x))=vrai$ alors il existe un nom $a$ tel que $M(R(a)) = vrai$.

Quand tu parles de "théorie complète" tu penses à la définition donnée par Wikipedia je pense. Dans ce cas tu veux dire quoi par des théories complètes qui nomment*** tous leurs individus ?

Je précise : ce que je sais est qu'une théorie logique du premier ordre contient des symboles de constantes, de variables, de fonctions et de relations et qu'on construit des termes et des formules avec les règles appropriées. Ayant précisé ceci, ça veut dire quoi qu'une théorie nomme tous ces individus ?

Tu écris : si un modèle $M$ (donc une fonction selon ce que tu as dit avant) est tel que $M(\exists xR(x))=vrai$ alors il existe un nom $a$ tel que $M(R(a)) = vrai$.

"$\exists xR(x)$" est une formule du langage (où $R$ est un symbole de relation unaire), M envoie donc $\exists xR(x)$ sur $vrai$, mais ton $a$ c'est quoi ? une constante du langage ?
Re: Logique bivalente et décidabilité
il y a six semaines
Christophe a une définition personnelle de ce qu'est un modèle, différente de celle de "tout le monde". Je n'en vois pas l'intérêt.
À ce que je comprends, la théorie des corps réels clos, par exemple, a un seul modèle en son sens. Bof bof.
Re: Logique bivalente et décidabilité
il y a six semaines
@raoul.S: Je pense qu’il veut dire dans le jargon officiel « qui admet des témoins de Henkin » et qu’il se permet d’assimiler théorie complète qui admet des témoins de Henkin et modèle via le théorème de complétude en fait. Mais pareil je suis intéressé par ce qu’il veut dire par là. Au moins ça te donne un mot clé à Googler si jamais.

[Leon Albert Henkin (1921-2006) prend toujours une majuscule. AD]



Edité 2 fois. La dernière correction date de il y a six semaines et a été effectuée par AD.
Re: Logique bivalente et décidabilité
il y a six semaines
De mon téléphone : je détaillerai d'un PC mais tu te trompes GBZM. Tu oublies les constantes. grinning smiley

Mes modèles sont les modèles usuels je fais juste remarquer que les deux paradigmes ne dont que psychologiquement différents.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a six semaines
Si je me trompe, c'est parce que tes propos sont flous.
Si tes modèles sont en fait les modèles usuels, pourquoi parler "d'illusion sémantique qui peut conduire à des contresens" ?
Re: Logique bivalente et décidabilité
il y a six semaines
De mon téléphone ce n'est pas très facile donc j'espère que toi comprendra un résumé sms mais je ferai un PC post pour les autres lecteurs.

Oui le flou de mon propos à d'ailleurs été souligné par Grthen qui croyait que j'evoquais forcément la skolemisation. La dessus tu as raison.

Mais mon souhait était de souligner (pour caricaturer) l'absence de différence clinique entre M models R(u,v) et M(R(u,v))=vrai et entre la complétude et le lemme de Zorn.

Voir par tes corps ordonnés comme des "mondes blabla" ou les voir comme une fonction envoie un ensemble de phrases dans {vrai,faux} (par exemple: IR(pi=e)= faux) ce est au fond qu'une différence psy.

C'edt pourquoi j'utilise l'expression "tous individus nommés" pour aller vite.

D'un PC je ferai un truc plus soigné.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a six semaines
@grothenbiete ok merci je vois à-peu-près.

Citation
GaBuZoMeu
Christophe a une définition personnelle de ce qu'est un modèle, différente de celle de "tout le monde"

Ben disons que ça m'intéressait de voir un modèle comme une fonction car je ne suis pas certains de comprendre la définition de "tout le monde".

Je veux dire est-ce qu'on a une "définition standard" rigoureuse de ce qu'est un modèle ?

Car en lisant dans les bouquins j'ai cru comprendre que c'est une structure où vivent les objets dont parle la théorie logique qu'on considère. Donc finalement on pense à un modèle comme à un ensemble naïf (un groupement d'objet quoi), les relations du langages étant interprétées comme des relations de l'ensemble naïf du modèle, les symboles de fonctions comme des fonctions de l'ensemble naïf du modèle, etc.

Me trompé-je ?
Re: Logique bivalente et décidabilité
il y a six semaines
Ça mériterait d'être un peu plus précis, mais c'est bien ça.
En quoi ça te pose problème ?
Re: Logique bivalente et décidabilité
il y a cinq semaines
Disons que la première fois que j'ai été confronté à cette notion de modèle ça m'a laissé un peu perplexe.

Je précise : avant de lire un quelconque texte de logique j'avais déjà étudié quelques structures algébriques (groupes, anneaux, etc.), suivis un cours de topologie etc. bref à chaque fois qu'on étudie ces théories on utilise la notion d'ensemble. En effet une structure de groupe par exemple est définie sur un ensemble, mais au début on étudie ces théories avec une idée naïve d'ensemble (car la majeure partie des fois c'est amplement suffisant). Donc en gros on voit un ensemble comme un groupement d'objets et voilà.

Puis lorsque j'ai mis un peu le nez dans la logique du premier ordre et un peu dans la théorie des ensembles pour comprendre comment formaliser correctement la notion d'ensemble j'ai été confronté à la notion de modèle et je me suis rendu compte qu'en fait mentalement on (ou en tout cas moi) a une image de ce qu'est un modèle (ou un "univers" dans la théorie des ensembles) qui est exactement la même que celle qu'on avait d'un ensemble naïf avant d'avoir lu un quelconque texte de logique.

Du coup on formalise la notion d'ensemble mais on ne se gène pas pour introduire la notion de modèle qui n'est pas du tout formalisée (ou bien ?) mais se base sur l'idée naïve classique du gros sac d'objets. En fait j'ai l'impression qu'on ne fait que déplacer "le problème".

Si quelqu'un peut m'éclairer et/ou confirmer... merci d'avance.



Edité 2 fois. La dernière correction date de il y a cinq semaines et a été effectuée par AD.
Re: Logique bivalente et décidabilité
il y a cinq semaines
Ben un modele est une L-structure donc est notamment un quadruplet d’ensembles, un premier ensemble non vide appelé univers, une application qui envoie les constantes sur l’univers, une application qui envoie les fonctions du langage sur des fonctions à plusieurs variables sur l’univers en conservant l’arité , et une fonction qui envoie les relations blabla sur blabla fin tu connais. Un quadruplet d’ensembles est un ensemble comme un autre, il faut juste comprendre qu’on décide d’etudier la logique mathématique en tant qu’objet mathématique donc avec la logique mathématique, et on parle et on raisonne sur l’objet « logique mathématique » avec le paradigme théorie des ensembles par défaut. Dans l’absolu on ne sait pas qu’on parle de la logique mathématique avec laquelle on raisonne, c’est un pari quelque part que de penser que ma description de mes raisonnements consiste bien en l’étude du gros machin qu’est l’ensemble des formules construites par induction sur un alphabet. Tu pourrais totalement oublier que t’es en train de t’etudier avec les moyens que tu étudies en regardant toutes ces structures banalement comme tu le fais quand tu fais de la topo ou ce que tu veux. Mais je pense pas qu’un problème est déplacé, un modèle est un ensemble comme un autre et c’est clairement assumé. Quant à ensemble, ça n’a pas de définition vraiment satisfaisante (ça bouclerait un moment ou on resterait sur notre faim mais y a pas le choix confer le problème du dictionnaire avec un nombre fini de mots qui ne satisfait jamais personne)

Bon c’est du baratin de néophyte hein

Édit: enfin on peut trouver plein de définitions « équivalentes dans les faits » de modèle, mais dans tout ce que j’ai vu c’est parfaitement formel. J’imagine que celle de CC se prête mieux au paradigme « lambda calcul » où le terme non défini de base est application plutôt qu’ensemble, mais j’imagine aussi que c’est très formel aussi



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par grothenbiete.
Re: Logique bivalente et décidabilité
il y a cinq semaines
Bonjour,

désolé de m'immiscer dans ce fil. Vous pouvez ne pas répondre si les questions vous semblent déplacé.
Qu'en est-il de la notion de modèle alors si l'on essaie de se placer dans le cadre de la théorie des catégories ?
Le fil est parti d'une question sur la notion de bivalence. Ayant écouté une conférence d' Alain Connes, que se passe-t-il si l'on se place dans le cadre des topos, dans lequel la bivalence est un cas particulier ? (Bien entendu, je ne comprends rien aux topos,...)

Merci.

ignatus.
Re: Logique bivalente et décidabilité
il y a cinq semaines
Jean-Louis Krivine, Théorie axiomatique des ensembles :

On considère une collection d'objets, collection qu'on appellera univers, et qu'on désignera par $\mathcal U$; on ne dit pas : "considérons un ensemble $\mathcal U$", car ce que nous appellerons ensembles, ce sont précisément les objets de $\mathcal U$ etc.

Les "ensembles naîfs" de raoul.S sont les collections de Krivine.

Pour ignatus : pour la sémantique dans un topos, l'univers est un objet du topos. Mais si tu ne connais rien aux topos, te voila bien avancé !



Edité 1 fois. La dernière correction date de il y a cinq semaines et a été effectuée par GaBuZoMeu.
Re: Logique bivalente et décidabilité
il y a cinq semaines
Je souffre d'un mal de dos inouï mais des que disponibilité je ferai un post détaillé en latex d'un PC. En gros il y a deux dimensions:

1/ la valeurs de vérité

2/ le "Tout-L'univers-Des-Possible" où se déroule le film.

Et une "pseudo-difficulte" les notions premières (problème de poule ou l'oeuf en gros).

Bien que ce ne soit pas très dur, ça nécessite des conversations détaillées.

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a cinq semaines
Bonjour GaBuZoMeu,

il me semble juste qu'on appelle topos une catégorie équivalente à la catégorie des faisceaux d'ensembles sur un espace topologique.
On peut parler de topos d'une catégorie en produisant un analogue d'un espace topologique, qui est une catégorie munie d'un site, le site définissant une topologie. On peut alors construire des faisceaux d'ensembles à partir des "ouverts" de la catégorie, et on appelle ça un topos.

D'après ce que tu dis, pour la sémantique d'un topos, l'univers est équivalent à un faisceau d'ensemble.

J'ai bien envie de comprendre cette relation entre théorie des modèles et topos, et notamment comment cela peut généraliser ce que l'on appelle la logique bivalente. Je peux ouvrir un fil parallèle si des bonnes âmes veulent bien me donner un peu de leur temps pour éclaircir ce problème.
Merci en tout cas.

ignatus.
Re: Logique bivalente et décidabilité
il y a cinq semaines
Citation
grothenbiete
...on parle et on raisonne sur l’objet « logique mathématique » avec le paradigme théorie des ensembles par défaut... Mais je pense pas qu’un problème est déplacé, un modèle est un ensemble comme un autre et c’est clairement assumé.

Ok en fait tu es en train de dire qu'on fait de la logique à l'intérieur de la théorie des ensembles et que les symboles du langage qu'on considère sont en fait des ensembles tout comme la L-structure.

J'ai toujours pensé que ce n'était pas le cas et que lorsqu'on étudie la logique on se place à l'extérieur de la théorie des ensembles...

et que les collections de Krivine sont des modèles (hypothétiques) de la théorie des ensembles...

@GaBuZoMeu j'ai le bouquin de théorie des ensembles de Jean-Louis Krivine mais je n'ai jamais dépassé le chapitre 4 grinning smiley.
Ceci dit je me souviens très bien de la phrase que tu cites (car elle est en première page du chap.1). J'espère que tu n'es pas Jean-Louis Krivine grinning smiley
Re: Logique bivalente et décidabilité
il y a cinq semaines
@raoul.S :
Théorème : GaBuZoMeu n'est pas JLK.
Démonstration par l'absurde : JLK ne traîne pas sur ce forum.

P.S. Si tu as tout compris jusqu'au Chap 4 c'est déjà pas mal
Re: Logique bivalente et décidabilité
il y a cinq semaines
Je posterai mais plus tard (trop fatigué, bien que sur mon pc).

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Logique bivalente et décidabilité
il y a cinq semaines
C'est compliqué, tout ça... Je ne sais pas si je comprends les choses. Je vais ouvrir un nouveau fil de discussion pour qu'on parle un peu des modèles, parce que j'ai vraiment vraiment VRAIMENT du mal avec ça.

Libre aux modérateurs de supprimer le nouveau fil et de le réintégrer ici, on verra bien ce qu'ils en pensent.

“Les mathématiques ne connaissent ni races, ni frontières géographiques. Pour les mathématiques, le monde de la culture est un seul et même pays.” - David Hilbert
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: 137 936, Messages: 1 337 760, Utilisateurs: 24 640.
Notre dernier utilisateur inscrit edcouturier.


Ce forum
Discussions: 2 132, Messages: 41 877.

 

 
©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