Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 6/latex

Aus Wikiversity

\setcounter{section}{6}

Bei den beiden folgenden Aufgaben soll mit den Peano-Axiomen der zweiten Stufe argumentiert werden.


\inputaufgabegibtloesung
{}
{

Zeige ausgehend von den \definitionsverweis {Dedekind-Peano-Axiomen}{}{,} dass jedes Element
\mathl{n \in {\mathbb N}}{,} $n \neq 0$, einen Vorgänger besitzt.

}
{} {}




\inputaufgabe
{}
{

Man gebe Beispiele $(M,0,')$ für Mengen mit einem ausgezeichneten Element $0 \in M$ und einer Abbildung \maabb {'} {M} {M } {} an, die je zwei der \definitionsverweis {Dedekind-Peano-Axiome}{}{} erfüllen, aber nicht das dritte.

}
{} {}




\inputaufgabe
{}
{

Zeige, dass in der \definitionsverweis {arithmetischen Sprache erster Stufe}{}{} mit den Konstanten
\mathl{0,1}{,} dem Nachfolgersymbol $N$ und den zweistelligen Funktionssymbolen \mathkor {} {+} {und} {\cdot} {} nur abzählbar viele Teilmengen von $\N$ \anfuehrung{adressierbar}{} sind und dass daher das zweitstufige Induktionsaxiom der \definitionsverweis {Dedekind-Peano-Axiome}{}{} nicht in dieser Sprache formulierbar ist.

}
{} {}




\inputaufgabe
{}
{

Zeige, dass man für jede Teilmenge
\mathl{T\subseteq \N}{} die \definitionsverweis {arithmetische Sprache erster Stufe}{}{} um ein einstelliges Relationssymbol $R_T$ und die \definitionsverweis {erststufigen Peano-Axiome}{}{} um geeignete Axiome ergänzen kann, derart, dass diese neue Axiomatik in der Standardinterpretation $\N$ genau dann gilt, wenn $R_T$ als $T$ interpretiert wird. Man folgere daraus, dass mit überabzählbar vielen Relationssymbolen alle Teilmengen der natürlichen Zahlen \anfuehrung{adressierbar}{} sind.

}
{\zusatzklammer {Dies bedeutet aber nicht, dass für jede Struktur einer solchen Axiomatik jede Teilmenge adressierbar ist, noch, dass das zweitstufige Induktionsaxiom, das eine Aussage über alle Teilmengen macht, erststufig formulierbar ist} {} {.}} {}




\inputaufgabegibtloesung
{}
{

Beweise die aussagenlogische Tautologie
\mathdisp {\vdash \alpha\rightarrow (\beta \rightarrow \alpha \wedge \beta)} { }
aus den aussagenlogischen \definitionsverweis {Axiomen}{}{.}

}
{} {}




\inputaufgabe
{}
{

Es seien
\mathl{\alpha_1 , \ldots , \alpha_n}{} Ausdrücke und es seien
\mathl{i_1 , \ldots , i_k}{} Elemente aus
\mathl{\{1 , \ldots , n \}}{.} Zeige, dass
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \alpha_{i_1} \wedge \ldots \wedge \alpha_{i_k}} { }
gilt.

}
{} {}




\inputaufgabe
{}
{

Zeige
\mathdisp {\vdash (\alpha \rightarrow \beta) \wedge (\beta \rightarrow \gamma) \wedge ( \neg \alpha \rightarrow \beta) \rightarrow \gamma} { . }

}
{} {}




\inputaufgabe
{}
{

Begründe die folgende Ableitungsregel: Aus
\mathl{\vdash \alpha}{} und
\mathl{\vdash \alpha \wedge \beta \rightarrow \gamma}{} folgt
\mathl{\vdash \beta \rightarrow \gamma}{.}

}
{} {}




\inputaufgabe
{}
{

Es seien
\mathl{s_1 , \ldots , s_n, t_1 , \ldots , t_n}{} \definitionsverweis {Terme}{}{,} $f$ ein $n$-stelliges Funktionssymbol und $R$ ein $n$-stelliges Relationssymbol. Zeige, dass die folgenden Aussagen im Prädikatenkalkül \definitionsverweis {ableitbar}{}{} sind. \aufzaehlungzwei {
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \rightarrow fs_1 \ldots s_n =ft_1 \ldots t_n} { . }
} {
\mathdisp {\vdash s_1=t_1 \wedge \ldots \wedge s_n=t_n \wedge Rs_1 \ldots s_n \rightarrow Rt_1 \ldots t_n} { . }
}

}
{} {}


<< | Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012) | >>

PDF-Version dieses Arbeitsblattes

Zur Vorlesung (PDF)