Benutzer:Bocardodarapti/Arbeitsseite/Logik

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Logik

Aufgabe

Kommutativer Halbring/Prim und irreduzibel/Repräsentierbar/Aufgabe


Aufgabe

Kommutativer Halbring/Irreduzibel und prim/In N/Nicht ableitbar/Aufgabe





Lemma  

Es seien Variablen, Terme und ein Ausdruck in einer prädikatenlogischen Sprache .

Dann ist

Beweis  


Das Substitutionsaxiom impliziert die folgende allgemeinere Substitutionstautologie.



Lemma  

Es sei ein Symbolalphabet, seien -Terme, verschiedene Variablen und sei ein -Ausdruck.

Dann ist

ableitbar.

Beweis  




Höhere Sorten

Viele mathematische Strukturen sind deutlich komplexer als die bisher behandelten und es ist nicht unmittelbar klar, wie diese mit einer Sprache erster Stufe erfasst werden können. Wir betrachten die Definition eines topologischen Raumes.


Definition  

Ein topologischer Raum besteht aus einer Menge zusammen mit einer Teilmenge der Potenzmenge von , die folgende strukturelle Bedingungen erfüllt (die Teilmengen , die zu gehören, nennt man offene Mengen).

  1. Die leere Menge und die ganze Menge sind offen (d.h. gehören zu ).
  2. Der Durchschnitt von endlich vielen offenen Mengen ist wieder offen, d.h. mit ist auch .
  3. Die Vereinigung von beliebig vielen offenen Mengen ist wieder offen, d.h. mit für jedes (zu einer beliebigen Indexmenge ) ist auch .

Hier sind die Objekte, über die quantifiziert wird, nicht aus verschiedenen Mengen, die „nebeneinander“ liegen und durch einfache Sortenprädikate getrennt werden können, sondern aus einer Grundmenge, dem Raum, und Teilmengen dieser Menge, und indizierten Familien von solchen Teilmengen. Es besteht also eine mengentheoretische Hierarchie zwischen den beteiligten Objekten. Dies kann man ebenfalls in einer erststufigen prädikatenlogischen Sprache ausdrücken. Allerdings braucht man dazu mengentheoretischen Symbole wie (Mengengleichheit). Der Aufbau der Interpretation schreibt dann aber nicht vor, dass diese auch mengentheoretisch interpretiert werden müssen.


Beispiel  

Wir betrachten ein Symbolalphabet, dass neben Variablen (die wir hier mit bezeichnen) aus einem einstelligen Funktionssymbol , aus zwei zweistelligen Funktionssymbolen vier einstelligen Relationssymbolen , einem zweistelligen Relationssymbol , besteht.


Einen topologischen Raum kann man als eine Interpretation dieser Ausdrucksmenge auffassen, indem man als Grundmenge der Interpretation
wählt und

setzt, wobei man das Ergebnis der Funktionen, für die es keine sinnvolle inhaltliche Interpretation gibt, als ansetzt.









Wie oben die Gesamtanzahl der Elemente von kann man auch die Anzahl der Elemente in den Klassen sprachlich charakterisieren, die Eigenschaft, dass es darin mindestens Elemente gibt, beispielsweise durch

Die Menge enthalte nun Elemente und es sei der in wahre Satz, dass genau Elemente enthält. Aufgrund der elementaren Äquivalenz von und gilt dieser Satz auch in . D.h. es gibt in für jedes genau Elemente, für die die Aussage zutrifft. Diese Teilmenge von bezeichnen wir mit .



In der folgenden Aussage wird ein wichtiger Begriff für eine syntaktische Tautologie, eine Ableitungsregel oder einen ganzen formalen Kalkül verwendet, den der Korrektheit. Er besagt, dass die Tautologie auch (im semantischen Sinn) allgemeingültig ist bzw. dass der Kalkül nur wahre Aussagen liefert. Die weiter oben axiomatisch formulierten aussagenlogischen Tautologien sind korrekt, d.h. sie (und auch jede weitere daraus mittels Modus Ponens ableitbare Tautologie) sind allgemeingültig, wie eine direkte Durchsicht zeigt. Die folgende Aussage zeigt, dass auch die eben postulierten Gleichheitsaxiome allgemeingültig sind und dass der Kalkül daher korrekt ist.