0
$\begingroup$

Suppose $L$ is a set with binary operations $\wedge$ and $\vee$, along with the special $T$ and $F$ (for an $x,y,z \in L$) such that the following rules hold:

  1. $x\wedge T=x$; $x\vee y=T$

  2. $x\wedge F=F$; $x\vee F=x$

  3. $x\wedge x=x$; $x\vee x=x$

  4. $x\wedge y=y\wedge x$; $x\vee y=y\vee x$

  5. $(x\wedge y) \wedge z=x\wedge (t\wedge z)$; $(x\vee y)\vee z=x\vee (y\vee z)$

  6. $x\wedge (x\vee y)=x$; $x\vee (x\wedge y)=x$

a) Show that $x \wedge y = x \iff x \vee y= y$

b) Suppose we define the relation $\leq$ by $x\leq y \iff x \wedge y =x$. Show that $\leq$ is a partial order on $L$, that is, show that it is reflexive, antisymmetric, and transitive.

c) Show that $x \wedge y$ is the largest element smaller than both $x$ and $y$ for the partial order.

d) Show that $x \vee y$ is the smallest element larger than both $x$ and $y$ for this partial order.

e) Show that $x\leq T$ and $F\leq x$, for an $x \in L$.

I have this one my test tomorrow and I have no idea on how to get on with this question. Any help will be helpful.

  • 1
    Next time, please edit your original question to include the missing information, rather than deleting it and posting a new one.2012-10-11

2 Answers 2

1

A) We need to relate $\wedge$ and $\vee$ in this question, and the only rule that contains both operations is rule (6). And in fact, that works: $\begin{align*} x &= x\wedge y \\ \Rightarrow x\vee y &= (x\wedge y)\vee y \\ \Rightarrow x\vee y &= y\text{ by rule (6)} \end{align*}$ The reverse implication is similar.

B) Reflexivity is $x\leq x$; using the definition this becomes $x\wedge x = x$, which is rule (3). Transitivity says that if $x\leq y$ and $y\leq z$, then $x\leq z$, i.e., if $x\wedge y= x$ and $y\wedge z = y$, then $x\wedge z$ must equal $x$. Starting with $x\wedge z$ and looking for something to substitute, we get $\begin{align*} x\wedge z &= (x\wedge y)\wedge z\\ &= x\wedge (y\wedge z)\text{ by rule (5)}\\ &= x\wedge y = x. \end{align*}$ As for antisymmetry, suppose $x\leq y$ and $y\leq x$; we want to show that $x=y$. The definition of $\leq$ tells us that $x\wedge y = x$ and $y\wedge x = y$, but by rule (4) these are equal.

C) First we show that $x\wedge y\leq x$, that is, $(x\wedge y) \wedge x= x$. This is true, because $(x\wedge y)\wedge x = x\wedge (x\wedge y) = (x\wedge x)\wedge y = x\wedge y$ by rules (4), (5), and (3), respectively. Similarly, $x\wedge y\leq y$, so $x\wedge y$ is smaller than both $x$ and $y$ in this partial order.

Now suppose $z$ is smaller than $x$ and $y$; we show that $z\leq x\wedge y$, making $x\wedge y$ necessarily the largest element smaller than $x$ and $y$. We have $\begin{align*} z\wedge(x\wedge y) &= (z\wedge x)\wedge y\\ &= z\wedge y\text{ since }z\leq x\\ &= z\text{ since }z\leq y. \end{align*}$ Therefore $z\leq (x\wedge y)$ as desired.

D) We need to show that $x$ and $y$ are smaller than $x\vee y$, and that if $x$ and $y$ are smaller than $z$, then $x\vee y$ is smaller than $z$. By (A), $x\leq y$ is the same as $x\wedge y = x$ is the same as $x\vee y = y$. So we're trying to prove that

  • $x \vee (x\vee y) = x\vee y$
  • $y \vee (x\vee y) = x\vee y$
  • If $x \vee z = z$ and $y \vee z = z$, then $(x\vee y)\vee z = z$.

The proofs from (C) work exactly the same way here, only with $\wedge$ replaced by $\vee$.

E) Proving $x\leq T$ is the same as proving $x\wedge T = x$, which is true by rule (1). Proving $F\leq x$ is the same as proving $F\wedge x = F$, which is true by rule (2).

Good luck on your test!

  • 0
    thank you so much for the help2012-10-11
1

In order.

a) Suppose $x \wedge y = x$. Then $x \vee y = (x \wedge y) \vee y = y$ by 6. The converse is analogous.

b) Reflexivity is 3), Antisymmetry follows from 4), for Transitivity, suppose $x \preceq y, y\preceq z$:

$x \wedge z = (x \wedge y) \wedge z = x \wedge (y \wedge z) = x \wedge y = x$

c) Suppose $z \wedge x = z = z \wedge y$. Then:

$z \wedge (x \wedge y) = (z \wedge x) \wedge y = z \wedge y = z$

so $z \preceq x \wedge y$.

d) By a), replacing all $\wedge$ by $\vee$ in the preceding argument and reversing the $\preceq$ proves the statement.

e) $x \wedge T = x$, i.e. $x \preceq T$. $x \wedge F = F$ i.e. $F \preceq x$.

I hope that helps. Feel free to ask if you don't get something.