0

Let $\sqsubseteq$ be the boolean ordering of $X$, so for every $x$ and $y$ applies $x \sqsubseteq y$ if $x \sqcap y = x$. Let $v, w, a, b \in X$ with $v \sqsubseteq a$ and $w \sqsubseteq b$. Show that $v \sqcup w \sqsubseteq a\sqcup b$ and $v \sqcap w \sqsubseteq a\sqcap b$.

Should this be solved algebraically, or in a different way? And if so, where would be my starting point?

Garth Marenghi
  • 1,115

2 Answers2

1

Hint:

  • What you want to prove is that $\sqcup$ and $\sqcap$ are monotone with respect to $\sqsubseteq$.
  • Start with a simple example: prove that the ordinary set operations $\cup$ and $\cap$ are monotone with respect to subset relation $\subseteq$, i.e.

\begin{align} A_1 \subseteq A_2 \land B_1 \subseteq B_2\quad &\implies\quad A_1 \cup B_1 \subseteq A_2 \cup B_2 \\ A_1 \subseteq A_2 \land B_1 \subseteq B_2\quad &\implies\quad A_1 \cap B_1 \subseteq A_2 \cap B_2 \end{align}

  • Transform your proof so that is uses only set-operations and related theorems and axioms.
  • Try to make the proof work for an arbitrary boolean algebra.

I hope this helps $\ddot\smile$

dtldarek
  • 37,381
  • Sorry for my late reaction! I'm not quite sure what you mean with what you wrote with the sets; IFF A is a real subset of Aand B which is a real subset, THEN the union of A and B are a subset of A and B. What is meant with A and B`? – Garth Marenghi Sep 15 '13 at 21:00
  • 1
    @GarthMarenghi Nothing in particular. I changed the notation, is this more clear? – dtldarek Sep 15 '13 at 21:09
  • Thanks for the fast reaction. It is more clear, though I have to really take the time to think about it. I'll do this tomorrow, since it's late here and I really need to go catch some sleep. – Garth Marenghi Sep 15 '13 at 21:18
0

HINT: Work up to it in steps:

  1. Show that if $x\sqsubseteq y$, then $x\sqcap a\sqsubseteq y\sqcap a$.
  2. Show that if $x\sqsubseteq y$, then $x\sqcup a\sqsubseteq y\sqcup a$; you may find it helpful to show first that $x\sqsubseteq y$ iff $x\sqcup y=y$.
  3. Apply (1) and (2) twice to get the desired results.
Brian M. Scott
  • 616,228
  • Well, I can reason that if $x\sqsubseteq y$ (thinking about it in a sets way) that $x$ is contained in $y$. With $a$, two scenario's (well actually three) can happen: either $a$ is contained in $x$, $x$ is contained in $a$, or $x$ is equal to $a$. If $a$ is contained in $x$, that would mean that $x\sqcap a$ would result in $a$. Then that would als mean that $y\sqcap a$ would result in $a$, and so $a\sqsubseteq a$, which is true. On the other hand, if $x$ is contained in $a$, then $x\sqcap a$ would result in $x$ and $y \sqcup a$ would result in $a$. $x\sqsubseteq a$, which is true. – Garth Marenghi Sep 16 '13 at 09:02
  • But saying this is different than putting it down in algebraic formula's! – Garth Marenghi Sep 16 '13 at 09:06
  • @Garth: Don’t bother thinking about the power set algebra. If $x\sqsubseteq y$, then $x\sqcap y=x$, so $$(x\sqcap a)\sqcap(y\sqcap a)=(x\sqcap y)\sqcap a=x\sqcap a;,$$ and therefore $x\sqcap a\sqsubseteq y\sqcap a$. I used only the commutativity and associativity of $\sqcap$ and the identity $z\sqcap z=z$. // If $x\sqsubseteq y$, then $$(x\sqcup y)\sqcap y=(x\sqcap y)\sqcup(y\sqcap y)=(x\sqcap y)\sqcup y=x\sqcup y;,$$ so $x\sqcup y\sqsubseteq y$; ... – Brian M. Scott Sep 16 '13 at 16:53
  • ... and $y\sqsubseteq x\sqcup y$ follows from one of the absorption axioms for Boolean algebras. I’ll leave the rest of (2) and all of (3) for you to try. – Brian M. Scott Sep 16 '13 at 16:54
  • I think I might get it, thank you for your help! – Garth Marenghi Sep 16 '13 at 19:43
  • @Garth: You’re welcome. Let me know if you get stuck on the rest. – Brian M. Scott Sep 16 '13 at 19:43