# 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_{\cap}(X,Y)\colon\mathcal{P}(L)\to\mathcal{P}(L)$ is defined as follows:

 $C_{\cap}(X,Y)(Z)=\begin{cases}X\cup Z&Y\cap Z\not=\emptyset\\ Z&Y\cap Z=\emptyset\end{cases}$
###### Theorem 1.

For every choice of two elements, $X$ and $Y$, of a given set $L$, the function $C_{\cap}(X,Y)$ 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=\emptyset$, 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\not=\emptyset$, then

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

Again, since $Y\cap Z\not=\emptyset$, we also have $(Y\cap X)\cup(Y\cap Z)\not=\emptyset$, so

 $\displaystyle C_{\cap}(X,Y)(C_{\cap}(X,Y)(Z))$ $\displaystyle=$ $\displaystyle X\cup C_{\cap}(X,Y)(Z)$ $\displaystyle=$ $\displaystyle X\cup(X\cup Z)$ $\displaystyle=$ $\displaystyle X\cup Z$ $\displaystyle=$ $\displaystyle 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=\emptyset$ and $Y\cap W=\emptyset$

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=\emptyset$ but $Y\cap W\not=\emptyset$

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\not=\emptyset$ and $Y\cap W\not=\emptyset$

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_{\cup}(X,Y)\colon\mathcal{P}(L)\to\mathcal{P}(L)$ is defined as follows:

 $C_{\cup}(X,Y)(Z)=\begin{cases}X\cup Z&Y\cup Z=Z\\ Z&Y\cup Z\not=Z\end{cases}$
###### Theorem 2.

For every choice of two elements, $X$ and $Y$, of a given set $L$, the function $C_{\cup}(X,Y)$ 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\not=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\not=Z$ and $Y\cup W\not=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 ProofThatCcupAndCcapAreConsequenceOperators 2013-03-22 16:29:41 2013-03-22 16:29:41 rspuzio (6075) rspuzio (6075) 21 rspuzio (6075) Proof msc 03G25 msc 03G10 msc 03B22