Comparaison de logiques différentes

[invitef591ed4b]

Existe-t-il un moyen de comparer la fécondité mathématique de différentes logiques (classique, intuitionniste, multivalente, modale, paraconsistante, floue...) ?

Plus précisément :

• Peut-on hiérarchier les logiques suivant une relation d'inclusion ? (J'ai lu que la logique intuitionniste contient la classique, par exemple.)

• Y a-t-il une notion de "fécondité" ou de "puissance" associée à chaque logique, de sorte qu'on puisse les comparer ? Par "fécondité" d'une logique, j'entends intuitivement l'ensemble des propositions mathématiques démontrables avec cette logique. J'imagine que rejeter le tiers exclus, c'est déjà mettre une croix sur toutes les preuves par l'absurde, et donc c'est être potentiellement "moins fécond".
-----

[shokin]

Pas d'autres meilleurs conseils que l'expérimentations de théorèmes.



Si une logique "contient" une autre, n'est-ce pas en fait une théorie qui engloble une autre (qui n'en est, en fait, qu'un particulier) ?




Shokin

[invitef591ed4b]

Si une logique "contient" une autre, n'est-ce pas en fait une théorie qui engloble une autre (qui n'en est, en fait, qu'un particulier) ?

Pas tout à fait je pense : je ne parle pas de systèmes formels différents dans une même logique, je parle de logiques différentes. Une logique qui englobe une seconde signifierait que toute déduction formulée dans la seconde, est reformulable dans la première (mais pas vice-versa).

J'ignore si c'est pertinent ce que je dis...

Une question est la suivante : peut-on faire autant de maths avec une logique alternative qu'avec la logique classique ?

[Matmat]

Existe-t-il un moyen de comparer la fécondité mathématique de différentes logiques (classique, intuitionniste, multivalente, modale, paraconsistante, floue...) ?

Plus précisément :

• Peut-on hiérarchier les logiques suivant une relation d'inclusion ? (J'ai lu que la logique intuitionniste contient la classique, par exemple.)

• Y a-t-il une notion de "fécondité" ou de "puissance" associée à chaque logique, de sorte qu'on puisse les comparer ? Par "fécondité" d'une logique, j'entends intuitivement l'ensemble des propositions mathématiques démontrables avec cette logique. J'imagine que rejeter le tiers exclus, c'est déjà mettre une croix sur toutes les preuves par l'absurde, et donc c'est être potentiellement "moins fécond".

Remarque que:

(1) la logique classique admet le principe du tiers exclus (et on y fait des démonstrations par l'absurde)
(2) la logique intuitioniste rejette le principe du tiers exclus (on n'admet pas les démonstrations par l'absurde)

Tu dis rejeter le tiers exclus c'est etre moins fécond ... autrement dit en tenant compte de 1 et 2 que la logique intuitioniste est moins féconde que la classique, or tu as lu que la logique intuitioniste contenait la logique classique .

[A voir en vidéo sur Futura]

[invite73192618]

"L'univers logique" dans lequel tel ou tel principe n'existe pas (par exemple le tiers exclus) ne devrait-il pas être plus souple, et donc plus riche, qu'un univers logique qui le possède?

[Matmat]

Oui,

Ce qui rend "l'univers logique" intuitioniste plus riche que "l'univers logique" classique n'est pas la fécondité telle que la définit Sephi ... Du moins sa définition intuitive de la "fécondité d'une logique" ne répond pas au but qu'il s'est fixé de hierarchisé les logiques par ordre corissant du nombre de formules démontrables , il faut aussi tenir compte d'abord du nombre de formule diverses formulables avec une logique donnée .

ex: quand "A" est une formule démontrée , la forumle "A ou T", où T est une tautologie n'est pas une formule différente de A , il faut considérer qu'en réalité il y a une seule formule démontrée ( et non 2 ) , considérer que ce sont deux écritures d'une meme formule et non considérer que 2 formules ont été démontrés . c'est sans doute ce que n'a pas tenu compte Sephi puisque
en logique classique , quand "A" est une formule démontrée , la forumle "non(nonA)" est une formule démontrée et inversement , et comme ci dessus elle n'est pas une formule différente de A ! Une démonstration de l'une est une démonstration de l'autre , et inversement . Il faut donc considérer qu'il n'y a en réalité qu'une seule formule démontrée ! ( et non 2 )

Par contre , en logique intuitioniste , on peut avoir "non(nonA)" démontrée et "A" non démontrée ... Il y a donc soit 0,1, ou 2 formules démontrées car "non(nonA)" n'est pas qu'une simple réécriture de A ,comme l'est "A ou T" par exemple , mais bel et bien une formule réellement différente de A qui signifie vraiment quelque chose de différent de A .

Ce qui rend "l'univers logique" intuitioniste plus riche que "l'univers logique" classique c'est la plus grande diversité des formules formulables à partir d'une ou plusieurs formules données , finalement en nombres de formules démontrés à partir d'une ou plusieurs formules données la logique intuitioniste contient autant ou plus de formules démontrés que la classique, elle ne peut pas en contenir moins . "l'univers" intuitioniste contient bien "l'univers" classique bien que la critère de "fécondité" , tel qu'il est défini par Sephi, plaide pour le contraire (il manque quelque chose dans sa définition de la "fécondité" pour qu'on puisse s'en servir comme critère d'inclusion des univers logiques ) .

[invitef591ed4b]

Matmat > J'ai bien conscience de ce que tu dis, mais je ne sous-entendais pas que l"« inclusion » au sens où la logique intuitionniste contient la logique classique, est synonyme de "la logique intuitionniste sait démontrer tout ce que démontre la classique".

Je sais pas comment formuler précisément la chose... Par "être contenu dans", j'entends qqch comme "être compatible avec, mais plus restreint que". Et "plus restreint que" pourrait signifier "avoir plus d'axiomes que". Dans ce sens, c'est alors naturel qu'avec plus d'axiomes, on sait démontrer plus de choses. C'est bizarre comme inclusion mais bon...

[invite73192618]

Ah ok, je n'avais pas bien compris ton message précédent (@matmat). Que penses-tu alors de cette phrase trouvé dans un article de wikipedia, qui semble utiliser "puissance" avec une définition similaire au "fécondité" de sephi?

D’autres théories, qui sont soit moins puissantes que les précédentes, parce qu’elles refusent les constructions ensemblistes trop audacieuses (théories constructivistes, intuitionnistes, finitaires, ...), soit plus puissantes parce qu’elles les complètent avec d’autres axiomes (axiome de constructibilité, axiomes des très grands ensembles, ...)

EDIT croisement

[Matmat]

Ah ok, je n'avais pas bien compris ton message précédent (@matmat). Que penses-tu alors de cette phrase trouvé dans un article de wikipedia, qui semble utiliser "puissance" avec une définition similaire au "fécondité" de sephi?


EDIT croisement

On veut comparer des logiques,
Pour comparer 2 logiques, il me parait indispensable de les "tester" sur des bases axiomatiques égales.

Par exemple une théorie a 3 axiomes A,B,C , on décide d'en déduire des théorèmes, et selon la logique que l'on choisira les théorèmes déduits à partir de la meme base axiomatique différeront.

Laquelle, de la logique intuitioniste ou de la logique classique, permet de déduire le plus grand nombre de théorèmes (non équivalents) à partir d'une meme base axiomatique ?

Je répond que c'est l'intuitioniste, et une facon de s'en convaincre est de construire un graphe entre les théorèmes de la théorie obtenue à partir de la logique classique (Tc) et ceux obtenues à partir de la logique intuitioniste (Ti)...

Dans ce graphe, on pourra toujours faire une flèche d'un Tc vers un Ti avec la non-non traduction de Godel-Kolmogorov.

Inversement, je ne vois pas comment on pourrait toujours faire une flèche de tout Ti vers un Tc sans faire pointer plusieurs flèche sur un meme Tc, par exemple (A et B) est une théorème pour l'intuitioniste, ainsi que non(non(A etB)) puisque (A et B) --> non(non(A etB)) , et il ne lui est pas équivalent . la flèche pourra donc aller du (A et B) intuitioniste vers le (A et B) classique , mais aucune flèche ne pourra partir du non(non(A etB)) intuitioniste vers un théorème classique n'ayant pas déjà de flèche pointé sur lui, en effet non(non(A etB)) classique est "déjà pris" puisque c'est,pour le classique, le meme que (A et B) , qui a déjà une flèche pointé sur lui .

Conclusion: ce graphe est une injection non surjective des Tc sur les Ti ...

Autrement dit la logique intuitioniste permet de construire plus de théorèmes non équivalents que le classique à partir d'une base axiomatique donnée.

[invite73192618]

Ok ton point me parait clair. Néanmoins, le critère "plus grand nombre de théorème" me titille un peu. J'imagine que tous les théorèmes possibles d'une logique particulière n'ont pas forcément le même intérêt pour un mathématicien. Imaginons qu'on ai un problème particulièrement difficile à résoudre. Est-ce qu'à ton avis on aurait à priori plus de chance de le résoudre dans une logique comportant peu d'axiomes et beaucoup de théorèmes possibles (disons l'intuitioniste) ou dans un logique comportant plus d'axiomes et moins de théorèmes possibles (disons la classique)?

[Médiat]

Conclusion: ce graphe est une injection non surjective des Tc sur les Ti ...

Ton explication ne m'amène pas à cette conclusion :
D'abord je ne vois pas bien la relation d'équivalence dont tu parles, en effet tous les théorèmes "vrais" d'une théorie sont équivalents (au sens de l'équivalence logique), de même pour les "faux", quant à utiliser une notion "d'équivalence tautologique", il faudrait la définir, ce qui risque de ne pas être facile (tous les théorèmes d'une théorie sont des conséquences tautologiques des axiomes).

Je comprends bien ton souci de ne pas embarquer non(non A) avec A (en logique classique), mais pourquoi le faire en logique intuitioniste alors que l'on a tautologiquement que A entraîne non (non A) ?

Que le théorème non (non A) n'apporte rien par rapport au théorème A (Logique classique), je suis d'accord, mais est-ce que (A ou B) apporte quelque chose à A quelque soit B (et pourtant il n'y a pas "équivalence") ?

Ma conclusion serait plutôt : la Logique intuitioniste permet d'exhiber plus de propositions (modulo une relation d'équivalence à définir) : à partir de la proposition A on peut fabriquer A, non A et non (non A), c'est à dire une de plus qu'en logique classique, mais une proposition n'est pas forcément un théorème.

Imaginons qu'on ai un problème particulièrement difficile à résoudre. Est-ce qu'à ton avis on aurait à priori plus de chance de le résoudre dans une logique comportant peu d'axiomes et beaucoup de théorèmes possibles (disons l'intuitioniste) ou dans un logique comportant plus d'axiomes et moins de théorèmes possibles (disons la classique)?

J'ai peur qu'il y ait confusion entre deux niveaux, celui de la logique (avec ses règles d'inférences) et la théorie (avec ses axiomes). En tout état de cause, il me semble que "plus" une logique a de règles d'inférence et "plus" on peut démontrer de théorèmes (aucune règle ==> seuls les axiomes sont des théorèmes) ; de la même façon "plus" une théorie consistante a d'axiomes indépendants et "plus" on peut démontrer de théorèmes (on supprime au moins une proposition indécidable).

[Matmat]

Ton explication ne m'amène pas à cette conclusion :
D'abord je ne vois pas bien la relation d'équivalence dont tu parles, en effet tous les théorèmes "vrais" d'une théorie sont équivalents (au sens de l'équivalence logique), de même pour les "faux", quant à utiliser une notion "d'équivalence tautologique", il faudrait la définir, ce qui risque de ne pas être facile (tous les théorèmes d'une théorie sont des conséquences tautologiques des axiomes).

Je comprends bien ton souci de ne pas embarquer non(non A) avec A (en logique classique), mais pourquoi le faire en logique intuitioniste alors que l'on a tautologiquement que A entraîne non (non A) ?

Je suis d'accord, on peut choisir d'autre relation d'équivalence ...
En tout cas, il m'a semblé qu'il fallait une relation équivalence pour que l'énoncé de Sephi soit complet.
Je propose la suivante : Deux théorèmes A et B sont équivalent ssi "A entraine B" et "B entraine A".

Que le théorème non (non A) n'apporte rien par rapport au théorème A (Logique classique), je suis d'accord, mais est-ce que (A ou B) apporte quelque chose à A quelque soit B (et pourtant il n'y a pas "équivalence") ?

Oui, quand on doit conclure B dans le cas où nonA est démontré.

Ma conclusion serait plutôt : la Logique intuitioniste permet d'exhiber plus de propositions (modulo une relation d'équivalence à définir) : à partir de la proposition A on peut fabriquer A, non A et non (non A), ...

D'accord.

...c'est à dire une de plus qu'en logique classique,...

OUI ! toujours d'accord.

Quand une théorème T est démontré en logique classique alors nécessairement on a non(nonT) démontré en logique intuitioniste (argument que j'ai oublié de dire mais sans lequel la non-non traduction de Godel ne serait pas):
donc avec la logique intuitioniste on obtient AU MOINS autant de théorème qu'avec la logique classique... et quand,éventuellement, T est démontrable aussi en logique intuitioniste (ca arrive) , ca lui fait un théorème de plus.
Pour chaque théorème obtenu avec la logique classique , la logique intuitionniste peut en obtenir 1 ou 2 .

...mais une proposition n'est pas forcément un théorème.

J'ai considéré qu'on comparait "le potentiel" des logiques et non le nombre de propositions démontrables dont on a bien voulus faire des théorèmes d'une théorie... Sinon le problème dépend plus des théories que des logiques , or on voulait comparer les logiques.

... (aucune règle ==> seuls les axiomes sont des théorèmes) ...

mais aussi :
(une infinité de règles ==> tous les théorèmes sont équivalents aux axiomes)

[Médiat]

Je propose la suivante : Deux théorèmes A et B sont équivalent ssi "A entraine B" et "B entraine A".

Et c'est quoi "entraîne" (dans chacune des logiques) ?

(une infinité de règles ==> tous les théorèmes sont équivalents aux axiomes)

Dans la mesure où les axiomes sont vrais et les théorèmes aussi les théorèmes sont toujours équivalents aux axiomes, quelque soit le nombre de règles d'inférence.

[Matmat]

Et c'est quoi "entraîne" (dans chacune des logiques) ?

c'est l'implication (de chacune des logiques)

Dans la mesure où les axiomes sont vrais et les théorèmes aussi les théorèmes sont toujours équivalents aux axiomes, quelque soit le nombre de règles d'inférence.

Que les théorèmes soient vrais n'est pas suffisant pour affirmer leur équivalence avec les axiomes.

Les axiomes ne sont en général pas équivalent aux théorèmes , les axiomes entrainent les théorèmes mais les théorèmes n'entrainent pas les axiomes.

Pour qu'il y ait équivalence il faut qu'il y ait implication dans les deux sens.

[Médiat]

c'est l'implication (de chacune des logiques)

Que les théorèmes soient vrais n'est pas suffisant pour affirmer leur équivalence avec les axiomes.

Regarde le tableau de vérité de l'implication : Si le théorème T est "vrai", comme l'axiome A est "vrai" par définition alors T entraîne A et A entraîne T (puisque Vrai entraîne Vrai).

En fait le problème vient de la difficulté à définir cette fameuse relation d'équivalence dont je parlais ce matin (à 6h40), et qui est sans doute plus lié à la notion de démonstration (domaine de prédilection de la logique intuitionniste) qu'à la notion de valeur de vérité (celui de la logique classique).

[Matmat]

Regarde le tableau de vérité de l'implication : Si le théorème T est "vrai", comme l'axiome A est "vrai" par définition alors T entraîne A et A entraîne T (puisque Vrai entraîne Vrai).

En fait le problème vient de la difficulté à définir cette fameuse relation d'équivalence dont je parlais ce matin (à 6h40), et qui est sans doute plus lié à la notion de démonstration (domaine de prédilection de la logique intuitionniste) qu'à la notion de valeur de vérité (celui de la logique classique).

Oui,en effet je n'ai pas pensé à la difficulté de définir la relation d'équivalence commune. La piste que j'ai lancée ne tient pas la route à cause de ca.
Je n'ai plus d'idée sur le sujet...