\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  

\usepackage{graphicx}

%\usepackage[latin1]{inputenc}

\usepackage{amsmath, amsthm, amssymb}

\usepackage{typearea}

\usepackage{algorithm}

\usepackage{algorithmic}

\usepackage{fullpage}

\usepackage{mathtools}

\usepackage[all]{xy}

\title{Theory I, Sheet 10 Solution}

\author{Eugen Sawin}

\renewcommand{\familydefault}{\sfdefault}

\newcommand{\Pos}{\mathcal{P}os}

\newcommand{\E}{\mathcal{E}}

\newcommand{\D}{\mathcal{D}}

\newcommand{\J}{\mathcal{J}}

\include{pythonlisting}

\pagestyle{empty}

\begin{document}

\maketitle

\section*{Exercise 11.1.1}

We show $attr(\alpha) \subseteq Y \subseteq X \implies \pi[Y](\sigma[\alpha]r) \equiv \sigma[\alpha](\pi[Y]r)$:

\begin{align*}

\pi[Y](\sigma[\alpha]r) &= \{\mu \in Tup(Y) \mid \exists{\mu' \in \sigma[\alpha]r}: \mu = \mu'[Y]\}\\

\sigma[\alpha]r &= \{\mu \in Tup(X) \mid \mu \in r \land \mu \text{ fulfills } \alpha\}

\end{align*}

From $Y \subseteq X$ follows:

\begin{align*}

\pi[Y](\sigma[\alpha]r) &= \{\mu \in Tup(Y) \mid \mu \in r \land \mu \text{ fulfills } \alpha\}\\

\sigma[\alpha](\pi[Y]r) &= \{\mu \in Tup(Y) \mid \mu \in \pi[Y]r \land \mu \text{ fulfills } \alpha\}\\

\pi[Y]r &= \{\mu \in Tup(Y) \mid \exists{\mu' \in r}: \mu = \mu'[Y]\}\\

\end{align*}

Again from $Y \subseteq X$ follows:

\begin{align*}

\sigma[\alpha](\pi[Y]r) &= \{\mu \in Tup(Y) \mid \mu \in r \land \mu \text{ fulfills } \alpha\}\\

\end{align*}

\end{document}