Fitch Proofs für Zahlentheorie
Hinweis: Die Axiome und Beweise in diesem Dokument beschrieben sind, wurden geschaffen, um die erste Ausgabe des LPL Buch mit und Software (Fitch). In der zweiten Version des Buches sind die Peano Axiome ein wenig anders, eine Nachfolgerfunktion anstelle einer konstanten 1. Verwendung Auch hat die neue Version von Fitch hinzugefügt speziell formale Inferenzregeln mit mathematischen Induktion tun haben, sowie einen Mechanismus erlaubt Nachweis von Dateien auf andere Dateien zu verweisen Beweise für frühere gesicherte (Lemma ist) enthalten. Die Beweis-Dateien für die alte Version von Fitch können in der neuen Version von Fitch geöffnet werden.
Siehe: Numbers (komprimierte Ordner von 16 PRF-Dateien)
Anmerkung 2: I umgewandelt, um den Nachweis der es keine größte Primzahl zur zweiten Auflage zu sein. Aufgrund der Art und Weise Lemma Dateien jedes Mal enthalten sind ein Verweis auf das Lemma hergestellt ist, wuchs die ursprüngliche Beweis Datei auf etwa 3 Mb und dauerte ca. 3 Stunden zu speichern. Ich habe seit dem Beweis geändert, so dass es weniger auf Lemma ist verlassen. Es ist jetzt etwa 600 Kb, und dauert etwa 20 Minuten zu speichern. Hier ist der neue Beweis (komprimierte Ordner von 11 PRF-Dateien). Ich habe auch alle Beweise aus der ursprünglichen Version umgewandelt (und hinzugefügt einige mehr) 100 Beweise für insgesamt knapp über, aber ich fühlte eine .zip-Datei zu groß sein würde, zu schreiben. Außerdem hat das LPL Buch dieser Beweise einige wie im Buch ausübt.
Einige Proofs der Zahlentheorie in Fitch
Das Buch Sprache, Proof- und Logik, von Barwise und Etchemendy legt einen formalen Beweis System aus F, die für die Konstruktion der formalen Logik Beweise eine Reihe von formalen Ableitungsregeln definiert. Das Buch kommt mit einigen Übungen, die den Benutzer auffordern, einen formalen Beweis mit Hilfe des Software-Programm Fitch, die eine grafische Benutzeroberfläche bietet zu konstruieren für Benutzer formale Beweise gemäß System F. Teil I und II zu schaffen, die das Buch Layout des Basissysteme propositionaler und Prädikatenlogik, während Teil III des Buches in einigen Anwendungen und Metatheorie geht. Dieses Dokument befasst sich mit einer bestimmten Anwendung, die Zahlentheorie (Arithmetik) ist, und sieht, welche Arten von Theoremen in Fitch über diese Domäne nachgewiesen werden.
Die Axiome von Peano Arithmetik
Abschnitt 16.4 des LPL Buch, genannt „axiomatisieren die natürlichen Zahlen“, legt 7 Axiome und ein Axiom Schema für die natürlichen Zahlen:
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
Induktions-Axiom Scheme: für jede Formel P (x) (a-Formel mit einer freien Variablen x) die folgende Anweisung ist ein Axiom:
(P (0) - Ax (P (x) -> P (x + 1))) -> Ax P (x)
Zusammen werden diese 7 Axiome und das Induktions Axiom Schema Peano Arithmetik (PA) genannt. Mit PA, können wir alle Arten von Theoremen über die natürlichen Zahlen beweisen.
Die Sprache der Arithmetik und der Standard Interpretation
Die Axiome in PA verwenden Sie die folgenden nicht-logischen Symbole: 0, 1, + und *. 0 und 1 sind einzelne Konstanten (oder konstante Symbole) und + und * Funktionssymbole. Diese vier Symbole bilden die Sprache der Arithmetik (LA). Das heißt, können wir sagen, dass LA =. Nicht logische Symbole kann man will in irgendeiner Weise interpretiert werden. Zum Beispiel, aber unter der Standardinterpretation der Sprache der Arithmetik werden die Symbole genau interpretiert als man erwartet: 0 ist die Zahl Null, 1 ist die Nummer eins, + ist die Funktion der Zugabe und * ist die Funktion der Multiplikation. Somit wird unter der Standard-Interpretation, die komplexe Term (1 + 1) * (1 + 1) ausgewertet wird, die die Anzahl vier.
Einige sehr grundlegende Wahrheiten
Zunächst einmal, Peano Axiome 1 bis 7 allein mit (lassen Sie uns auf diesen Satz von Axiomen als PA 1-7 beziehen) wir einfache Dinge beweisen können, wie
1 = 0, 2 + 2 = 4 und 1 * 1 = 1 Natürlich, da wir nur Konstanten 0 und 1 haben, mit zu arbeiten, müssen wir eine Konvention verwenden Zahlen darzustellen als 0 und 1. Wir werden verwenden, um die Konvention, dass eine Anzahl N, wie dargestellt ist (((((. (1 + 1) + 1) + 1) + 1) + 1). + 1) + 1 (dh ein Komplex Term n 1'en in dem Muster Einbeziehung as) gezeigt, und wir auf diese Darstellung, wie n beziehen. Im Allgemeinen kann man beweisen, dass man formal aus PA ableiten 1-7:
1) T = a. für jeden Begriff t, die die Nummer unter der Standardinterpretation einer auswertet (schreiben wir dies als N (t) = a)
t = ein für jede Laufzeit t, die unter der Standardinterpretation ausgewertet zu einer anderen Zahl als ein
Daraus folgt unmittelbar, dass:
3) PA1-7 | - t1 = t2, für alle Bedingungen T1 und T2 für die N (t1) = N (t 2)
t1 = t2, für alle Bedingungen T1 und T2 für die N (t1)! = N (t 2)
Insbesondere können wir von PA1-7 beweisen:
a = b für alle Zahlen a und b, für die a! = b
Allerdings kann man nicht Ax Ay x + y = y + x aus PA 1-7 (in der Tat ableiten, können wir beweisen, dass diese nicht durch die Berücksichtigung nicht-Standard-Interpretationen für die Sprache der Arithmetik abgeleitet wird, in dem PA 1-7 Halt , aber in denen Ay Ax x + y = y + x nicht gilt). Glücklicherweise durch das Induktionsschema hinzugefügt hat, können wir Ax Ay x + y = y + x, das heißt die letzte Aussage von PA bewiesen werden kann, beweisen.
Grund additiven und multiplikativen Eigenschaften
Mit Hilfe der Voll PA, können wir verschiedene Sätze in Bezug auf grundlegende Eigenschaften der Addition und Multiplikation, unter Beweis stellen, wie:
Ay Ax Az (x + y) + z = x + (y + z) (Verband der Zugabe)
Ay Ax x + y = y + x (Commutation Zugabe)
Ax Ay Az (x * y) * z = x * (y * z) (Verband der Multiplikation)
Ax Ay x * y = y * x (Vermittlungs- der Multiplikation)
Ay Ax Az x * (y + z) = (x * y) + (x * z) (Verteilung der Multiplikation über Addition)
Ein sehr nützlicher Satz, daß man oft mit endet ist die folgende:
x = 0 -> Ey y + 1 = x)
Addition und Multiplikation mit 0 und 1
Siehe: Additon.prf, Multiplication.prf
Die kleiner ist als Beziehung
Manchmal wollen wir einige neue Symbole zu unserer Sprache einzuführen, um uns einige nützliche Konzept sprechen über zu helfen. Ein elementares und wichtiges Konzept ist die kleinere als Beziehung, die wir definieren als:
Ax Ay (x < y <-> Ez (
z = 0 - x + z = y)
Wenn wir diese Definition als Axiom in unser System PA hinzugefügt haben, können wir jetzt Dinge beweisen, wie 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) und die letztere Aussage können aus dem ursprünglichen PA abgeleitet werden.
Starke oder vollständige Induktion
Ax (ay (y < x -> P (y)) -> P (x)) -> Ax P (x)
Während diese induktive Schema als das induktive Schema stärker zu sein scheint, wir haben, stellt sich heraus, dass wir dieses starke Programm von der (schwachen) induktive Schema tatsächlich nachweisen können, die wir bereits haben. Wir können natürlich auch die schwächere Version von der stärkeren Version beweisen.
In dem Buch Berechenbarkeit und Logik, 5. Auflage, Boolos, Burgess und Jeffrey System Q definieren, die von 10 elementaren Axiome bezüglich Addition, Multiplikation besteht, und der kleiner ist als Beziehung. Dieses System von theoretischem Interesse ist, wie in dem Buch zeigen die Autoren, dass für jede rekursiv abzählbaren Menge von Axiomen, die arithmetisch Sound ist (dh, von dem man keine arithmetischen Unwahrheiten nicht ableiten kann) und die in der Lage ist, diese 10 Axiome zu beweisen, kann man bauen ein Godel Satz, der ein wahrer arithmetischer Satz ist, dass in diesem System beweist nicht möglich ist. Daher ist ein solches System arithmetisch unvollständig: nicht alle arithmetischen Wahrheiten kann aus einem solchen Satz von Axiome ableiten. Es stellt sich heraus, dass PA ist genau ein solches System: es arithmetisch Sound ist, rekursiv abzählbar, und als die Fitch-Datei zeigt, werden alle 10 Axiome von Q können in System PA abgeleitet werden. In der Tat sind die ersten 6 Axiome (Q1 bis Q6) eine Teilmenge von PA 1-7 und Axiome Q7 bis Q10 aus PA viele der zuvor gewonnenes basisches Ergebnisse in Bezug auf die kleinere als Beziehung unter Verwendung abgeleitet werden. Deshalb können wir schließen, dass PA unvollständig ist. Das ist ein doofe. Dennoch wollen wir mal sehen, was wir beweisen können!
Die Kürzungsregeln
Nun, da wir unsere grundlegenden arithmetischen Regeln eingerichtet haben, können wir noch einige ‚interessante‘ Ergebnisse versuchen und beweisen. Das erste Ergebnis ist, dass jede Zahl ist entweder gerade oder ungerade (in einem exklusiven Sinne natürlich!). Dazu werden wir die folgenden formalen Definitionen der Begriffe gerade und ungerade verwenden:
Ax (Even (x) <-> Ey (1 + 1) * y = x)
Ax (Odd (x) <-> Ey (1 + 1) * y + 1 = x)
Interessanterweise muss man das induktive Schema verwenden, um nachzuweisen, dass jede Zahl entweder selbst oder ungerade, aber nicht beide. Ohne sie Nicht-Standard-Interpretationen erlauben Objekte in seiner Domäne weder gerade noch ungerade oder zu sein, sowohl gerade und ungerade zu sein! Sobald die exklusive Disjunktion obwohl bewiesen ist, folgen viele bekannte Eigenschaften von geraden und ungeraden Zahlen.
Die Quadratwurzel von 2 ist keine rationale Zahl
Hier ist ein berühmter Satz: die Quadratwurzel von 2 ist keine rationale Zahl. Der Beweis dieses Ergebnisses ist bekannt und beruht auf dem Konzept der geraden Zahlen. Bei der vorherigen Definition und Theoreme evenhood in Kraft in Bezug, können wir in der Tat dieses Ergebnis beweisen. Der einzige schwierige Teil ist hier, wie dieser Satz auszudrücken. Das heißt, während wir in der Regel diesen Satz aussprechen wie: Es gibt keine Zahlen a und b, so dass sqrt (2) a / b =, wir haben keine / oder sqrt Funktionen definiert. Auch drückend mehr, wenn wir würden, würden wir plötzlich über nicht-natürliche Zahlen sprechen müssen, während die beabsichtigte Domain hat immer nur die natürlichen Zahlen gewesen. Glücklicherweise sqrt (2) = kann a / b neu geschrieben werden als 2 * b * b = a * a (unter der Annahme, b nicht 0 ist) und damit der Satz, die wir nachweisen können (siehe Rationals.prf) wird:
y = 0 - x * x = 2 * y * y)
Es gibt keine größte Primzahl
Siehe: Divisors.prf, Factorial.prf, DivFac.prf und PrimesFac.prf
Schließlich wollen wir einen anderen berühmten Satz von Arithmetik beweisen: dass es keine größte Primzahl (und damit, dass es unendlich viele Primzahlen). Dieser Satz wird auch als Euklids zweiten Satz bekannt. Wie üblich mit einem neuen Konzept, dann ist es sinnvoll, den Begriff einer Primzahl zu versuchen und formal zu definieren. Mathematicians definiert eine Primzahl als eine Zahl, die genau zwei (das heißt zwei verschiedene) Divisoren: 1 aufweisen und selbst. Beachten Sie, dass diese Definition Regeln aus 0 und 1 als Primzahlen, die einen guten Grund hat. Mathematikern nicht immer 1 betrachten wie keine Primzahl ist: Seit dem 1. keine Teilern außer 1 und sich selbst hat (das ist eine durchaus vernünftige Art und Weise Primzahlen zu definieren, zu sein scheint), ist es für eine Weile war als bester angesehen. Doch dabei der Fundamentalsatz der Arithmetik, die besagt, dass jede Zahl eine eindeutige Primfaktorzerlegung hat, nicht mehr hält. Also, um sicherzustellen, dass der Fundamentalsatz der Arithmetik nicht halten, wurde die Definition der aktuellen Definition geändert:
Ax Ay (Div (x, y) <-> (
x = 0 - Ez x * z = y))
x = 1 - Ay (Div (y, x) <-> (Y = 1 v y = x))))
Je mehr schwierige Teil dieses Beweises ist, wenn man an dem typischen Beweis dieses Satzes sieht, die den Begriff eines faktoriellen verwendet. Jetzt können wir sehr leicht die Vorstellung eines faktoriellen definieren:
Ax fac (x + 1) = (x + 1) * FAC (x)
Mit dieser Definition und die verschiedenen Sätze, die von ihm bewiesen werden kann, können wir jetzt in der Tat beweisen Euklids zweiten Satz.
Es gibt keine größte Primzahl (alternativer Beweis)
Siehe: Divisors.prf, Primes.prf
Leider ist die Definition der Fakultäts nicht ein, dass wir einfach ‚abschieben‘. Für eine Konstruktion wie Ax (P (x) <-> phi (x)), die als eine Definition von P (x) dient, können wir immer einfach ersetzen phi (x) wieder in irgendwelche Beweise in Bezug auf P (x), damit die ultimative Ergebnisse zu zeigen, konnte die ursprüngliche Sprache bewährt haben mit von allein (siehe die kleiner ist als Abschnitt). Aber das wird nicht bei dieser Definition des Fakultäts arbeiten. Also, wenn wir sicherstellen möchten, dass das, was wir beweisen können, in der Tat letztlich aus PA allein nachgewiesen werden (das heißt ohne zusätzliche definitorischen Axiome), haben wir etwas anderes zu tun.
Zum Glück, wir haben nicht den Begriff der Fakultäts verwenden, um Euklids zweiten Satz zu beweisen. Alles, was wir zeigen müssen, ist, dass für jede Zahl x gibt es eine Zahl y, so ist, dass alle Zahlen zwischen 1 und x Teilern dieser Zahl y. Dies kann mit dem induktiven Schema nachgewiesen werden und daraus folgt der Satz.