Kurs:Einführung in die mathematische Logik (Osnabrück 2011-2012)/Arbeitsblatt 6/latex
\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) | >> |
|---|