Closure for Finite Collection of Relations and Operations

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\RR_1, \RR_2, \ldots \RR_n$ be relations.

Let $\SS_1, \SS_2, \ldots \SS_m$ be operations.

Let $T$ be a small class.


Let the image of $\RR_i$ over any small class $x$ be small classes for $1 \le i \le n$.

Let the image of $\SS_i$ over any Cartesian product $x \times x$ be small classes for $1 \le i \le m$.


Then there exists a small class $X$ such that:

$(1): \quad$ $T \subseteq X$
$(2): \quad$ Each $\RR_i$ is closed with respect to $X$. Each $\SS_i$ is closed with respect to $X \times X$.
$(3): \quad$ $X$ is the smallest small class satisfying conditions $(1)$ and $(2)$ above.

If $Y$ satisfies conditions $(1)$ and $(2)$, then $X \subseteq Y$.


Proof

Let $R \sqbrk x$ denote the image of $x$ under $R$.

Set:

$\displaystyle \map G x = x \cup \bigcup_{i \mathop = 1}^n \mathcal R_i \sqbrk x \cup \bigcup_{i \mathop = 1}^m \SS_i \sqbrk x$

Using the Principle of Recursive Definition, construct the function $F$ as follows:

$\map F 0 = T$
$\map F {n + 1} = \map G {\map F n}$

Define $X$ as follows:

$\displaystyle X = \bigcup_{n \mathop \in \omega} \map F n$


Proof that $T \subseteq X$

\(\displaystyle T\) \(=\) \(\displaystyle \map F 0\) Definition of $F$
\(\displaystyle \) \(\subseteq\) \(\displaystyle \bigcup_{n \mathop \in \omega} \map F n\) Set is Subset of Union

$\Box$


Proof of Closure

Take any $\RR_i$.

Suppose $x \RR_i y$ and $x \in \map F n$ for some $n$.

Then $y \in \map F {n + 1}$ by the definition of image.


Thus $y \in X$ and $R_i$ is closed with respect to $X$.


Similarly, take any $\SS_i$.

Suppose $\paren {x S_i y} = z$ and that $x \in X$ and $y \in X$.

It follows that $x, y \in \map F n$ for some $n$.

So:

$z \in \map F {n + 1}$

Therefore:

$z \in X$

$\Box$


Proof that $X$ is the Smallest Relational Closure

Suppose $T \subseteq Y$ and that $R_i$ and $S_i$ are closed with respect to $Y$.

$\map F n \subseteq Y$ shall be proven by induction:

For all $n \in \omega$, let $\map P n$ be the proposition:

$\map F n \subseteq Y$


Basis for the Induction

$\map P 0$ is the case:

$\map F 0 \subseteq Y$

which has been proved above.

This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 0$, then it logically follows that $\map P {k + 1}$ is true.


So this is our induction hypothesis:

$\map F k \subseteq Y$


Then we need to show:

$\map F {k + 1} \subseteq Y$


Induction Step

This is our induction step:

\(\displaystyle \map F k\) \(\subseteq\) \(\displaystyle Y\) Inductive Hypothesis
\(\displaystyle \leadsto \ \ \) \(\displaystyle R_i \sqbrk {\map F k} \subseteq Y\) \(\land\) \(\displaystyle S_i \sqbrk {\map F k \times \map F k} \subseteq Y\) Image Preserves Subsets and $R_i$ and $S_i$ are closed with respect to $Y$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map F k \cup \bigcup_{i \mathop = 1}^n R_i “ \map F k \cup \bigcup_{i \mathop = 1}^m S_i “ \map F k\) \(\subseteq\) \(\displaystyle Y\) Indexed Union Subset
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map G {\map F k}\) \(\subseteq\) \(\displaystyle Y\) Definition of $G$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map F {k + 1}\) \(\subseteq\) \(\displaystyle Y\) Definition of $\map F {k + 1}$

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\forall n \in \omega: \map F n \subseteq R$

Hence by Indexed Union Subset:

$T \subseteq Y$

$\blacksquare$


Sources