%blatt12
\documentclass[A4,11pt]{article}

\usepackage{lmodern}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{enumerate}
\usepackage[german]{babel}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{multicol}

\usepackage{tikz}
\usetikzlibrary{automata,positioning}

\pagestyle{empty}

\usepackage{fancyhdr}

\pagestyle{fancy}
\fancyhf{}
\theoremstyle{definition}
\newtheorem{ubung}{Aufgabe}
\newtheorem{uebung}{Aufgabe}

\newcommand{\fA}{\mathfrak{A}}
\newcommand{\fB}{\mathfrak{B}}
\newcommand{\fN}{\mathfrak{N}}
\newcommand{\lra}{\leftrightarrow}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\bR}{\mathbb{R}}
\newcommand{\such}{\; : \;}



\begin{document}

\lhead{Logik f\"ur Studierende der Informatik\\
WS 2022/23
}

\rhead{Dozentin: Prof. Dr. Heike Mildenberger\\\
Assistent: M.Sc. Christian Br\"auninger}


$\,$\\
\\
\\
\cfoot{Abgabe per Ilias bis Mittwoch 25.1.2023, 10 Uhr.}



\begin{center}
 \textbf{BLATT 12}\\
 (18.1.2023)
\end{center}


\begin{ubung}[6 Punkte]~\\
Es sei $\tau$ eine beliebgige Symbolmenge. Eine bijektive Abbildung $i:A\to B$ zwischen den Universen zweier $\cL(\tau)$-Strukturen $\fA$ und $\fB$ hei{\ss}t \emph{Isomorphismus von $\fA$ nach $\fB$}, falls
\begin{itemize}
\item[i)] $i(c^\fA)=c^\fB$ f\"ur alle Konstantensymbole $c\in \tau$,
\item[ii)] $i(f^\fA(a_1,\dots,a_n))=f^\fB(i(a_1),\dots,i(a_n)) \;$ f\"ur jedes $n$ und alle $n$-stelligen Funktionssymbole $f\in \tau$ und
\item[iii)] $(a_1,\dots,a_n) \in R^\fA$ genau dann gilt, wenn auch $(i(a_1),\dots,i(a_n))\in R^\fB$ f\"ur jedes $n$ und alle $n$-stelligen Pr\"adikate $R\in \tau$.
\end{itemize}
Zwei $\cL(\tau)$-Strukturen $\fA$ und $\fB$ hei{\ss}en \emph{isomorph}, falls es einen Isomorphismus von $\fA$ nach $\fB$ gibt. Begr\"unden Sie Ihre Antworten auf die folgenden Fragen.
\begin{itemize}
\item[a)] Sei $\tau=\{R\}$ f\"ur ein zweistelliges Pr\"adikat $R$. Sind $(\mathbb{Q},<)$ und $(\bR, <)$ isomorph?
\item[b)] Sei $\tau=\{R\}$ f\"ur ein zweistelliges Pr\"adikat $R$. Sind $({\mathcal P}({\mathbb N}),\subseteq)$ und $(\bR,<)$ isomorph?
\item[c)] Sei $\tau=\{c,f\}$ f\"ur ein Konstantenzeichen $c$ und ein zweistelliges Funktionssymbol $f$.~\\ Sind $(\{2^n\such n\in \mathbb{Z}\},1,\cdot)$ und $(\mathbb{Z},0,+)$ isomorph?
\item[d)] Sei $\tau=\{R\}$ f\"ur ein zweistelliges Pr\"adikat $R$. Welche Eigenschaften muss ein gerichteter Graph haben, damit er als $\cL(\tau)$-Struktur isomorph zu einem ungerichteten Graphen ist?
\item[e)] Sei $\tau$ wieder beliebig, $\fA$ und $\fB$ zwei isomorphe Strukturen und $\varphi$ eine $\cL(\tau)$-Formel. Zeigen Sie: Es gibt genau dann eine Belegung $s$ in $\fA$ mit $\fA\models \varphi[s]$, wenn es eine Belegung $s'$ in $\fB$ mit $\fB\models \varphi[s']$ gibt.
\end{itemize}
\end{ubung}
\medskip


\begin{ubung}[6 Punkte]~\\
Es seien $\varphi,\psi,\varrho$ drei $\cL(\tau)$-Formeln f\"ur eine beliebige Symbolmenge $\tau$. Zeigen oder widerlegen Sie im Hilbertkalk\"ul:
\begin{itemize}
\item[a)] $\vdash ((\varphi \wedge \psi) \to (\varphi \vee \varrho))$
\item[b)] $\neg(\varphi\to\psi) \vdash (\psi \to \varphi)$
\item[c)] $\vdash (\varphi_t^x\to \exists x \varphi)$, wenn $t$ f\"ur $x$ in $\varphi$ eingesetzt werden kann.
\item[d)] $(\varphi\to \psi)\vdash (\exists x\varphi \to \psi)$, wenn $x$ nicht frei in $\varphi$ auftritt.
\end{itemize}
\end{ubung}
\medskip


\begin{ubung}[4 Punkte]~\\
Zeigen Sie den Kompaktheitssatz der Pr\"adikatenlogik:~\\
Eine Formelmenge $\Gamma$ ist genau dann erf\"ullbar, wenn jede endliche Teilmenge von $\Gamma$ erf\"ullbar ist.~\\
\emph{Hinweis:} Verwenden Sie den Vollst\"andigkeitssatz.
\end{ubung}
\medskip



\end{document}