conséquences de la complétude et de l'incomplétude

[invite4492c379]

Ok alors, encore une définition :



membres-liglab.imag.fr/michel.levy/TL/poly.pdf

Dans le même document :

1.1 Vocabulaire
On appelle vocabulaire (ou alphabet) un ensemble fini quelconque. Les éléments d’un vocabulaire sont appelés
lettres, caractères ou symboles. On note #V le nombre d’éléments d’un vocabulaire V.

-----

[Médiat]

Non la logique du premier ordre est couverte, l'alphabet est fini. Si vous le désirez, je peux prendre le temps pour la décrire pour en parler plus sérieusement.

Ok, donnez moi l'exemple pour un langage contenant un nombre dénombrable de prédicats n-aires pour chaque n dans IN.

[invite4492c379]

Il est clair que "langage formel" est une expression polysémique, tant que des intervenants ne prendront pas soin de préciser (précision que j'ai justement donné pour mon compte dans mon message 148) dans quel sens ils l'utilisent, ce fil continuera de ressembler à une partie de ping pong stérile.

Quant à chercher quel est la "bonne définition", c'est une question religieuse sans aucun intérêt.

Le point où je veux en venir : des définitions précises et claires se dégagent dans le cadre de la théorie des langages et qui sont enseignées au moins depuis les années 90. Elle est féconde, mais récente. Utilisons donc son vocabulaire pour enfin arriver à se comprendre (OK ça prend du temps).

[Médiat]

Utilisons donc son vocabulaire pour enfin arriver à se comprendre (OK ça prend du temps).

Non, parce que le point qui m'intéresse ici est celui des mathématiques classiques ou infinitaires et que votre définition, toute honorable qu'elle soit, ne couvre pas ces cas.

[Amanuensis]

La confusion est continue entre ce dont peuvent (via une sémantique adaptée) parler les mathématiques et un langage formalisant les mathématiques construites effectivement par les humains.

Les échanges de sourds peuvent durer longtemps sur cette base.

C'est d'ailleurs une disjonction usuelle, entre l'infini actuel allégrement manipulé (symboliquement) par les mathématiques (et les mathématiciens, pour lesquels le finitaire est un terrain de jeu bien trop limité), et le monde concret désespérement limité à l'infini potentiel (et encore).

[invite6754323456711]

Bonjour,

A la lecture des échanges j'ai comme l'impression que c'est une notion de contexte qui permet de lever les ambiguïtés car donne des sens différents aux syntaxes. Donc le sens/sémantique aurait une dimension orthogonale à la syntaxe. Il n'y aurait donc pas une définition plus abstraite qui unifierait les deux facettes que sont la sémantique et la syntaxe ? J'avais cru comprendre que concernant le problème mathématique de la décidabilité Turing avait établie une équivalence avec la théorie des automates sous-ensemble de la théorie des langages formels ?

Patrick

[invite4492c379]

Ok, donnez moi l'exemple pour un langage contenant un nombre dénombrable de prédicats n-aires pour chaque n dans IN.

V_t={'P','a','_','(',')','0','1', '2','3','4','5','6','7','8','9 ',','}

V_n = {CHIFFRE19,CHIFFRE,NOMBRE,ARGU MENT,LISTEARGUMENT,NOMPREDICAT }

CHIFFRE19 = '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
CHIFFRE = '0' | CHIFFRE19
NOMBRE = CHIFFRE | CHIFFRE19 CHIFFRE

ARGUMENT = 'a''_'NOMBRE
NOMPREDICAT = 'P''_'NOMBRE

LISTEARGUMENT = ARGUMENT | ARGUMENT',' LISTEARGUMENT

PREDICAT = NOMPREDICAT'('')' | NOMPREDICAT'('LISTEARGUMENT')'

[invite7863222222222]

Certains trahissent seulement, les bonnes intentions de définitions qui étaient les leur avant, de restreindre inutilement.

Moi ce que je dis, c'est qu'il me semble douteux de croire que lorsqu'on donne l'alphabet {'a', 'b'} par exemple on explicite quoique ce soit qui soit plus précis que {'0', '1', '2', ...}, tout dépend de ce que l'on considére exister. Dans tous les cas, pour les symboles , ce ne sont aps des pixels sur un écran, mais une abstraction pour dénoter quelque chose. Rien n'empêche au vocabulaire de s'adapter à ce qui est dénoté, et qu'il faille comprendre différemment les symboles (notamment le "...") suivants les cas.

[Médiat]

Oui, mais là ce ne sont pas des mathématiques, c'est juste un choix (que vous imposez) d'écriture des mathématiques : vous utilisez des tonnes de symboles qui n'existent même pas dans le langage dont je parlais. Pour vous est un mot de longueur 5 qui utilise 4 symboles du vocabulaire, pour moi, mathématicien, il s'agit d'un seul symbole.

Par exemple avec cette façon de faire, vous ne ferez pas de différence entre la formule infinitaire définissant les groupes de torsion et une banale formule du permier ordre, or les propriétés des théories utilisant ces formules sont fondamentalement différentes.

C'est une évidence absolue d'une banalité telle qu'il ne devrait même être nécessaire de le rappeler que quoi que j'écrive ce sera une chaîne finie sur un alphabet fini, mais justement, en mathématiques les choses sont différentes (La classe des groupes de torsion n'est pas une classe élémentaires, c'est quand même un résultat fondamental, et cela montre bien que cette formule est fondamentalement différente de la formule définissant la commutativité, par exemple).


Et vous n'avez pas exprimé qu'il y avait une infinité de prédicats n-aires pour chaque entier.

[invite4492c379]

Certains trahissent seulement, les bonnes intentions de définitions qui étaient les leur avant, de restreindre inutilement.

Moi ce que je dis, c'est c'est une illusion de croire que lorsqu'on donne l'alphabet {'a', 'b'} par exemple on explicite quoique ce soit qui soit plus précis que {'0', '1', '2', ...}, tout dépend de ce que l'on considére exister. Dans tous les cas, pour les symboles , ce ne sont aps des pixels sur un écran, mais une abstraction pour dénoter quelque chose. Rien n'empêche aux symboles de s'adapter à ce qui est dénoter.

1. plus concis n'est pas plus précis. Il n'y a pas restriction, il y a définition. Sortir de la définition est parler d'autre chose que ce qui est défini. J'ai fait remarquer que alphabet dénombrable se réduit à alphabet fini.

2. Est-ce une illusion de croire que «{'0', '1', '2', ...} permette plus d'expressivité que {'a','b'}» ?
oui si le premier ensemble est dénombrable.

[invite4492c379]

Oui, mais là ce ne sont pas des mathématiques, c'est juste un choix (que vous imposez) d'écriture des mathématiques : vous utilisez des tonnes de symboles qui n'existent même pas dans le langage dont je parlais. Pour vous est un mot de longueur 5 qui utilise 4 symboles du vocabulaire, pour moi, mathématicien, il s'agit d'un seul symbole.

Par exemple avec cette façon de faire, vous ne ferez pas de différence entre la formule infinitaire définissant les groupes de torsion et une banale formule du permier ordre, or les propriétés des théories utilisant ces formules sont fondamentalement différentes.

C'est une évidence absolue d'une banalité telle qu'il ne devrait même être nécessaire de le rappeler que quoi que j'écrive ce sera une chaîne finie sur un alphabet fini, mais justement, en mathématiques les choses sont différentes (La classe des groupes de torsion n'est pas une classe élémentaires, c'est quand même un résultat fondamental, et cela montre bien que cette formule est fondamentalement différente de la formule définissant la commutativité, par exemple).


Et vous n'avez pas exprimé qu'il y avait une infinité de prédicats n-aires pour chaque entier.

Ce sont des mathématiques car jusqu'à preuve du contraire l'informatique fondamentale est un domaine inclus dans les mathématiques. Il s'agit d'une définition d'un langage formel, je n'y attache aucune sémantique. Je me borne à appliquer les définitions de la théorie des langages formels.
Pour préciser votre « pour moi, mathématicien, il s'agit d'un seul symbole» je dirais que dans vos lectures il est usuels de nommer cela un symbole. Or si nous parlons de langages formels ce n'en est plus un mais effectivement un mot longueur 6 construit sur un alphabet fini.

Pour la dernière partie, toute phrase de la forme (je passe en langage naturel, le Français) : un 'P' suivi d'un '_', puis d'un entier puis d'un '(' puis de n arguments séparés par des ',' le dernier argument n'étant pas suivi d'un ',' mais d'un ')' sera reconnu par la règle PREDICAT et ce pour tout n, le nombre d'arguments.

[invite7863222222222]

photon57, tant que vous me disqualifierez avec l'argument que je ne respecte pas les définitions, vous sous estimerez mes propos. Et je ne peux vous forcer de rien, dans ces conditions, si je n'ai pas réussi à vous exprimer ce que je veux dire, tant pis.

Mais je continue de dire qu'il est restrictif de limiter les symboles à une finitude. C'est parceque vous croyez que les symboles sont des pixels sur un écran, ce que pour moi ils ne sont pas. Je n'ai pas les moyens de vous en dire plus prenez le, pour ce que ca vaut.

[Médiat]

Ce sont des mathématiques car jusqu'à preuve du contraire l'informatique fondamentale est un domaine inclus dans les mathématiques. Il s'agit d'une définition d'un langage formel, je n'y attache aucune sémantique. Je me borne à appliquer les définitions de la théorie des langages formels.

Je n'ai pas voulu dire que ce que vous faisiez ne participait pas aux mathématiques (désolé si vous l'avez compris ainsi), mais que ce que vous aviez écrit n'était la mathématique associé au langage que j'ai définit, votre partie en gras, confirmant ce que je viens d'écrire.

Pour préciser votre « pour moi, mathématicien, il s'agit d'un seul symbole» je dirais que dans vos lectures il est usuels de nommer cela un symbole. Or si nous parlons de langages formels ce n'en est plus un mais effectivement un mot longueur 6 construit sur un alphabet fini.

Pas dans mes lectures, mais pour tous les logiciens du monde Tant que vous ne voudrez pas admettre qu'il existe plusieurs définitions de "langage formel" et que vous ferez semblant de croire que tout le monde l'utilise dans le même sens que vous, nous n'avancerons pas (je me suis bien gardé d'utiliser cette expression dans le sens qui m'intéresse depuis quelques posts pour ne parler que de mathématiques et de logiques mathématiques.

Il y a une différence entre écrire des mathématiques, ce que votre définition de "langage formel" fait sans doute très bien, et faire des mathématiques, ce qui peut nécessiter un vocabulaire infini même au premier ordre !

Pour la dernière partie, toute phrase de la forme (je passe en langage naturel, le Français) : un 'P' suivi d'un '_', puis d'un entier puis d'un '(' puis de n arguments séparés par des ',' le dernier argument n'étant pas suivi d'un ',' mais d'un ')' sera reconnu par la règle PREDICAT et ce pour tout n, le nombre d'arguments.

Certes, je sais lire, mais cela n'impose en rien d'avoir un nombre dénombrable de prédicats n-aires pour chaque entier.

[invite4492c379]

photon57, tant que vous me disqualifierez avec l'argument que je ne respecte pas les définitions, vous sous estimez ma réflexion.

Si c'est votre choxi de vous obstinez je ne peux vous forcer de rien.

Je continue de dire qu'il est restrictif de limiter les symboles à une finitude. C'est parceque vous croyez que les symboles sont des pixels sur un écran, ce que pour moi ils ne sont pas. Réfléchissez à cela. C'est tout ce que je peux vous dire. Je n'ai pas les moyens de vous en dire plus prenez le, pour ce que ca vaut.

Non le problème est plus profond.
Si l'alphabet sur lequel est construit un langage est dénombrable il n'y a pas de problèmes car on se réduit à un cas connu, celui des langages construits sur un alphabet fini.
Si l'alphabet sur lequel est construit un langage est infini indénombrable il y a peu d'intéret (pour l'instant) car le langage n'est pas exploitable ou applicable, car n'étant pas calculable. Mais ils existent ... sans être des langages formels.
Il y a une grande différence entres langages et langages formels,

Si j'insiste sur la définition c'est uniquement pour savoir de quoi on parle.

[invite4492c379]

(...)
Pas dans mes lectures, mais pour tous les logiciens du monde Tant que vous ne voudrez pas admettre qu'il existe plusieurs définitions de "langage formel" et que vous ferez semblant de croire que tout le monde l'utilise dans le même sens que vous, nous n'avancerons pas (je me suis bien gardé d'utiliser cette expression dans le sens qui m'intéresse depuis quelques posts pour ne parler que de mathématiques et de logiques mathématiques.

Ce n'est pas *ma* définition.
Les mathématiques définissent plusieurs langages : formels, réguliers, contextuels, ...
Chacun de ces langages a des définitions, et des propriétés.

Il y a une différence entre écrire des mathématiques, ce que votre définition de "langage formel" fait sans doute très bien, et faire des mathématiques, ce qui peut nécessiter un vocabulaire infini même au premier ordre !

À nouveau ce n'est pas *ma* définition. Je ne nie pas que le vocabulaire est infini, mais il est toujours construit sur un alphabet fini.

Certes, je sais lire, mais cela n'impose en rien d'avoir un nombre dénombrable de prédicats n-aires pour chaque entier.

Peut-être pourriez-vous donner un contre-exemple dans ce cas ?

[invite7863222222222]

Si l'alphabet sur lequel est construit un langage est dénombrable il n'y a pas de problèmes car on se réduit à un cas connu

Peut-être mais je ne dis pas le contraire, je dis seulement qu'il n'y a rien d'obligé à vouloir réduire.

[invite4492c379]

J'ai déjà donné un exemple, est-ce que pour vous l'ensemble des mots du type "1,3,5, ... 0, 2,4,...." est dénombrable ?

On en revient toujours au-même. Pour répondre à cette question il va falloir être un peu plus précis :

* sur quel alphabet construit-on ces mots ?
* comment sont construits ces mots ?

[invite7863222222222]

On en revient toujours au-même. Pour répondre à cette question il va falloir être un peu plus précis :

* sur quel alphabet construit-on ces mots ?
* comment sont construits ces mots ?

J'ai édité mon message.

Mais j'ai déjà répondu à ces questions. Vous avez ce qu'il faut pour répondre à la question.

[Médiat]

À nouveau ce n'est pas *ma* définition. Je ne nie pas que le vocabulaire est infini, mais il est toujours construit sur un alphabet fini.

Une fois de plus vous ne parlez que de la façon d'écrire des mathématiques, c'est sans doute très intéressant, mais une fois de plus ce n'est pas ce dont je parle, et j'avoue que je ne sais plus comment vous le dire.

Si vous êtes d'accord pour appeler alphabet la liste des éléments atomiques d'un langage (formel dans votre sens, formalisé dans le mien), et non des éléments permettant leur écriture (ce qui revient au même dans votre cas, mais pas dans le mien), alors je vous affirme, mais pour la dernière fois, que la logique même classique du premier ordre autorise les alphabets infinis.

Peut-être pourriez-vous donner un contre-exemple dans ce cas ?

Vous n'avez pas écrit que le langage (au sens mathématique) possédait un nombre dénombrable de prédicats n-aires pour tout n, vous avez écrit qu'un prédicat pouvait avoir n arguments.

[invite4492c379]

Une fois de plus vous ne parlez que de la façon d'écrire des mathématiques, c'est sans doute très intéressant, mais une fois de plus ce n'est pas ce dont je parle, et j'avoue que je ne sais plus comment vous le dire.

Si vous êtes d'accord pour appeler alphabet la liste des éléments atomiques d'un langage (formel dans votre sens, formalisé dans le mien), et non des éléments permettant leur écriture (ce qui revient au même dans votre cas, mais pas dans le mien), alors je vous affirme, mais pour la dernière fois, que la logique même classique du premier ordre autorise les alphabets infinis.

C'est ce que j'essaye de faire comprendre : ce dont vous parlez ne correspond pas à un langage formel.

La description d'un langage n'a pas besoin de sémantique. Ça vous choque si j'écris :

A={0,1,2,3,4,5,6,7,8,9}

NOMBRE = 0|1|2|3|4|5|6|7|8|9
NPAIR = 0|3|6|9

ZERO = 1|2|3|4|5|6|7|8|9
CHIFFRE = ZERO | ZERO NOMBRE

PAIR = CHIFFRE NPAIR | NPAIR

Vous n'avez pas écrit que le langage (au sens mathématique) possédait un nombre dénombrable de prédicats n-aires pour tout n, vous avez écrit qu'un prédicat pouvait avoir n arguments.

Il y a un nombre dénombrable de termes de la forme P_«un entier» , un pour chaque entier.
Chaque P_«un entier» peut accepter un nombre entier quelconques d'arguments.

pour tout n et pour tout k :
P_n()
P_n(a1)
P_n(a1,a2)
...
P_n(a1,...,ak)
.....

[invite7863222222222]

La description d'un langage n'a pas besoin de sémantique. Ça vous choque si j'écris :

A={0,1,2,3,4,5,6,7,8,9}

Mais c'est quoi pour vous 0,1,2,3,4,5,6,7,8,9 ?

[Médiat]

ce dont vous parlez ne correspond pas à un langage formel.

Si, mais pas avec votre acception, et vous refusez de faire la différence que je vous suggère depuis le message 148 en acceptant que cette expression est polysémique, et elle l'ai que vous le vouliez ou non.

Chaque P_«un entier» peut accepter un nombre entier quelconques d'arguments.

Mais ce n'est pas ce que je vous ai demandé.

J'ai bien compris qu'il existait une théorie des "langages formels" qui sont des chaines finies sur des alphabets finis qui permettent d'écrire beaucoup de choses, y compris des mathématiques, mais en gommant, tout ce qui, moi, m'intéresse dans les langages mathématiques qui peuvent être sur un vocabulaire infini, et dont certaines caractéristiques fondamentales sont gommées si on se contente de les écrire.

Je ne vous oblige, évidemment pas, à avoit les mêmes intérêts que moi, mais ne m'imposez pas les votres !

Ce sujet s'arrête là pour moi (sauf à répondre à des questions précises, éventuellement).

[invite4492c379]

Mais c'est quoi pour vous 0,1,2,3,4,5,6,7,8,9 ?

les éléments de l'ensemble A.

[invite6754323456711]

La confusion est continue entre ce dont peuvent (via une sémantique adaptée) parler les mathématiques et un langage formalisant les mathématiques construites effectivement par les humains.

C'est d'ailleurs une disjonction usuelle, entre l'infini actuel allégrement manipulé (symboliquement) par les mathématiques (et les mathématiciens, pour lesquels le finitaire est un terrain de jeu bien trop limité), et le monde concret désespérement limité à l'infini potentiel (et encore).

Si on y regarde de prêt, tout semble revenir à une manipulation (algèbre) de symbole en nombre fini, même si cette symbolique désigne dans notre esprit une entité infini.

Patrick

[invite6754323456711]

Bonjour,

La je ne perçois qu'un nombre fini de symbole. Cela ne fait pas sens pour moi. Pour faire sens il faut une conscience initiés qui l'interprète. Ce qui me conduit à dire que le langage formel ne peut suffire à tout exprimer sans l'aide d'une sémantique qui elle semble propre à un domaine donné et qui en fait sa spécificité.

C'est ce que je comprends de ce qu'exprime Médiat.

Patrick

[invite7863222222222]

Et je confirme aussi que j'ai limpression que c'est aussi ce que j'ai exprimé.