|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
proof that  and  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 $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 \begin{eqnarray*} Y \cap C_\cap (X,Y) (Z) &=& Y \cap (X \cup Z) \\ &=& (Y \cap X) \cup (Y \cap Z). \end{eqnarray*}Again, since $Y \cap Z \not= \emptyset$ we also have $(Y \cap X) \cup (Y \cap Z) \not= \emptyset$ so \begin{eqnarray*} 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) \end{eqnarray*}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)$ 
|
"proof that  and  are consequence operators" is owned by rspuzio.
|
|
(view preamble | get metadata)
Cross-references: implies, subset, property, function, definitions, defining properties, satisfy, consequence operators, section, operators, proof
This is version 18 of proof that  and  are consequence operators, born on 2006-12-22, modified 2007-01-16.
Object id is 8670, canonical name is ProofThatC_cupAndC_capAreConsequenceOperators.
Accessed 780 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
|
|
|
|
|
|
|
|
|
|
|
