PlanetMath: proof that $C_\cup$ and $C_\cap$ are consequence operators

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (511)
Corrections (9)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

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

(Proof)

The proof that the operators $C_\cup$ and $C_\cap$ defined in the second example of section 3 of the parent entry 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 and two elements, and , of this set, the function $C_\cap (X,Y) \colon \mathcal{P}(L) \to \mathcal{P}(L)$ is defined as follows:

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

Theorem 1 For every choice of two elements, and , of a given set , the function $C_\cap (X,Y)$ is a consequence operator.

Proof.

Property 1: Since 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

$\displaystyle 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

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

Property 3: Suppose that and are subsets of and that is a subset of . 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)$ .

$\qedsymbol$

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

$\begin{displaymath} C_\cup (X,Y)(Z) = \begin{cases} X \cup Z & Y \cup Z = Z \ Z & Y \cup Z \not= Z \end{cases}\end{displaymath}$

Theorem 2 For every choice of two elements, and , of a given set , the function $C_\cup (X,Y)$ is a consequence operator.

Proof.

Property 1: Since 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

$\displaystyle 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

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

Property 3: Suppose that and are subsets of and that is a subset of . 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)$ . $\qedsymbol$

"proof that $C_\cup$ and $C_\cap$ are consequence operators" is owned by rspuzio.

(view preamble)

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: implies, subset, property, function, definitions, defining properties, satisfy, consequence operators, section, operators, proof

This is version 18 of proof that $C_\cup$ and $C_\cap$ are consequence operators, born on 2006-12-22, modified 2007-01-16.
Object id is 8670, canonical name is ProofThatC_cupAndC_capAreConsequenceOperators.
Accessed 497 times total.

Classification:

AMS MSC:	03B22 (Mathematical logic and foundations :: General logic :: Abstract deductive systems)
	03G10 (Mathematical logic and foundations :: Algebraic logic :: Lattices and related structures)
	03G25 (Mathematical logic and foundations :: Algebraic logic :: Other algebras related to logic)

Pending Errata and Addenda

None.[ View all 1 ]

Discussion

forum policy

Interact

post | correct | update request | add example | add (any)