Benutzer:Bocardodarapti/Arbeitsseite/Logik

Logik

Aufgabe

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

Aufgabe

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

Lemma

Es seien ${}x_{1},\ldots ,x_{n}$ Variablen, ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ Terme und ${}\alpha$ ein Ausdruck in einer prädikatenlogischen Sprache ${}L^{S}$.

Dann ist

$\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(\alpha {\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow {\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}.$

Beweis

$\Box$

Das Substitutionsaxiom impliziert die folgende allgemeinere Substitutionstautologie.

Lemma

Es sei ${}S$ ein Symbolalphabet, ${}s_{1},\ldots ,s_{n},t_{1},\ldots ,t_{n}$ seien ${}S$-Terme, ${}x_{1},\ldots ,x_{n}$ verschiedene Variablen und ${}\alpha$ sei ein ${}S$-Ausdruck.

Dann ist

$\vdash s_{1}=t_{1}\wedge \ldots \wedge s_{n}=t_{n}\rightarrow {\left(\alpha {\frac {s_{1},\ldots ,s_{n}}{x_{1},\ldots ,x_{n}}}\rightarrow \alpha {\frac {t_{1},\ldots ,t_{n}}{x_{1},\ldots ,x_{n}}}\right)}$

ableitbar.

Beweis

$\Box$

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 ${}(X,{\mathcal {T}})$ besteht aus einer Menge ${}X$ zusammen mit einer Teilmenge ${}{\mathcal {T}}$ der Potenzmenge von ${}X$, die folgende strukturelle Bedingungen erfüllt (die Teilmengen $U\subseteq X$, die zu ${}{\mathcal {T}}$ gehören, nennt man offene Mengen).

1. Die leere Menge und die ganze Menge ${}X$ sind offen (d.h. gehören zu ${}{\mathcal {T}}$).
2. Der Durchschnitt von endlich vielen offenen Mengen ist wieder offen, d.h. mit ${}U_{1},\ldots ,U_{n}\in {\mathcal {T}}$ ist auch ${}U_{1}\cap \ldots \cap U_{n}\in {\mathcal {T}}$.
3. Die Vereinigung von beliebig vielen offenen Mengen ist wieder offen, d.h. mit ${}U_{i}\in {\mathcal {T}}$ für jedes ${}i\in I$ (zu einer beliebigen Indexmenge ${}I$) ist auch ${}\bigcup _{i\in I}U_{i}\in {\mathcal {T}}$.

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 ${}\in ,\cup ,\cap ,\equiv$ (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 ${}x,y,z,U,V,I,J$ bezeichnen) aus einem einstelligen Funktionssymbol ${}\bigcup$, aus zwei zweistelligen Funktionssymbolen ${}\cup ,\cap$ vier einstelligen Relationssymbolen ${}R_{0},R_{1},R_{2},T$, einem zweistelligen Relationssymbol ${}E$, besteht.

$\forall U\forall V{\left(TU\wedge TV\rightarrow TU\cap V\right)}.$

$\forall I{\left(R_{2}I\rightarrow {\left(\forall U{\left(EUI\rightarrow TU\right)}\rightarrow T\bigcup I\right)}\right)}$

Einen topologischen Raum kann man als eine Interpretation dieser Ausdrucksmenge auffassen, indem man als Grundmenge der Interpretation

$M=X\cup {\mathfrak {P}}\,(X)\cup {\mathfrak {P}}\,({\mathfrak {P}}\,(X))\cup \{\delta \}$

wählt und

$R_{0}^{M}=X,R_{1}^{M}={\mathfrak {P}}\,(X),R_{2}^{M}={\mathfrak {P}}\,({\mathfrak {P}}\,(X)),$

$Exy{\text{ als }}x\in y$

$\cap {\text{ und }}\cup {\text{ als Durchschnitt und Vereinigung von zwei Mengen}}$

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

Wie oben die Gesamtanzahl der Elemente von ${}M$ kann man auch die Anzahl der Elemente in den Klassen ${}M_{i}$ sprachlich charakterisieren, die Eigenschaft, dass es darin mindestens ${}s$ Elemente gibt, beispielsweise durch

$\exists x_{1}\ldots \exists x_{s}{\left(x_{1}\neq x_{2}\wedge \ldots \wedge x_{s-1}\neq x_{s}\wedge \alpha _{i}{\frac {x_{1}}{x}}\wedge \ldots \wedge \alpha _{i}{\frac {x_{s}}{x}}\right)}.$

Die Menge ${}M_{i}$ enthalte nun ${}s_{i}$ Elemente und es sei ${}\beta _{i}$ der in ${}M$ wahre Satz, dass ${}M_{i}$ genau ${}s_{i}$ Elemente enthält. Aufgrund der elementaren Äquivalenz von ${}M$ und ${}N$ gilt dieser Satz auch in ${}N$. D.h. es gibt in ${}N$ für jedes ${}i$ genau ${}s_{i}$ Elemente, für die die Aussage ${}\alpha _{i}$ zutrifft. Diese Teilmenge von ${}N$ bezeichnen wir mit ${}N_{i}$.

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.