tautologies, axiomes et règles

[Médiat]

Les coupures de Dedekind qui partionnent Q

Donner un nom à un problème ne résout pas le problème, je répète ma question : comment faites-vous (je vous rappelle qu'il s'agit de logique du premier ordre) ?
-----

[invite7863222222222]

Justement la est ma question/mon interrogation.

Ca me semble difficile, car un mathématicien à ce jour, même constructiviste, ne peut construire qu'une quantité dénombrable de réels.

[karlp]

, il suffit de (re)lire la définition de cet ensemble des parties pour comprendre ce piège :


Ce qui peut se lire (à la louche) : il existe un ensemble qui contient tous les ensembles qui sont des sous ensembles de x.

Ce qui ne doit pas se lire : il existe un ensemble qui contient tous les sous ensembles de x.

.

Très remarquable Médiat, j'ai le plus grand mal avec l'expression formelle ci dessus.
Je viens de passer une heure avec un professeur de math du supérieur (il n'est certes pas un spécialiste de la théorie des modèles) qui n'a pas pu m'éclairer et qui me demande s'il n'y a eu aucune erreur d'écriture. A priori j'ai pleine confiance en vos compétences. Pouvez vous confirmer ? (je vais rechercher d'autres formulations peut être plus à la portée de mon indigence)

[Deedee81]

On comprend mieux pourquoi les réels sont "mal définis" (dans un certain sens du moins), ce qui est vraiement très peu intuitif.

C'est fou mais je viens seulement de comprendre pourquoi il y a cette indécidabilité de HC.

Aaaaah les pièges de l'infini

P.S. : je ne pense pas que la nature pose ce problème. La gravitation quantique semble montrer que l'espace-temps est discrétisé (ou du moins les spectres de longueurs, durées,..., Voir la gravité quantique à boucles. C'est moins flagrant en TDC). On est donc dans le fini. Mais ça ne change que le coté "philosophique" car vouloir faire de la physique en se passant des réels et de l'analyse, c'est à peu près la même chose que de vouloir voyager dans l'espace sans engin spatial C'est un mal nécessaire pourrais-je dire un peu abusivement

[invité576543]

car vouloir faire de la physique en se passant des réels et de l'analyse, c'est à peu près la même chose que de vouloir voyager dans l'espace sans engin spatial C'est un mal nécessaire pourrais-je dire un peu abusivement

Pas si clair que cela. Par exemple, toutes les simulations par ordinateurs correspondent à des méthodes se passant totalement des réels. Et pourtant ce serait choquant de ne y pas voir "faire de la physique". Par exemple pour concevoir un avion alors qu'on ne sait pas résoudre analytiquement Navier-Stokes. Non?

[Médiat]

j'ai le plus grand mal avec l'expression formelle ci dessus.

J'aurais pu écrire cette formule plus simplement :



Mais je ne me souvenais plus du symbole d'inclusion en latex et ce matin je n'avais pas le temps de chercher .

Une remarque : l'ensemble y qui est défini par l'axiome ci-dessus (axiome de l'ensemble des parties) peut très bien contenir des éléments qui ne sont pas inclus dans x .

[karlp]

J'aurais pu écrire cette formule plus simplement :



Mais je ne me souvenais plus du symbole d'inclusion en latex et ce matin je n'avais pas le temps de chercher .

Une remarque : l'ensemble y qui est défini par l'axiome ci-dessus (axiome de l'ensemble des parties) peut très bien contenir des éléments qui ne sont pas inclus dans x .

Merci infiniment ! cette écriture m'est effectivement beaucoup plus familière (je prendrais quand même le temps de comprendre l'autre)

Est-ce parce que, comme vous le dîtes, Y peut contenir des éléments qui ne sont pas des sous ensembles de X que HC reste indémontrable ?... celà peut-il signifier que le cardinal de IR peut être supérieur à 2 puissance aleph zero ?

[Médiat]

Est-ce parce que, comme vous le dîtes, Y peut contenir des éléments qui ne sont pas des sous ensembles de X que HC reste indémontrable ?...

Non pas du tout (je suis allé trop vite pour écrire cette remarque perfide), ce n'est pas parce qu'il peut en contenir trop, mais parce qu'il peut ne pas les contenir "tous" (au sens où un être humain peut comprendre "tous" dans la phrase précédente) ; qu'il puisse en contenir trop est juste un petit détail facile à surpasser ...

celà peut-il signifier que le cardinal de IR peut être supérieur à 2 puissance aleph zero ?

On touche à une subtilité : le cardinal de IR est toujours , mais comme IR n'est pas toujours "le même", cela veut dire que n'est pas toujours "le même".

[invite7863222222222]

qu'il puisse en contenir trop est juste un petit détail facile à surpasser ...

L'erreur de votre message précédent tendrait à montrer qu'il est plus difficile de passer du minimum au trop, que du trop au minimum ou était-ce encore une erreur volontaire d'ordre pédagogique ?

[Médiat]

L'erreur de votre message précédent tendrait à montrer qu'il est plus difficile de passer du minimum au trop, que du trop au minimum ou était-ce encore une erreur volontaire d'ordre pédagogique ?

De quelle erreur parlez-vous ?

[mh34]

Encore une fois, merci Médiat pour votre patience.

J'ai une autre question ; si HC est indécidable dans ZFC, existe-t-il des modèles, des théories, dans lesquelles HC ne serait plus indécidable?

[Médiat]

J'ai une autre question ; si HC est indécidable dans ZFC, existe-t-il des modèles, des théories, dans lesquelles HC ne serait plus indécidable?

Oui, ZFC + HC est une théorie où HC n'est pas indécidable ; d'ailleurs ZFC + non HC est un autre exemple.

Pour les modèles, c'est la même chose, les deux exemples sont "construits" par les démonstrations de Gödel et de Cohen (mais c'est loin d'être simple, surtout pour la partie Cohen (il a eu la médaille Fields pour cela )).

[invite6754323456711]

comment faites-vous (je vous rappelle qu'il s'agit de logique du premier ordre) ?

Lorsque l'on écrit :

∀E ∃P ∀A (A ∈ P ⇔ A ⊂ E)

Pour tout ensemble E (on est sensé tous les considérer non ?), il existe un ensemble P tel que tout ensemble A (idem) est un élément de P si et seulement s’il (⇔ ) est une partie de E. Donc toute les parties de E (A ⊂ E) font partie de P non ?

Patrick

[invite7863222222222]

HC reste indémontrable car l'ensemble y défini plus haut ne peut pas contenir tous les éléments qui ne sont pas inclus dans x (désolé d'être largué).

[invité576543]

On touche à une subtilité : le cardinal de IR est toujours , mais comme IR n'est pas toujours "le même", cela veut dire que n'est pas toujours "le même".

N'est-ce pas juste une subtilité de vocabulaire ? Ne pourrait-on pas avoir un vocabulaire tel que dénote quelque chose comme (aucune idée si c'est formalisable) "le plus grand nombre d'éléments que peut avoir l'ensemble des parties de N tout modèles confondus" ? (Et donc d'utiliser une autre notation pour le cardinal de R dans un modèle donné.)

[Médiat]

Lorsque l'on écrit :

∀E ∃P ∀A (A ∈ P ⇔ A ⊂ E)

Pour tout ensemble E (on est sensé tous les considérer non ?), il existe un ensemble P tel que tout ensemble A (idem) est un élément de P si et seulement s’il (⇔ ) est une partie de E. Donc toute les parties de E (A ⊂ E) font partie de P non ?

Et bien justement : non ! Relisez mon message #108 et en particulier les deux commentaires sous la formule. Essayer d'écrire "toute les parties de E", telle que vous l'entendez, d'une façon formelle ...

[invité576543]

annulé.......

[Médiat]

N'est-ce pas juste une subtilité de vocabulaire ? Ne pourrait-on pas avoir un vocabulaire tel que dénote quelque chose comme (aucune idée si c'est formalisable) "le plus grand nombre d'éléments que peut avoir l'ensemble des parties de N tout modèles confondus" ? (Et donc d'utiliser une autre notation pour le cardinal de R dans un modèle donné.)

Malheureusement, il n'y a aucune façon de formaliser cela au premier ordre (ni même à un ordre supérieur, me semble-t-il) ; et je ne suis pas certain (à part un certain confort intellectuel qui pourrait satisfaire le mathématicien platonicien, mais pas le logicien) que cela serait très utile car lorsque l'on fait des mathématiques c'est au sein d'un modèle et non de tous, il est donc plus utile d'avoir une définition valide dans ce modèle (pour l'exponentielle par exemple).

Et je ne parle pas de la difficulté à définir "le plus grand nombre d'éléments" entre ensembles définis formellement de façon commune, mais vivant dans des modèles différents.

[invite6754323456711]

Essayer d'écrire "toute les parties de E", telle que vous l'entendez, d'une façon formelle ...

j'ai l'impression que la définition donné dans wiki n'est pas la même que celle que vous donnez.

∀E ∃P ∀A (A ∈ P ⇔ A ⊂ E).

Il y a ⇔. ∀A (A ⊂ E ⇔ A ∈ P)

Ce qui peut se lire : il existe un ensemble qui contient tous les sous ensembles de E non ?

Maintenant cette formulation n'est peut être pas correcte car on ne peut décrire en logique du premier ordre "toute les parties de E" ?

Patrick

[Médiat]

j'ai l'impression que la définition donné dans wiki n'est pas la même que celle que vous donnez.

∀E ∃P ∀A (A ∈ P ⇔ A ⊂ E).

Il y a ⇔. ∀A (A ⊂ E ⇔ A ∈ P)

Ce qui peut se lire : il existe un ensemble qui contient tous les sous ensembles de E non ?

La définition de wikipedia est correcte, ... et la mienne aussi (il va de soi que la définition de wiki implique la mienne, mais on peut démontrer que la mienne implique celle de wiki, dans ZF).

Le problème vient exclusivement dans la signification de "tous les sous-ensembles" selon que c'est un humain (qui n'est pas un logicien formaliste ) qui interprète cette phrase, ou qu'on la considère du point de vue formel, dans le cadre de ZFC. S'il n'y avait pas de différence vous arriveriez à écrire votre "tous" de façon formelle.

[Médiat]

Pour les modèles, c'est la même chose, les deux exemples sont "construits" par les démonstrations de Gödel et de Cohen (mais c'est loin d'être simple, surtout pour la partie Cohen (il a eu la médaille Fields pour cela )).

J'ai oublié de préciser qu'en tout état de cause, dans un modèle, il n'y a pas de proposition indécidable.

[invité576543]

J'ai oublié de préciser qu'en tout état de cause, dans un modèle, il n'y a pas de proposition indécidable.

Là, cela met le doigt sur un aspect de la théorie des modèles qui m'échappe.

Je serais intéressé par un petit développement, parce que rien dans mes lectures annexes (et dont je me souviens) ne me permet de comprendre cette affirmation.

[invite6754323456711]

Le problème vient exclusivement dans la signification de "tous les sous-ensembles" selon que c'est un humain (qui n'est pas un logicien formaliste ) qui interprète cette phrase, ou qu'on la considère du point de vue formel, dans le cadre de ZFC. S'il n'y avait pas de différence vous arriveriez à écrire votre "tous" de façon formelle.

Il va donc valoir apprendre à lire ces subtilités Il y a encore beaucoup de piège de ce type dans la théories des ensembles ?

Patrick

[Médiat]

Là, cela met le doigt sur un aspect de la théorie des modèles qui m'échappe.

Je serais intéressé par un petit développement, parce que rien dans mes lectures annexes (et dont je me souviens) ne me permet de comprendre cette affirmation.

Si vous considérez la théorie des groupes, la commutativité y est indécidable (c'est dans les vieux pots que l'on fait les meilleurs exemples), mais si vous considérez un modèle particulier, soit c'est un groupe commutatif, soit c'est un groupe non commutatif.

D'une façon plus générale, dans un modèle, les éléments du langage sont interprétés, c'est à dire que s'il y a un symbole de relation R (disons binaire) dans le langage, alors dans le modèle, pour chaque couple (a, b) d'éléments de ce modèle, on sait si R(a, b) ou si non R(a, b), si je veux vérifier si pour tout x R(x, x), il "suffit de vérifier que la diagonale est bien dans R ; cet exemple se généralise à toutes les formules atomiques et par récurrence sur la complexité de la formule, à toutes les formules du langage.

Un modèle est un "monde" dans lequel les éléments du langage sont interprétés, et les axiomes vérifiés pour cette interprétations, et chaque élément (ou n-uplet) du modèle vérifie ou non chacune des formules atomiques.

J'espère que c'est plus clair.

Histoire de combattre une fois de plus certaines façons de massacrer le théorème d'incomplétude de Gödel : la théorie de IN dans le langage (0, s, +, .), c'est à dire l'ensembles de formules "vraies" dans ce modèle, pour ce langage est une théorie complète (qui, évidemment permet de formaliser l'arithmétique).

[Médiat]

Il va donc valoir apprendre à lire ces subtilités Il y a encore beaucoup de piège de ce type dans la théories des ensembles ?

Il y a ce genre de subtilité (pas des pièges), et il faut apprendre à les décrypter, dans toutes les théories dès que l'on admet sans vérification, que le langage informel se traduit exactement dans le langage formel (et le vocabulaire peut être un piège).
D'où l'intérêt collatéral d'être formaliste .

[invité576543]

J'espère que c'est plus clair.

Malheureusement, cela ne suffit pas à vaincre les épaisses membranes dont s'entoure, par mesure de prudence, mon entendement toujours actif.

L'exemple pour les groupes montre une propriété indécidable dans la théorie qui ne l'est pas dans les modèles. OK. Mais la phrase à laquelle je répondais contenait un "il n'y a pas".

Passons alors à la généralité, et la je butte sur le "on sait si R(a,b) ou non R(a,b)". Que veut dire ce "on sait" ? En particulier si le modèle n'est pas dénombrable ?

Ce "on sait" est une propriété que tout modèle doit avoir pour avoir l'étiquette "modèle", ou est-ce une propriété qui découle d'aspects plus fondamentaux du concept de modèle.

Histoire de combattre une fois de plus certaines façons de massacrer le théorème d'incomplétude de Gödel : la théorie de IN dans le langage (0, s, +, .), c'est à dire l'ensemble de formules "vraies" dans ce modèle, pour ce langage est une théorie complète (qui, évidemment permet de formaliser l'arithmétique).

"ce modèle" renvoie à N comme modèle ?

Autre point : ici comme dans le message d'avant, est utilisée la relation "dans" entre "formule" (ici) ou "proposition" (avant) et modèle.

Comme je n'arrive toujours pas à cerner le mot "modèle", je n'arrive pas à voir un modèle comme ayant dedans des formules.

[invite6754323456711]

Comme je n'arrive toujours pas à cerner le mot "modèle", je n'arrive pas à voir un modèle comme ayant dedans des formules.

J'arrive à me faire une compréhension de la notion de modèle en séparant clairement l'aspect syntaxique de l'aspect sémantique des théories du premier ordres c'est à dire les théories exprimés dans des langages formel du premier ordre.

Les langage sont d'abord définis par leur syntaxe, sans aucune référence à la signification de leurs expressions. Pour définir un langage formel, il faut se donner un alphabet (ensemble de symboles) et des règles permettant de construire les "expression bien formés" c'est à dire conforme aux règles syntaxiques.

Le langage du premiers ordre L est donc construit syntaxiquement à partir des symboles :

- ensemble de variables,
- ensemble de constantes
- ensemble de fonctions
- ensemble de relations

On définit ensuite les termes, les formules atomiques, les formules composées ...

D'un point de vue sémantique l'interprétation d'une formule dépend de l'ensemble (univers) dans lequel on travaille et du sens données aux symboles dans cet univers.

Nous avons l'équivalence Formule1 |-- Formule2 ⇔ Formule 2 est une conséquence logique de Formule1


Par exemple un modèle des axiomes de Peano est une structure de Dedeking <A, f, a> ou A est un ensemble, f une fonction défini sur A et a ∈ A, qui satisfait tout les axiomes. La structure de Dedeking <IN,s,0> (ou s est la fonction successeur) est un modèle des axiomes de Peano. Il semble que Dedeking est montré que deux structures de Dedeking quelconques sont isomorphes. Autrement dit ces conditions définissent IN à l'isomorphisme prés.

De manière générale un énoncé L est une conséquence des axiomes s'il est vrai dans tous les modèles.

Patrick

[Médiat]

Passons alors à la généralité, et la je butte sur le "on sait si R(a,b) ou non R(a,b)". Que veut dire ce "on sait" ? En particulier si le modèle n'est pas dénombrable ?

Il est exact que "on sait" était un peu maladroit, mais pas totalement injustifié, une interprétation d'un symbole de relation binaire dans un modèle d'univers M est un "sous-ensemble" (sous collection si vous préférez éviter les interférences) de M², en ce sens, la question de savoir si un être humain peut savoir si R(a, b) ou non n'est pas pertinente ("on sait" était maladroit), mais d'un autre côté si un être humain ne peut pas savoir, alors un être humain ne peut pas savoir si on a un modèle ou non ; mais la clé n'est pas dans dénombrable ou non, mais dans la définissabilité, IR n'est pas dénombrable, pourtant on sait que (IR, +) est un groupe. A l'inverse, on peut démontrer (théorème de Tennenbaum dans mon document sur l'arithmétique) qu'un modèle dénombrable non standard de Peano est de la forme IN + QZ pour l'ordre, mais + et . ne peuvent y être récursifs (autrement dit on ne peut pas les définir), cela n'empêche pas ces modèles "d'exister".

Ce "on sait" est une propriété que tout modèle doit avoir pour avoir l'étiquette "modèle", ou est-ce une propriété qui découle d'aspects plus fondamentaux du concept de modèle.

Comme je viens de l'expliquer "on sait" était maladroit, ce qui est nécessaire c'est l'existence du sous-ensemble, si il est définissable, alors "on sait" et on peut vérifier (cela peut rester très compliqué), à l'inverse si ce sous-ensemble n'est pas définissable, alors certaines propriétés ne seront pas accessibles à un être humain qui pourra donc très bien ne pas savoir si telle proposition est vraie ou non dans ce modèle, mais ce n'est pas parce que cette information est inacessible qu'elle n'existe pas.

La question de base est : est-ce que les formules atomiques sont vraies ou fausse dans telle structure (à la limite, je ne sais pas encore si j'ai un modèle, et je ne m'intéresse même pas à la théorie, je ne me préoccupe que du langage et de son interprétation), autrement dit (toujours avec le même exemple), est-ce que (a, b) appartient à R ou non, peut-être que "on ne sait pas" répondre à cette question parce que R n'est pas définissable, n'empêche que, à l'aide du tiers exclu, je peux affirmer que l'une de ces deux hypothèses est correcte (et pas l'autre).

"ce modèle" renvoie à N comme modèle ?

Oui

Autre point : ici comme dans le message d'avant, est utilisée la relation "dans" entre "formule" (ici) ou "proposition" (avant) et modèle.

Comme je n'arrive toujours pas à cerner le mot "modèle", je n'arrive pas à voir un modèle comme ayant dedans des formules.

La formule n'est pas dans le modèle, elle est vraie ou fausse dans le modèle.

[Médiat]

Par exemple un modèle des axiomes de Peano est une structure de Dedeking <A, f, a> ou A est un ensemble, f une fonction défini sur A et a ∈ A, qui satisfait tout les axiomes. La structure de Dedeking <IN,s,0> (ou s est la fonction successeur) est un modèle des axiomes de Peano. Il semble que Dedeking est montré que deux structures de Dedeking quelconques sont isomorphes. Autrement dit ces conditions définissent IN à l'isomorphisme prés.

Deux points importants :
1) "Axiomes de Peano" est imprécis, genéralement on désigne ainsi les axiomes de l'arithmétique, ce qui n'est pas le cas dans votre exemple

2) La structure de Dedekind dont vous parlez (et qui permet de démontrer l'unicité à isomorphisme près) est une structure (totale) du 2^nd ordre et non du 1^er, ce qui change beaucoup de choses (pas de théorème de complétude par exemple).

[invité576543]

Un esquisse, encore assez floue, se présente à mon esprit. Je vais reformuler... Un modèle est une collection de "choses", dont on peut parler avec des formules, et telle que toute formule ou sa négation soit "vraie".

[Les formules, elles, sont des chaînes de symboles respectant un langage, et des formules particulières (axiomes) engendrent par un processus mécanique ("démonstration") un sous-ensemble particulier de formules ("démontrables").]


(Ce n'est pas la partie formelle qui me pose problème, c'est le concept de modèle.)

Vu comme cela, il serait bien une exigence pour "être un modèle" qu'une notion de "formule vraie" "existe", et que le tiers exclus s'applique. (Les mots "notion" et "existe" sont flous, dans cette esquisse. Sans oublier "collection" et "choses" )

Mais on peut travailler avec des "collections" qu'on suppose être des modèles, sans en être sûr... (Et par exemple, l'absence de modèle dont on serait "sûr" pour ZFC ferait qu'on "ne sait pas" si ZFC est cohérente ??)

C'est cohérent avec une compréhension ?