Fitch pour la théorie des nombres Proofs
Remarque: Les axiomes et les preuves présentées dans ce document ont été créés à l'aide de la première édition du livre de LPL et des logiciels (Fitch). Dans la deuxième version du livre, les axiomes Peano sont un peu différentes, en utilisant une fonction de successeur au lieu d'une constante 1. En outre, la nouvelle version de Fitch a ajouté des règles d'inférence formelles portant spécifiquement sur l'induction mathématique, ainsi qu'un mécanisme permettant fichiers de preuve pour se référer à d'autres fichiers contenant des preuves pour des résultats établis précédemment (Lemme de). Les fichiers de preuve pour l'ancienne version de Fitch peut être ouvert dans la nouvelle version de Fitch.
Voir: chiffres (dossier compressé de 16 fichiers .prf)
Note 2: Je converti la preuve ne soit pas assurée le plus grand nombre premier à la deuxième édition. En raison de la façon dont les fichiers lemme sont inclus chaque fois une référence est faite au Lemme, le fichier de preuve d'origine a augmenté à environ 3Mo et a pris environ 3 heures pour sauver. Je l'ai depuis changé la preuve il s'appuyait moins sur Lemme de. Il est maintenant de 600Kb, et prend environ 20 minutes pour sauver. Voici la nouvelle preuve (de dossier compressé de 11 fichiers .prf). Je l'ai converti toutes les preuves de la version originale ainsi (et ajouté un peu plus) pour un total d'un peu plus de 100 épreuves, mais je me sentais un fichier .zip serait trop grand pour poster. Par ailleurs, le livre de LPL a certaines de ces preuves que des exercices dans le livre.
Quelques preuves de la théorie des nombres de Fitch
Le langage du livre, preuve et logique, par Barwise et Etchemendy expose un système de preuve formelle F, qui définit un ensemble de règles d'inférence formelles pour construire des preuves logiques formelles. Le livre est livré avec plusieurs exercices qui demandent à l'utilisateur de construire une preuve formelle à l'aide du logiciel Fitch, qui fournit une interface utilisateur graphique pour les utilisateurs de créer des preuves formelles conformément au système F. parties I et II du livre était la systèmes de base de la logique propositionnelle et prédicat, tandis que la partie III du livre va dans certaines applications et metatheory. Le présent document se penche sur une application particulière, qui est la théorie des nombres (arithmétique), et voit quels types de théorèmes peuvent être prouvés dans Fitch sur ce domaine.
Les Axiomes de Peano Arithmétique
L'article 16.4 du livre de LPL, appelé « axiomatiser les nombres naturels », expose 7 axiomes et un schéma d'axiome pour les nombres naturels:
1. Ax Ay x + 1 = y + 1 -> x = y
5. Ax Ay x + (y + 1) = (x + y) + 1
7. Ax Ay * x (y + 1) = (x * y) + x
Induction Axiom Scheme: pour toute formule P (x) (une formule avec une variable libre x) l'instruction suivante est un axiome:
(P (0) - Ax (P (x) -> P (x + 1))) -> Ax P (x)
Collectivement, ces 7 axiomes et le schéma d'axiome d'induction sont appelés Peano Arithmétique (PA). L'utilisation PA, nous pouvons prouver toutes sortes de théorèmes sur les nombres naturels.
Le langage de l'arithmétique et la norme d'interprétation
Les axiomes PA utilisent les symboles non logiques suivants: 0, 1, + et *. 0 et 1 sont des constantes individuelles (ou symboles de constante) et + et * sont des symboles de fonction. Ces quatre symboles représentent la langue de l'arithmétique (LA). Autrement dit, on peut dire que LA =. Les symboles non logiques peuvent être interprétées de quelque façon que l'on veut. Par exemple, mais dans l'interprétation standard de la langue de l'arithmétique, les symboles sont interprétés exactement comme on attend: 0 est le numéro zéro, 1 est le numéro un, + est la fonction d'addition, et * est la fonction de la multiplication. Ainsi, selon l'interprétation standard, le terme complexe (1 + 1) * (1 + 1) évalue au nombre de quatre.
Quelques vérités très simples
Tout d'abord, en utilisant Peano Axioms 1 à 7 seul (nous faire référence à cet ensemble d'axiomes que PA 1-7) nous pouvons prouver des choses simples comme
1 = 0, 2 + 2 = 4, et 1 * 1 = 1. Bien sûr, étant donné que nous ne disposons que des constantes 0 et 1 pour travailler avec, nous avons besoin d'utiliser une convention pour représenter des nombres autres que 0 et 1. Nous allons utiliser la convention selon laquelle un nombre n est représenté par (((((. (1 + 1) + 1) + 1) + 1) + 1). + 1) + 1 (par exemple un terme complexe impliquant n 1 dans le motif comme le montre), et nous faisons référence à cette représentation en tant que n. En général, on peut prouver que l'on peut tirer formellement de PA 1-7:
1) t = a. pour tout terme t que, dans l'interprétation standard évalue au nombre d'un (on écrit ce que N (t) = a)
t = a pour un terme t que, dans l'interprétation standard est évaluée à un nombre autre qu'un
De ce fait, il suit immédiatement que:
3) PA1-7 | - t1 = t2, pour tout termes t1 et t2 pour lesquels N (t1) = N (t2)
t1 = t2, pour tout termes t1 et t2 pour lesquels N (t1)! = N (t2)
En particulier, nous pouvons prouver à partir PA1-7:
a = b pour tout nombres a et b pour laquelle a! = b
Cependant, on ne peut pas déduire Ax Ay x + y = y + x de PA 1-7 (en fait, nous pouvons prouver que ce ne peut être déterminée en tenant compte des interprétations non standard pour la langue de l'arithmétique dans laquelle PA 1-7 attente mais dans laquelle Ax Ay x + y = y + x ne tient pas). Heureusement, en ajoutant le schéma d'induction, nous pouvons prouver Ax Ay x + y = y + x, à savoir la dernière déclaration peut être prouvée de PA.
Base propriétés additives et multiplicatives
En utilisant la pleine PA, nous pouvons prouver divers théorèmes concernant les propriétés de base de l'addition et la multiplication, telles que:
Ax Ay Az (x + y) + z = x + (y + z) (Association d'addition)
Ax Ay x + y = y + x (Commutation d'addition)
Ax Ay Az (x * y) z = * x * (y * z) (Association de multiplication)
Ax Ay x * y = y * x (Commutation de multiplication)
Ax Ay Az * x (y + z) = (x * y) + (x * z) (Distribution de multiplication sur l'addition)
Un théorème très utile que l'on finit souvent à l'aide est la suivante:
x = 0 -> Ey y + 1 = x)
L'addition et la multiplication par 0 et 1
Voir: Additon.prf, Multiplication.prf
La plus petite que la relation
Parfois, nous ne voulons introduire de nouveaux symboles à notre langue pour nous aider à parler un concept utile. Un concept de primaire et important est la plus petite que la relation que nous pouvons définir comme:
Ax Ay (x < y <-> Ez (
z = 0 - x + z = y)
Si l'on ajoute à cette définition comme un axiome à notre système de sonorisation, nous pouvons maintenant prouver des choses comme 0 < 1, Ax
X < 0, and the important properties of irreflexivity (Ax
X < x), asymmetry (Ax Ay x < y ->
y < x), and transitivity (Ax Ay Az ((x < y - y < z) -> X < z). Note, though, that one can always restate any of these theorems using the original language that does not have the < symbol in accordance to the definition above. For example, Ax
X < 0 becomes Ax
z = 0 - x + z = y), et la déclaration ci peuvent être dérivées de l'original PA.
Induction forte ou complète
Ax (Ay (y < x -> P (y)) -> P (x)) -> Ax P (x)
Bien que ce système inductif semble être plus fort que le régime inductif que nous avons, il se trouve que nous pouvons réellement prouver ce régime fort du régime inductif (faible), nous avons déjà. Nous pouvons bien sûr prouver aussi la version plus faible de la version plus forte.
Dans le livre calculabilité et logique, 5ème édition, Boolos, Burgess et Jeffrey définissent le système Q, qui se compose de 10 axiomes élémentaires concernant addition, multiplication, et la plus petite que relation. Ce système est d'un intérêt théorique, comme dans le livre, les auteurs montrent que pour tout qui est arithmétiquement son ensemble d'axiomes récursivement énumérable (ie dont on ne peut tirer des faussetés arithmétiques) et qui est en mesure de prouver ces 10 axiomes, on peut construire une phrase Godel, qui est une vraie phrase qui ne peut pas arithmétique être prouvé dans ce système. Par conséquent, un tel système est arithmétiquement incomplet: pas toutes les vérités arithmétiques peuvent être dérivées d'un tel ensemble d'axiomes. Il se trouve que PA est exactement un tel système: il est arithmétiquement son, récursivement dénombrable, et, comme le fichier Fitch démontre, les 10 axiomes de Q peuvent être obtenus dans le système PA. En fait, les 6 premiers axiomes (Q1 à Q6) sont un sous-ensemble de PA 1-7 et axiomes Q7 par Q10 peuvent provenir de PA en utilisant un grand nombre de résultats de base précédemment dérivés en ce qui concerne la plus petite que la relation. Par conséquent, nous pouvons conclure que PA est incomplète. Ce qui est une vraie corvée. Pourtant, nous allons voir ce que nous pouvons prouver!
Les lois d'annulation
Maintenant que nous avons nos principes de base en place arithmétique, nous pouvons essayer de prouver des résultats plus « intéressants ». Le premier résultat est que chaque numéro est pair ou impair (dans un sens exclusif bien sûr!). Pour cela, nous allons utiliser les définitions formelles suivantes des notions de pair et impair:
Ax (Even (x) <-> Ey (1 + 1) * y = x)
Ax (Odd (x) <-> Ey (1 + 1) * y + 1 = x)
Il est intéressant, il faut utiliser le schéma inductif pour prouver que chaque numéro est soit même, ou impair, mais pas les deux. Sans elle, les interprétations non standard permettent des objets dans son domaine d'être ni même ni impair, ou être à la fois pair et impair! Une fois que la disjonction exclusive est prouvé que, de nombreuses propriétés familières des nombres pairs et impairs suivent.
La racine carrée de 2 est pas un nombre rationnel
Voici un fameux théorème: la racine carrée de 2 est pas un nombre rationnel. La preuve de ce résultat est célèbre, et repose sur le concept des nombres pairs. Avec la définition précédente et théorèmes concernant evenhood en place, on peut en effet prouver ce résultat. La seule partie délicate est ici comment exprimer ce théorème. Autrement dit, alors que nous énonçons normalement ce théorème que: il n'y a pas nombres a et b tels que sqrt (2) = a / b, nous n'avons pas / ou fonctions sqrt définies. Encore plus pressante, si nous le voulions, nous aurions tout à coup parler de chiffres non-naturels, alors que le domaine prévu a toujours été juste les nombres naturels. Heureusement, sqrt (2) = a / b peut être réécrite comme 2 * b * b = a * a (en supposant b est différent de 0) et donc le théorème que nous pouvons prouver (voir Rationals.prf), devient:
y = 0 - x * x = 2 * y * y)
Il n'y a pas plus grand nombre premier
Voir: Divisors.prf, Factorial.prf, DivFac.prf et PrimesFac.prf
Enfin, prouvons un autre fameux théorème de l'arithmétique: qu'il n'y a pas plus grand nombre premier (et donc qu'il existe une infinité de nombres premiers). Ce théorème est également connu sous le second théorème d'Euclide. Comme d'habitude avec un nouveau concept, il est utile d'essayer de définir formellement la notion d'un nombre premier. Mathematicians définie comme un nombre premier nombre qui a exactement deux (à savoir deux différents) diviseurs: 1 et elle-même. Notez que ces règles de définition sur 0 et 1 comme les nombres premiers, qui a une bonne raison. Mathématiciens a fait pas toujours considérer 1 ne pas être un premier: depuis 1 n'a pas d'autres diviseurs que 1 et lui-même (ce qui semble être une façon tout à fait raisonnable de définir des nombres premiers), il a été pendant un certain temps considéré comme un premier choix. Toutefois, ce faisant, le théorème fondamental de l'arithmétique, qui stipule que chaque numéro a une factorisation prime unique ne tient plus. Donc, pour vous assurer que le théorème fondamental de l'arithmétique ne tient, la définition a été modifiée à la définition actuelle:
Ax Ay (Div (x, y) <-> (
x = 0 - Ez x * z = y))
x = 1 - Ay (Div (y, x) <-> (Y = 1 y = v x))))
La partie la plus délicate de cette preuve est quand on regarde la preuve typique de ce théorème, qui utilise la notion de factoriel. Maintenant, nous pouvons définir très facilement la notion d'un factoriel:
Ax fac (x 1) = (x + 1) * fac (x)
En utilisant cette définition, et les divers théorèmes qui peuvent être prouvées de lui, nous pouvons maintenant en effet prouver deuxième théorème d'Euclide.
Il n'y a pas plus grand nombre premier (Preuve alternative)
Voir: Divisors.prf, Primes.prf
Malheureusement, la définition du factoriel n'est pas une que nous pouvons facilement « se débarrasser ». Pour une construction comme Ax (P (x) <-> phi (x)) qui sert de définition de P (x), on peut toujours remplacer simplement phi (x) de nouveau dans toutes les preuves concernant P (x) afin de montrer que les résultats finaux auraient pu être prouvé en utilisant la langue d'origine des seuls (voir la plus petite que la section). Toutefois, cela ne va pas fonctionner dans le cas de cette définition du factoriel. Donc, si nous voulons nous assurer que ce que nous montrons peut en effet être finalement prouvé de PA seul (à savoir sans axiomes supplémentaires définitionnelles), nous devons faire autre chose.
Heureusement, nous ne devons pas utiliser la notion de factoriel pour prouver deuxième théorème d'Euclide. Tout ce que nous devons montrer, est que pour tout nombre x, il y a un certain nombre y de telle sorte que tous les nombres compris entre 1 et x sont diviseurs de ce nombre y. Cela peut être prouvé en utilisant le schéma inductif et, de cela, le théorème suivant.