proof that $C_{\cup }$ and $C_{\cap }$ are consequence operators

The proof that the operators $C_{\cup }$ and $C_{\cap }$ defined in the second example of section 3 of the parent entry (http://planetmath.org/ConsequenceOperator) are consequence operators is a relatively straightforward matter of checking that they satisfy the defining properties given there. For convenience, those definitions are reproduced here.

Definition 1.

Given a set $L$ and two elements, $X$ and $Y$, of this set, the function $C_{\mathrm{\cap }}\mathit{}\mathrm{(}X\mathrm{,}Y\mathrm{)}\mathrm{:}\mathrm{P}\mathit{}\mathrm{(}L\mathrm{)}\mathrm{\to }\mathrm{P}\mathit{}\mathrm{(}L\mathrm{)}$ is defined as follows:

Theorem 1.

For every choice of two elements, $X$ and $Y$, of a given set $L$, the function $C_{\mathrm{\cap }}\mathit{}\mathrm{(}X\mathrm{,}Y\mathrm{)}$ is a consequence operator.

Proof.

Property 1: Since $Z$ is a subset of itself and of $X\cup Z$, it follows that $Z\subseteq C_{\cap }(X,Y)(Z)$ in either case.

Property 2: We consider two cases. If $Y\cap Z=\mathrm{\varnothing }$, then $C_{\cap }(X,Y)(Z)=Z$, so

$$C_{\cap }(X,Y)(C_{\cap }(X,Y)(Z))=C_{\cap }(X,Y)(Z).$$

If $Y\cap Z\ne \mathrm{\varnothing }$, then

$Y\cap C_{\cap }(X,Y)(Z)$ $=$ $Y\cap (X\cup Z)$

$=$ $(Y\cap X)\cup (Y\cap Z).$

Again, since $Y\cap Z\ne \mathrm{\varnothing }$, we also have $(Y\cap X)\cup (Y\cap Z)\ne \mathrm{\varnothing }$, so

$C_{\cap }(X,Y)(C_{\cap }(X,Y)(Z))$ $=$ $X\cup C_{\cap }(X,Y)(Z)$

$=$ $X\cup (X\cup Z)$

$=$ $X\cup Z$

$=$ $C_{\cap }(X,Y)(Z)$

So, in both cases, we find that

$$C_{\cap }(X,Y)(C_{\cap }(X,Y)(Z))=C_{\cap }(X,Y)(Z).$$

Property 3: Suppose that $Z$ and $W$ are subsets of $L$ and that $Z$ is a subset of $W$. Then there are three possibilities:

1. $Y\cap Z=\mathrm{\varnothing }$ and $Y\cap W=\mathrm{\varnothing }$

In this case, we have $C_{\cap }(X,Y)(Z)=Z$ and $C_{\cap }(X,Y)(W)=W$, so $C_{\cap }(X,Y)(Z)\subseteq C_{\cap }(X,Y)(W)$.

2. $Y\cap Z=\mathrm{\varnothing }$ but $Y\cap W\ne \mathrm{\varnothing }$

In this case, $C_{\cap }(X,Y)(Z)=Z$ and $C_{\cap }(X,Y)(W)=X\cup W$. Since $Z\subseteq W$ implies $Z\subseteq X\cup W$, we have $C_{\cap }(X,Y)(Z)\subseteq C_{\cap }(X,Y)(W)$.

3. $Y\cap Z\ne \mathrm{\varnothing }$ and $Y\cap W\ne \mathrm{\varnothing }$

In this case, $C_{\cap }(X,Y)(Z)=X\cup Z$ and $C_{\cap }(X,Y)(W)=X\cup W$. Since $Z\subseteq W$ implies $X\cup Z\subseteq X\cup W$, we have $C_{\cap }(X,Y)(Z)\subseteq C_{\cap }(X,Y)(W)$.

∎

Definition 2.

Given a set $L$ and two elements, $X$ and $Y$, of this set, the function $C_{\mathrm{\cup }}\mathit{}\mathrm{(}X\mathrm{,}Y\mathrm{)}\mathrm{:}\mathrm{P}\mathit{}\mathrm{(}L\mathrm{)}\mathrm{\to }\mathrm{P}\mathit{}\mathrm{(}L\mathrm{)}$ is defined as follows:

Theorem 2.

For every choice of two elements, $X$ and $Y$, of a given set $L$, the function $C_{\mathrm{\cup }}\mathit{}\mathrm{(}X\mathrm{,}Y\mathrm{)}$ is a consequence operator.

Proof.

Property 1: Since $Z$ is a subset of itself and of $X\cup Z$, it follows that $Z\subseteq C_{\cup }(X,Y)(Z)$ in either case.

Property 2: We consider two cases. If $C_{\cup }(X,Y)(Z)=Z$, then

$$C_{\cup }(X,Y)(C_{\cup }(X,Y)(Z))=C_{\cup }(X,Y)(Z).$$

If $C_{\cup }(X,Y)(Z)=X\cup Z$, then we note that, because $X\cup (X\cup Z)=X\cup Z$, we must have $C_{\cup }(X,Y)(X\cup Z)=X\cup Z$ whether or not $Y\cup (X\cup Z)=X\cup Z$, so

$$C_{\cup }(X,Y)(C_{\cup }(X,Y)(Z))=C_{\cup }(X,Y)(Z).$$

Property 3: Suppose that $Z$ and $W$ are subsets of $L$ and that $Z$ is a subset of $W$. Then there are three possibilities:

1. $Y\cup Z=Z$ and $Y\cup W=W$

In this case, we have $C_{\cup }(X,Y)(Z)=X\cup Z$ and $C_{\cup }(X,Y)(W)=X\cup W$. Since $Z\subseteq W$ implies $X\cup Z\subseteq X\cup W$, we have $C_{\cup }(X,Y)(Z)\subseteq C_{\cup }(X,Y)(W)$.

2. $Y\cup Z\ne Z$ but $Y\cup W=W$

In this case, $C_{\cup }(X,Y)(Z)=Z$ and $C_{\cup }(X,Y)(W)=X\cup W$. Since $Z\subseteq W$ implies $Z\subseteq X\cup W$, we have $C_{\cup }(X,Y)(Z)\subseteq C_{\cup }(X,Y)(W)$.

3. $Y\cup Z\ne Z$ and $Y\cup W\ne W$

In this case, $C_{\cup }(X,Y)(Z)=Z$ and $C_{\cup }(X,Y)(W)=W$, so $C_{\cup }(X,Y)(Z)\subseteq C_{\cup }(X,Y)(W)$. ∎

Title	proof that $C_{\cup }$ and $C_{\cap }$ are consequence operators
Canonical name	ProofThatCcupAndCcapAreConsequenceOperators
Date of creation	2013-03-22 16:29:41
Last modified on	2013-03-22 16:29:41
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	21
Author	rspuzio (6075)
Entry type	Proof
Classification	msc 03G25
Classification	msc 03G10
Classification	msc 03B22