0
$\begingroup$

Let $L$ be the set of equivalence classes of statement forms $[\phi]$.

The partial order defined on these classes is the natural partial order of Boolean algebras, i.e., $[\phi]\leq [\psi]$ if and only if $(\phi \Rightarrow \psi)$ is true.

If we denote the set of all equivalence classes of statement forms by $C$, prove that $(C, \leq)$ is a lattice.

I know that the given structure is a lattice iff every two elements have a supremum and an infimum and I feel that the infimum is $[A \wedge \neg A]$, but the supremum I do not know. Could anyone help me?

Thanks.

$\endgroup$
3
  • 1
    $\begingroup$ The infimum (greatest lower bound) of $A$ and $B$ should depend on both $A$ and $B$. Why $A \wedge \neg A$? Also note that the dual of conjunction is disjunction. $\endgroup$ – Fabio Somenzi Mar 19 '17 at 6:17
  • $\begingroup$ @FabioSomenzi part of the definition of a lattice is that a min (bottom) and max (top) exist. I think he was going for that. $\endgroup$ – Henno Brandsma Mar 19 '17 at 6:21
  • $\begingroup$ @HennoBrandsma Possible, but there certainly was some confusion that I was trying to dissipate. I'm glad, though, I didn't start a full answer, which would have mostly duplicated yours. $\endgroup$ – Fabio Somenzi Mar 19 '17 at 6:31
2
$\begingroup$

The infimum (meet) of $[\phi]$ and $[\psi]$ should be $[\phi \land \psi]$, their supremum (join) $[\phi \lor \psi]$, quite as suggested by notation.

$[A \land \lnot A]$ is just the class of the always false statement, so the minimum of the whole lattice ("ex falso quodlibet"), and with $\lor$ it becomes the max of the whole lattice again (any implication with a true conclusion holds).

Of course you still need to verify the infimum properties, using the definitions:

  • $[\phi \land \psi] \le [\phi]$, $[\phi \land \psi] \le [\psi]$

  • if $[\chi] \le [\phi]$ and $[\chi] \le [\psi]$, then $[\chi] \le [\phi \land \psi]$

These should be clear after you use what $\le$ means.

Dually for $[\phi \lor \psi]$ of course as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy