Arithmétique

[Médiat]

Bonjour,

Désolé d'avoir mis tant de temps à répondre.

Je n'ai pas trouvé de manière très élégante de revenir sur les démonstrations concernant la bijectivité (cf. supra), aussi je vais me contenter de préciser certains non-dits qui auraitent dus être explicites.

Soit , c'est à dire un élément du modèle , et non un entier "naïf" servant d'abbréviation.

On peut écrire , et en appliquant la définition de la fonction f, on obtient :
où, cette fois-ci n est bien une abréviation

Après cette remarque, injectivité et surjectivité sont évidentes à démontrer (par exemple si , cela veut dire que pour un certain n et donc a = f(n)).

Amicalement,

Médiat
-----

[karlp]

Bonjour,

Désolé d'avoir mis tant de temps à répondre.

Je n'ai pas trouvé de manière très élégante de revenir sur les démonstrations concernant la bijectivité (cf. supra), aussi je vais me contenter de préciser certains non-dits qui auraitent dus être explicites.

Soit , c'est à dire un élément du modèle , et non un entier "naïf" servant d'abbréviation.

On peut écrire , et en appliquant la définition de la fonction f, on obtient :
où, cette fois-ci n est bien une abréviation

Après cette remarque, injectivité et surjectivité sont évidentes à démontrer (par exemple si , cela veut dire que pour un certain n et donc a = f(n)).

Amicalement,

Médiat

Bonjour Médiat (je n'ai pas laissé tombé ma lecture -je suis lent mais tétu - mais j'ai peu de temps, malheureusement)

Je crois que je comprends bien la démonstration de la surjectivité. Avec beaucoup de prudence je dirais que c'était la voie que je tentais d'emprunter.
J'aborde l'exercice suivant .
Cordialement.

[karlp]

Je ne vous étonnerai pas, cher Médiat, en vous disant que je "coince" déjà !
(je suis sur l'exercice 6)
Avec l'indication que vous proposez (cf"même chose que pour cc1 à peu de chose près"]) je soupçonne qu'en substituant la variable "a" aux occurences du 0 de MI , on peut établir cette démonstration du caractère bijectif de f (de Z dans cc3).
Je ne comprends pas la "portée" de cette démonstration : je croyais que les composantes connexes de type CC3 ne pouvaient pas constituer des modèles pour PréA, dans la mesure où elles ne contiennent pas le 0.

D'où mes questions :
Est-ce que le fait que f soit un isomorphisme suffit et est nécessaire pour montrer qu'une composante connexe constitue un modèle pour la théorie considérée ?
Si oui, cc3 est-elle un modèle pour PréA ?
ou bien: l'exercice devrait -il conduire à la démonstration du fait que f n'est pas bijective ?
ou encore: le problème vient-il du fait que 0 dans Z est successeur , contrairement à ce que dit l'axiome 1 ?

[Autre question: Vous écrivez " soit cc3 la composante connexe non vide de type CC3, etc. définie par:
f(0_IN)= a" : ne doit-on pas écrire f(0_z) ?]

- Je suis perdu

[Médiat]

Avec l'indication que vous proposez (cf"même chose que pour cc1 à peu de chose près"]) je soupçonne qu'en substituant la variable "a" aux occurences du 0 de MI , on peut établir cette démonstration du caractère bijectif de f (de Z dans cc3).

C'est cela.

Je ne comprends pas la "portée" de cette démonstration : je croyais que les composantes connexes de type CC3 ne pouvaient pas constituer des modèles pour PréA, dans la mesure où elles ne contiennent pas le 0.

Vous avez raison, l'idée ici n'est pas de démontrer que cc3 est un modèle de PréA, mais que si un modèle de PréA contient une ou des composantes connexes de type CC3, alors ces composantes connexes sont isomorphes à Z

Est-ce que le fait que f soit un isomorphisme suffit et est nécessaire pour montrer qu'une composante connexe constitue un modèle pour la théorie considérée ?

Donc non, cela montre que Z est isomorphe à ces composantes connexes, mais il a été démontré précédemment qu'un modèle de PréA contient une et une seule composante connexe de type CC1

Si oui, cc3 est-elle un modèle pour PréA ?

Donc non.

ou bien: l'exercice devrait -il conduire à la démonstration du fait que f n'est pas bijective ?

Donc non

ou encore: le problème vient-il du fait que 0 dans Z est successeur , contrairement à ce que dit l'axiome 1 ?

Ce fait suffit à conclure que Z ne peut pas être un modèle de PréA

[Autre question: Vous écrivez " soit cc3 la composante connexe non vide de type CC3, etc. définie par:
f(0_IN)= a" : ne doit-on pas écrire f(0_z) ?]

Vous avez parfaitement raison, il faut que je corrige le document .

[karlp]

Merci infiniment !

Je consigne vos remarques et précisions et vais poursuivre ma lecture avec grand plaisir.

[karlp]

Je crois qu'il y a une petite faute de frappe dans l'énoncé précédant l'exercice 7: "soit cc4 une composante connexe de cardinal p strictement inférieur à 0". Sauf erreur de ma part, le symbole a été inversé (?).

Si c'est le cas, alors je suis en mesure de "voir", c'est à dire de me faire une représentation intuitive, de la bijection. Je crains d'abuser en vous demandant votre démonstration.

Ne désespérez pas de l'étudiant que je suis redevenu grace à vous: j'ai très bien compris la démonstration du théorème 1.

Pour l'exercice 8, je ne vois pas en quoi la solution que vous donnez (en fin de page 5) n'est pas suffisante :vous rappelez que le groupe additif des classes résiduelles modulo 1 (qui ne contient donc que le 0, si je ne m'abuse ?) vérifie la formule "il existe un x, tel que s(x) = x".
[remarque purement secondaire et d'ordre strictement graphique :dans l'énoncé de l'exercice 8 le "forall" n'est pas converti en A renversé; cela ne nuit toutefois pas à la compréhension des plus indigents; je peux vous l'assurer]

[Médiat]

Je crois qu'il y a une petite faute de frappe dans l'énoncé précédant l'exercice 7: "soit cc4 une composante connexe de cardinal p strictement inférieur à 0". Sauf erreur de ma part, le symbole a été inversé (?).

Oui, vous allez m'aider à trouver toutes les fautes de frappe qui restent même après 20 relectures

Je crains d'abuser en vous demandant votre démonstration.

J'y reviendrai.

Pour l'exercice 8, je ne vois pas en quoi la solution que vous donnez (en fin de page 5) n'est pas suffisante :vous rappelez que le groupe additif des classes résiduelles modulo 1 (qui ne contient donc que le 0, si je ne m'abuse ?) vérifie la formule "il existe un x, tel que s(x) = x".

L'exercice 8 généralise à tous les p le point évoqué en bas de la page 5 qui n'est démontré que dans le cas p = 1.

[remarque purement secondaire et d'ordre strictement graphique :dans l'énoncé de l'exercice 8 le "forall" n'est pas converti en A renversé; cela ne nuit toutefois pas à la compréhension des plus indigents; je peux vous l'assurer]

Et paf encore une

[karlp]

(1) oui, vous allez m'aider à trouver toutes les fautes de frappe qui restent même après 20 relectures

(2)J'y reviendrai.


(3)L'exercice 8 généralise à tous les p le point évoqué en bas de la page 5 qui n'est démontré que dans le cas p = 1.

(1)Et paf encore une

(3) Je prends le temps d'y réfléchir

(2) Merci d'avance; il n'y a aucune urgence (je lis avec plaisir votre discussion sur le forum epistémologie)

(1) C'est un immense honneur pour moi; ça me donne le sentiment de vous dédommager un tout petit peu de la peine que vous vous donnez pour faire entrer la lumière dans mon obscurité intérieure.

J'ai avancé un peu et la page 6 me semble limpide (il faudra toutefois que j'aille voir de plus près les théorèmes auxquels vous vous référez) et -cela pourra sembler étrange- d'une beauté extraordinaire.

[Médiat]

Rassurez-vous je ne trouve absolument pas étrange, mais bien au contraire très agréable que vous trouviez de la beauté dans ces théorèmes ; je tiens les théorèmes de compacité, de Lowenheim-Skolem, de Los-Vaught et de Morley (sans oublier le théorème d'incomplétude de Gödel), comme de purs splendeurs.

Puisque vous en êtes à la page 6, je vous signale une faute de frappe déjà repérée, mais pas encore corrigée :
Il faut lire :
Une théorie T est dîte -catégorique si elle ne possède qu'un seul modèle de cardinal à isomorphisme près.

[karlp]

Bonjour Médiat

Je suis interrompu dans ma lecture, faute de pouvoir trouver une formulation pour moi satisfaisante du théorème de Lowenheim Skolem (le temps me manque et je ne lis que les textes brefs). J'ai du mal à relier ce que je lis avec la place que vous accordez à ce théorème dans votre article . En particulier je ne suis pas sûr du tout qu'il faille entendre le mot "dénombrable" dans le même sens que lorsque l'on parle de l'infini dénombrable. Je ne désespère pas.
J'enregistre et vous remercie pour votre correction.
Cordialement

[Médiat]

Bonjour karlp,

Le théorème de Lowenheim-Skolem dit deux choses :
1) toute théorie (logique classique du 1er ordre) qui admet un modèle infini, possède des modèles en tous les cardinaux infinis, c'est à dire possède une infinité de modèles non-isomorphes.
2) toute théorie qui admet des modèles finis aussi grand que l'on veut possède des modèles infinis.

Ce théorème permet de montrer, par exemple qu'il n'existe pas de théorie (logique classique du 1er ordre) dont les modèles sont les groupes (par exemple) finis (j'ai parler de ce point de vue là : http://forums.futura-sciences.com/ep...e-linfini.html).

Ce théorème permet aussi de montrer que si la théorie des ensembles est consistante, alors elle admet un modèle dénombrable dans lequel on peut définir l'ensembles des parties de IN (qui n'est donc pas dénombrable) comme sous-partie d'un ensemble dénombrable : http://forums.futura-sciences.com/ma...ombrables.html

Autre conséquence : ZF moins l'axiome de l'infini est consistante, elle admet donc des modèles, qui sont tous infinis, donc il en existe de toutes cardinalités.

Quant à la page 6, le mot dénombrable est bien à prendre dans le sens infini dénombrable.

[karlp]

Bonjour karlp,

I ) Le théorème de Lowenheim-Skolem dit deux choses :
1) toute théorie (logique classique du 1er ordre) qui admet un modèle infini, possède des modèles en tous les cardinaux infinis, c'est à dire possède une infinité de modèles non-isomorphes.
2) toute théorie qui admet des modèles finis aussi grand que l'on veut possède des modèles infinis.

II)Ce théorème permet de montrer, par exemple qu'il n'existe pas de théorie (logique classique du 1er ordre) dont les modèles sont les groupes (par exemple) finis (j'ai parler de ce point de vue là : http://forums.futura-sciences.com/ep...e-linfini.html).

III)Ce théorème permet aussi de montrer que si la théorie des ensembles est consistante, alors elle admet un modèle dénombrable dans lequel on peut définir l'ensembles des parties de IN (qui n'est donc pas dénombrable) comme sous-partie d'un ensemble dénombrable : http://forums.futura-sciences.com/ma...ombrables.html

Autre conséquence : ZF moins l'axiome de l'infini est consistante, elle admet donc des modèles, qui sont tous infinis, donc il en existe de toutes cardinalités.

IV)Quant à la page 6, le mot dénombrable est bien à prendre dans le sens infini dénombrable.

Bonjour Médiat

I) ouf ! enfin une formulation qui me permette de comprendre clairement ce que vous dîtes page 6 ( les mathématiciens de mon entourage vous remercient: je vais cesser de les harceler; aucun ne connaissait ou ne se souvenait de ce théorème)

II) J'irai approfondir cette question plus tard.
III) Je crois que vous faîtes allusion au "paradoxe" de Lowenheim Skolem ?
J'en comprends vaguement l'idée ; il me faudra étudier la démonstration du théorème ci dessus pour vraiment assimiler ce dont il s'agit.
IV) oui, ça ne me pose plus de difficulté désormais.

Une question me taraude: La théorie PréA' est aleph1-catégorique: celà signifie donc qu'elle ne possède qu'un seul modèle (à isomorphisme près) de cardinal aleph 1: comment se fait-il qu'il n'y ait pas contradiction avec me théorème de Lowenheim Skolem ? En effet, si préA' possède un modèle infini, elle devrait donc posséder des modèles pour les autres aleph ?

Je vous souhaite une bonne journée.

[Médiat]

Bonjour karlp

I) ouf ! enfin une formulation qui me permette de comprendre clairement ce que vous dîtes page 6 ( les mathématiciens de mon entourage vous remercient: je vais cesser de les harceler; aucun ne connaissait ou ne se souvenait de ce théorème)

Pour être complet, j'aurais dû écrire "en tous les cardinaux infinis supérieurs ou égaux au cardinal du langage", mais généralement le langage est de cardinal au plus dénombrable.

III) Je crois que vous faîtes allusion au "paradoxe" de Lowenheim Skolem ?

Oui, c'est bien cela.

Une question me taraude: La théorie PréA' est -catégorique: celà signifie donc qu'elle ne possède qu'un seul modèle (à isomorphisme près) de cardinal : comment se fait-il qu'il n'y ait pas contradiction avec me théorème de Lowenheim Skolem ? En effet, si préA' possède un modèle infini, elle devrait donc posséder des modèles pour les autres ?

Il n'y a pas de contradiction, dire qu'elle ne possède qu'un seul modèle de cardinal (et non qu'elle ne possède qu'un seul modèle qui est de cardinal , phrase fausse, bien sur) , ne veut pas dire qu'il n'y en a pas de cardinal , etc.

[karlp]

Il n'y a pas de contradiction, dire qu'elle ne possède qu'un seul modèle de cardinal (et non qu'elle ne possède qu'un seul modèle qui est de cardinal , phrase fausse, bien sur) , ne veut pas dire qu'il n'y en a pas de cardinal , etc.

C'est ce que j'ai fini par supposer (j'aurai pourtant dû y penser spontanément); votre confirmation me rassure grandement.
Je vais poursuivre ma lecture, mais je ne vais pas faire les exercices que vous proposez, j'en suis absolument incapable (j'essaierai quand même de me faire une "intuition").
Je suis impatient d'aborder le chapitre sur l'élimination des quantificateurs.

En vous remerciant

[karlp]

Bonjour Médiat

(je n'ai pas laissé tomber cette enrichissante et passionante lecture; mon travail me laisse trop peu de temps ce jours ci)

Contrairement à ce que j'avais dit, j'ai quand même eu envie d'essayer de traiter au moins un exercice. Même "facile", 'jai beaucoup de difficulté (euphémisme pour dire que je n'y parviens pas).

J'ai essayé de démontrer que l'axiome A1 de la théorie PréA était un théorème de PréA"'.

Je vous présente ci dessus la "piste" sur laquelle je me suis engagé.

Rappel:
Axiome 1 (de PréA): "x, (s(x) = 0)"

Exercice 10: montrer que cet axiome est un théorème de PréA"'

Par O3
x (x<0)

et O6
xy (( x< y) (x = y) (y< x))

Je peux déduire:

x (x < 0) ((x = 0) ( 0 < x ))

Or : (x = 0) (s(x) = 0) (C'est ici que j'ai une grande difficulté: je ne sais pas comment démontrer que (s(x) = x))

et (0 < x) y (x = s(y)) par l'axiome O1

Et comme (s(y) = x)et que (0 < x) alors PréA"' y (s(y) = 0)


J'ai conscience que ce que j'écris ressemble beaucoup à du "bricolage" bien peu rigoureux (mais je ne peux pas ne pas au moins "essayer").

Bonne journée

[Médiat]

Bonjour karlp,

Vous étiez bien parti :

Axiome
Axiome
Axiome
Axiome

Donc s(x) ne peut pas être égal à 0.

Médiat

[karlp]

Mille mercis!!!

[karlp]

Bonjour Médiat

(je vous en prie, n'hésitez pas à me dire si mes sempiternelles requêtes vous ennuient. Je ne veux surtout pas que vous vous sentiez obligé, d'aucune façon)

J'ai essayé de démontrer A2:

Par O3 et O6 j'obtiens (x = 0) v (y< x)
et par O1 je déduis ( x = O ) v y (x = s(y)).


J'ai également essayé A3 (je n'ai pas réussi à coder la bi implication et lui ai substitué un autre symbole d'équivalence. Je ne retrouve plus ma feuille avec le code ):

Par O2 je peux déduire

s(x) < s(y) (s(x) < s(y)) v (s(x) = y)
D'où (s (x)< s(y)) (s(x)<y) ET (s(x) = y)

Par O6 j'en déduis y < s(x)

En appliquant le même raisonnement mais en substituant x à chaque occurence de y et y à chaque occurence de x, j'obtiens

x< s(y)

Par O4, appliqué aux deux dernières solutions, j'obtiens
(s(x)<y)
ET (s(y)<x)

Enfin, par O2 : x=y

Avec tous mes respects.

[Médiat]

Bonjour,

(je vous en prie, n'hésitez pas à me dire si mes sempiternelles requêtes vous ennuient. Je ne veux surtout pas que vous vous sentiez obligé, d'aucune façon)

AU contraire, cela me ravit de donner un peu de vie à ce document.

(c'est tout simplement une application de la relation ).


Pour c'est un tout petit peu plus compliqué :

Si on suppose , on peut écrire donc et entraine
Mais on peut écrire aussi donc et entraine , on a donc :

entraine que l'on ne peut avoir , donc (cqfd).

Amicalement

[Médiat]

Surtout réfléchissez à l'Exercice 11, il est simple, mais cache (pas trop) une subtilité fondamentale

[karlp]

Surtout réfléchissez à l'Exercice 11, il est simple, mais cache (pas trop) une subtilité fondamentale

Bonjour Médiat

Je prends le temps de "potasser" la solution pour A3 (je comprends assez bien; mais ai besoin d'un temps de "digestion").
Je vais ensuite m'atteler à l'exercice 11 ; même si je ne réussis pas, je vous avoue que je prends beaucoup de plaisir à essayer et je crois que si je ne faisais pas ces tentatives, je ne pourrai pas apprécier vos démonstrations comme elles le méritent (ce serait une question pour les pédagogues et les psychologues de la connaissance)

Je suis votre obligé.
Passez une excellente journée.

[Médiat]

je vous avoue que je prends beaucoup de plaisir à essayer

La deuxième raison pour laquelle j'ai introduit beaucoup d'exercices c'est qu'il s'agit d'un domaine très abstrait, et pour bien le maîtriser sans lui enlever son caractère d'abstraction, je trouve très efficace de mettre les doigts dedans

Cordialement

[karlp]

La deuxième raison pour laquelle j'ai introduit beaucoup d'exercices c'est qu'il s'agit d'un domaine très abstrait, et pour bien le maîtriser sans lui enlever son caractère d'abstraction, je trouve très efficace de mettre les doigts dedans

Cordialement

Bonjour Médiat

Vous avez absolument raison: c'est en parlant une langue que nous l'apprenons .

J'ai réflechi à l'exercice 11.
J'en suis venu à faire l'hypothèse que vous n'avez pas écrit "les axiomes sont ceux de PréA' plus deux axiomes pour +", peut-être parce que le schéma d'induction n'est pas un axiome, mais un schéma d'axiomes ?

Je vous souhaite une excellente journée

(pour l'exercice 12, j'ai, je crois, réussi à démontrer le Théorème 1, qui n'est autre que A4 et suis en train de réfléchir à la façon dont on peut démontrer la commutativité de l'addition)

[Médiat]

Bonjour,

J'en suis venu à faire l'hypothèse que vous n'avez pas écrit "les axiomes sont ceux de PréA' plus deux axiomes pour +", peut-être parce que le schéma d'induction n'est pas un axiome, mais un schéma d'axiomes ?

C'est effectivement lié, mais il y a une raison profonde à cela. Un schéma d'axiomes est une façon de "générer" des axiomes, par exemple, écrire que "ZFC = les mêmes axiomes que ZF auxquels on ajoute l'axiome du choix" ne me choque pas, malgré la présence de schémas d'axiomes dans ZF.

[karlp]

Je continue donc d'y réflechir

[Médiat]

(pour l'exercice 12, j'ai, je crois, réussi à démontrer le Théorème 1, qui n'est autre que A4

Attention, il y a une différence entre T1 et A4, la démonstration n'est donc pas "immédiate", il faut une récurrence.

[karlp]

Attention, il y a une différence entre T1 et A4, la démonstration n'est donc pas "immédiate", il faut une récurrence.

Je nage dans le brouillard

Pour l'exercice 11: est-ce que la réponse est liée au fait que + soit un symbole de type 2 par rapport à PréA ? (j'essaye d'envisager toues les possibilités , mais je sèche)

J'essaye d'appliquer la récurrence à A4 pour démontrer T1, mais là encore, je reste démuni: la seule différence que je perçois entre les deux énoncés est la place relative du 0 et du x.
J'ai l'impression que la difficulté posée par T1,T2 et T3 est la même: démontrer la commutativité de +

[Médiat]

Pour le 11 :
J'aurais pu écrire :
1) Les axiomes de Presburger sont ceux de PréA', plus deux axiomes pour +.
2) Les axiomes et schéma de Presburger sont ceux de PréA', plus deux axiomes pour +.
3) Les axiomes de Presburger sont ceux de PréA, plus le schéma d'induction, plus deux axiomes pour +.

La 1) est fausse, la 2) est ambiguë, il ne me restait plus que la 3).

La 1) est fausse car les axiomes générés par le schéma d'induction dans PréA' sont les axiomes écrit dans le langage de PréA', donc sans le +, or le schéma de Presburger doit engendrer les axiomes sur le langage avec + !

Pour T1 :

0 + 0 = 0 (axiome A₄)
ensuite il suffit d'écrire l'axiome d'induction adaptée à la formule 0 + x = x et d'utiliser l'axiome A₅

[karlp]

Pour le 11 :
J'aurais pu écrire :
1) Les axiomes de Presburger sont ceux de PréA', plus deux axiomes pour +.
2) Les axiomes et schéma de Presburger sont ceux de PréA', plus deux axiomes pour +.
3) Les axiomes de Presburger sont ceux de PréA, plus le schéma d'induction, plus deux axiomes pour +.

La 1) est fausse, la 2) est ambiguë, il ne me restait plus que la 3).

A)La 1) est fausse car les axiomes générés par le schéma d'induction dans PréA' sont les axiomes écrit dans le langage de PréA', donc sans le +, or le schéma de Presburger doit engendrer les axiomes sur le langage avec + !
B)Pour T1 :

0 + 0 = 0 (axiome A₄)
ensuite il suffit d'écrire l'axiome d'induction adaptée à la formule 0 + x = x et d'utiliser l'axiome A₅

Bonjour Médiat

A) C'est l'idée que j'avais en tête, mais que j'ai très mal formulée (en soulignant le fait que + était un symbole de type 2; vous n'imaginez pas ma joie en cet instant)
B) Merci, parce que là je n'avançais pas. Je prends le temps de la reflexion/digestion (peut-être cela m'aidera t'il à démontrer les théorèmes suivants).

A très bientôt (je l'espère, mon travail nuit grandement à mes passions ces derniers temps )

[karlp]

Je rencontre un soucis "technique": je ne vois pas du tout comment on peut appliquer le schéma d'induction à la formule (0 + x = x)

Passez une bonne journée