Arithmétique

[Médiat]

"Tout sous-ensemble y de x vérifie p(x,y)"

Bonjour,

C'est mathématiquement correct, mais cela laisse implicite ce qui est implicite (mais réellement présent) dans la formule formelle ; comme il n'y a pas eu beaucoup de volontaires pour tenter ce concours, je vais donner la réponse que j'avais en tête.

J'attire votre attention sur un point fondamental : ne pas connaître ou ne pas comprendre le détail suivant c'est être sûr de ne pas comprendre la théorie des ensembles.

Je mets sous spoiler au cas où certains voudraient continuer à chercher :

 Cliquez pour afficher

Tout ensemble y qui est un sous-ensemble de x vérifie p(x, y)

Je suis disponible pour tous les commentaires nécessaires.

Bon courage pour les exercices ...
-----

[Turgon]

EDIT: Bug de latex dans le précédent message et j'ai voulu éditer trop tard, voici un message normalement un peut mieux latexé.

Je poste ma résolutions des 4 premiers exercices, si ça intéresse quelqu'un. J'en suis plus loin mais c'est long de tout écrire donc je posterias petit à petit . Quand je reposterais, je garderais les notations que j'ai introduites.

En tant qu'élève de prépa, je n'avait pas toute les notions requises notamment la notion de Z/pZ, mais bon j'ai à peu près compris ayant étudié les congruences, grâces aux explications données plus tôt dans le post:

Arithmétique-1.

Pour commencer, je veux juste préciser que je n'ai souvent pas su faire autrement que de raisonner sur des modèles comme je raisonnerais sur des ensembles (avec la théorie qui va avec) alors que ce n'est peut-être pas les mêmes objets.

0) Pas encore de l'arithmétique.

Pour tout n, "Composante connexe de type n" est abrégé en CCn.

réponse exercice1:

 Cliquez pour afficher

Soit C une composante connexe. Si 0 est dans C, par définition, on a pour tout entier naïf n, dans C et vu qu'il y a une infinité d'entiers naïf, il y a une infinité "d'élément" dans C.
Donc le cas d'une composante contenant 0 et finie est impossible.

réponse exercice 2:

 Cliquez pour afficher

Soit C1 et C2 deux CC1.
Elle contiennent toutes deux 0 et donc l'ensemble {0, s(0), s(s(0)),...} noté par la suite S(0).
On a donc si on note de manière ensembliste, .
De plus, par connexité et par A1, pour tout $x$ dans C1 ou C2, il existe un entier naïf n tel que . Donc et donc par un raisonnement ensembliste simple, C1=C2=S(0).

réponse exercice 3:

 Cliquez pour afficher

Montrons A1 pour le langage interprété dans un modèle du type M.
Montrons donc qu'aucun élément du modèle n'a le 0 du modèle comme successeur.
Aucun élément de N n'a 0 pur successeur car l'application f qui a n associe n+1 vérifie f(N)=N*.
De plus aucun élément des autre ensemble dont le modèle est défini comme le produit n'a comme successeur vu que n'appartient à aucun de ces ensemble et que l'application successeur restreinte à chacun de ces ensemble est à valeur dans ces ensembles.
On a donc A1 dans les modèles de type M.

Montrons A2 pour les modèles de type M. Montrons donc que tous les éléments non nuls au sens du langage interprété sont successeurs au sens de l'application définie.
Dans N, l'application f qui a x associe x+1 est surjective de N dans N* donc A2 y est vrai au sens du modèle.
Dans les copies de Z, tout x vérifie: (x-1)+1=x donc x est bien successeur de x-1.
Dans les copies de Z/pZ, tout x vérifie: donc x est bien successeur de .
On a donc A2 dans tout modèle du type M.

Montrons A3 pour tout modèle du type M selon l'interprétation du langage. Cela se montre par injectivité de restreinte à chacun des facteurs du modèles (N, chaque copie de Z chaque copie des Z/pZ).
On a donc bien A3 dans tout modèle du type M selon l'interprétation du langage.

Tout modèle du type M est donc bien modèle du langage défini.

réponse (vague) exercice 4:

 Cliquez pour afficher

Euh bon, je ne suis pas très sur mais si comme je le crois on utilise les N, Z, Z/pZ qu'on peut définir classiquement, c'est-à dire à l'aide de la théorie des ensemble, en définissant les relations par des parties de produit d'ensemble etc..., alors cela signifie que l'on se place sous les hypothèses de la théorie des ensemble pour dire qu'il existe des modèles à la théorie préA (puisque les ensembles N, Z, Z/pZ n'existent pas, ni les produits unions etc..., sans certaines hypothèse).

Il n'est donc pas gênant d'utiliser ces ensemble si on considère qu'il n'est pas gênant de supposer les axiomes de la théorie des ensemble, après, est-il raisonable de les supposer, je ne saurais dire ...

A suivre quand j'aurais le courage de tout taper.

[Médiat]

Bonjour,

Exercice 1 :

 Cliquez pour afficher

Votre réponse est insuffisante, vous pouvez regarder le message http://forums.futura-sciences.com/ma...ml#post3240700 et en particulier les 3 dessins CC2.

Exercice 2 :
Démonstration correcte.

Exercice 3 :
Démonstration correcte.

Exercice 4 :
Réponse correcte, mais j'ajoute un petit complément :

 Cliquez pour afficher

Soit on considère que, dès que l'on parle de modèle, on parle d'ensemble, donc on peut se placer dans une théorie des ensembles satisfaisante (ZFC par exemple), et vos remarques sont satisfaisantes.

Soit on fait une théorie des modèles plus naïve, et on se contente de dissocier le champ syntaxique (la théorie, les axiomes, ...) et le champ sémantique (les modèles) ; comme le but ici est de donner une définition syntaxique de IN, il serait inacceptable d'utiliser IN dans cette partie (*), mais dans la partie sémantique, il serait très étrange qu'en cherchant à définir IN, je ne trouve pas IN dans les modèles possibles.

(*) Ce point n'est pas tout à fait innocent, si on demande à des non mathématiciens (voir à des mathématiciens non logiciens) de définir IN, il a de fortes chances que la réponse contiennent un usage de IN non explicite, mais bien réel.

[Seirios]

Nouveau déterrage pour ce post (presque un an jour pour jour) !

Je viens d'achevé la lecture de ce document et je l'ai adoré, vraiment passionnant !

Les commentaires de lectures sont-ils toujours d'actualité ? Dans tous les cas, je pose une question générale : le document montre une progression d'une arithématique "la plus intuitive" vers une arithmétique "acceptable", et finalement on se retrouve avec pléthore d'arithmétiques, avec chacune leurs défauts et leurs avantages. Ma question est simplement : Que fait-on avec toutes ces arithmétiques ? Parce que finalement, on a pas attendu d'avoir ces théories pour faire de l'arithmétique, alors y a-t-il une théorie que l'on préfère parce qu'elle correspond mieux à ce que l'on faisait déjà avant, y en a-t-il une qui se distingue particulièrement des autres, etc. ?

[Médiat]

Ma question est simplement : Que fait-on avec toutes ces arithmétiques ? Parce que finalement, on a pas attendu d'avoir ces théories pour faire de l'arithmétique, alors y a-t-il une théorie que l'on préfère parce qu'elle correspond mieux à ce que l'on faisait déjà avant, y en a-t-il une qui se distingue particulièrement des autres, etc. ?

Clairement l'arithmétique de Peano (du premier et du deuxième ordre) se détache des autres, qui, à mon sens, servent plus de laboratoire pour démontrer des théorèmes avec le minimum d'axiomes.

Et, bien sur, vous pouvez faire tous les commentaires que vous voulez, je tâcherais d'y répondre.

[invite8f0fad3a]

pouvez vous vous diriger au forum suivant:

www.les-mathematiques.net/phorum/list.php?5 et repondre au sujet (article )
ou bien au

marocmaths.forumgratuit.ca

jaimerais savoir votre avis la dessus.

merci

[Médiat]

Bonjour,

Quelques points :

1) Si vous voulez discuter ici de votre méthode, postez-là ici, dans un autre fil, puisque ce que vous proposez n'a rien à voir avec celui-ci.

2) Vous ne donnez aucune démonstrations, c'est donc impossible à publier.

3) Vous proposer un algorithme dont rien n'indique qu'il se termine, et vous ne donnez aucune indication sur sa vitesse de convergence.

4) Tout repose sur l'existence de 3 entiers, mais vous ne donnez aucune méthode pour les calculer

Pour conclure, après la lecture de votre article, je ne sais pas comment appliquer votre méthode, je ne sais pas si elle marche, je ne sais pas si elle est rapide.

Ne vous découragez pas pour autant, essayez de résoudre ces 3 points, et postez dans ce forum (si vous savez intéressez les lecteurs, je suis sur que vous trouverez ici des gens pour vous aider à peaufiner certains détails et/ou à faire des tests). Et ajoutez quelques exemples avec de "grands entiers".

Bon courage

[Médiat]

Bonjour,

Je profite de cette exhumation pour poster la dernière version, avec quelques fautes de frappes en moins. N'hésitez pas à me signaler celles qui restent.

arithmetique.pdf

[Seirios]

Je pense que le document gagnerait à avoir un petit glossaire ; si quelqu'un ne connaissant presque rien à la logique doit pouvoir comprendre ce document, quelques termes devraient être explicités, d'un autre côté il serait peut-être trop lourd d'intégrer ces définitions au texte lui-même.

Voici les termes que j'ai relevés :
- isomorphisme,
- théorie complète,
- formule indécidable,
- schéma d'axiomes,
- symboles et ,
- théorème de Löwenheim-Skolem,
- théorie consistante,
- théorème de compacité,
- quantificateur borné,
- segment initial d'un modèle,
- prédicat.

Quelques petites erreurs (elles ont peut-être été corrigées dans la nouvelle version, je n'ai pas vérifié) :
- en bas de la page 3 : "la démonstration envisagée est en fait..." et "Le monoïde libre à un générateur...",
- exercice 8 : il doit manquer un \ devant le forall,
- page 6, définition : "...si elle ne possède qu'un seul modèle de cardinal à isomorphisme près."

Quelques remarques / questions supplémentaires :
- Peut-être faudrait-il préciser que l'on sous-entend que le langage est égalitaire ?
- L'expression du modèle de PréA gagnerait à être expliquée davantage,
- Je n'ai pas vraiment compris le théorème 14 : qu'entendez-vous par procédé constructif ?
- J'ai également des problèmes de compréhension au niveau de la dernière remarque sur l'arithmétique du second ordre : que représentent X et Z ?
- On s'aperçoit que le schéma d'axiomes d'induction est vraiment important, notamment en étudiant l'arithmétique de Robinson. A-t-on montré que l'on ne peut pas obtenir d'arithmétique "satisfaisante" finement axiomatisable ?

(Je n'ai pas encore lu en détail tout le chapitre de l'arithmétique de Peano, donc j'aurai peut-être quelques remarques supplémentaires ultérieurement.)

[Médiat]

Je pense que le document gagnerait à avoir un petit glossaire ; si quelqu'un ne connaissant presque rien à la logique doit pouvoir comprendre ce document, quelques termes devraient être explicités, d'un autre côté il serait peut-être trop lourd d'intégrer ces définitions au texte lui-même.

Très bonne idée, je vais le faire.

- en bas de la page 3 : "la démonstration envisagée est en fait..." et "Le monoïde libre à un générateur...",

Corrigé dans la prochaine version.

- exercice 8 : il doit manquer un \ devant le forall,
- page 6, définition : "...si elle ne possède qu'un seul modèle de cardinal à isomorphisme près."

Corrigés dans la précédente version.

- Peut-être faudrait-il préciser que l'on sous-entend que le langage est égalitaire ?

Oui, dans le glossaire.

- L'expression du modèle de PréA gagnerait à être expliquée davantage,

J'ai déjà eu des remarques sur ce point, je vais y réfléchir.

- Je n'ai pas vraiment compris le théorème 14 : qu'entendez-vous par procédé constructif ?

Il s'agit d'un algorithme qui permet de construire effectivement la formule sans quantificateur équivalente à la formule avec quantificateur (un exemple simpliste : si a, b et c sont des constantes réelles avec a != 0, et x une variable réelle, la formule est équivalente à ).

- J'ai également des problèmes de compréhension au niveau de la dernière remarque sur l'arithmétique du second ordre : que représentent X et Z ?

et sont des ensembles de formules et signifie que permet de démontrer , l'autre symbole (non supporté par FSG) signifie que est vrai dans tous les modèles de

- On s'aperçoit que le schéma d'axiomes d'induction est vraiment important, notamment en étudiant l'arithmétique de Robinson. A-t-on montré que l'on ne peut pas obtenir d'arithmétique "satisfaisante" finement axiomatisable ?

Il existe des arithmétiques finiment axiomatisables, reste à savoir ce que l'on entend par satisfaisante (et quel intérêt on attend de "finiment axiomatisable").
On doit pouvoir faire des choses dans la théorie des ensembles NBG puisque celle-ci est finiment axiomatisable.

[Seirios]

et sont des ensembles de formules et signifie que permet de démontrer , l'autre symbole (non supporté par FSG) signifie que est vrai dans tous les modèles de

C'est donc bien ce que j'avais compris. Mais pourquoi chercher un tel système de règles d'inférence ? La propriété de robustesse me paraît raisonnable, mais pour la propriété de complétude, on ne l'a pas au premier ordre alors pourquoi la demander au second ordre ?

[Seirios]

Quelque chose d'intéressant à rajouter pourrait être aussi une petite bibliographie.

[Médiat]

C'est donc bien ce que j'avais compris. Mais pourquoi chercher un tel système de règles d'inférence ? La propriété de robustesse me paraît raisonnable, mais pour la propriété de complétude, on ne l'a pas au premier ordre alors pourquoi la demander au second ordre ?

Justement si, cette propriété est vérifiée par la logique du premier ordre : c'est le fameux théorème de complétude de Gödel.

[Médiat]

Quelque chose d'intéressant à rajouter pourrait être aussi une petite bibliographie.

C'est effectivement possible et certainement souhaitable, mais plus difficile, j'ai écrit beaucoup de chose de mémoire et j'ai refait la plupart des démonstrations (je devrais facilement trouver des choses sur Presburger, Robinson, Peano et Gödel, bien sur).

[Médiat]

Voici une nouvelle mouture avec une première version de glossaire ?

[Seirios]

Je trouve le glossaire clair (il doit cependant manquer une petit phrase dans l'entrée concernant la notion d'isomorphisme pour dire que est un isomorphisme).

Au début du document, vous renvoyer le lecteur vers d'autres liens pour la notion de modèle, peut-être pourriez-vous rajouter une entrée modèle dans le glossaire ?

Pour les références, je suis tombé sur ce document : http://www.logique.jussieu.fr/~zoe/papiers/MTluminy.pdf, qui m'ont l'air tout à fait intéressantes (par contre, il n'y a pas toutes les démonstrations, mais c'est plutôt pour avoir une vision d'ensemble).

[Médiat]

(il doit cependant manquer une petit phrase dans l'entrée concernant la notion d'isomorphisme pour dire que est un isomorphisme).).

Effectivement, ce serait plus clair.

(Au début du document, vous renvoyer le lecteur vers d'autres liens pour la notion de modèle, peut-être pourriez-vous rajouter une entrée modèle dans le glossaire ?).

Bonne idée

(
Pour les références, je suis tombé sur ce document : http://www.logique.jussieu.fr/~zoe/papiers/MTluminy.pdf, qui m'ont l'air tout à fait intéressantes (par contre, il n'y a pas toutes les démonstrations, mais c'est plutôt pour avoir une vision d'ensemble).

Je vais lire plus en détail, mais Zoé Chatzidakis est une logicienne bien connue.

[Médiat]

Bonjour,

Vous trouverez ci-joint une nouvelle version de Arithmetique.pdf (avec des corrections mineures de présentation et d'orthographe) et le document solutions.pdf avec les solutions des exercices.

Je n'ai pas beaucoup relu ce document (je suis dessus depuis 15 jours, et cela me sort un peu par les yeux (je ne suis malheureusement pas encore à la retraite )), donc merci de me remonter :

1) Toutes fautes de frappe
2) Toutes améliorations de présentation
3) Toutes améliorations des démonstrations
4) Toutes nouvelles démonstrations (plus claires ou plus simples ou plus élégantes ou ...)
5) Toutes questions
6) etc.

[Seirios]

Bonjour,

J'ai relu le document et il y a un point qui me gêne dans la démonstration du théorème 20 (l'arithmétique de Peano a modèles dénombrables non isomorphes). Dans la définition de , pour qu'elle ait un sens, ne faudrait-il pas que appartienne au langage ?

[Médiat]

Bonjour
Non, ce n'est pas nécessaire, car P est utilisé ici comme indice et non comme élément du langage

[Seirios]

Mais en écrivant avec , cela n'intervient pas seulement en tant qu'indice, non ?

[Médiat]

Bonjour
P intervient dans la façon de construire la formule, mais pas dans la formule elle-même qui ne contient que des entiers.