Prove that the set of all equivalence classes of statement forms is a lattice

Question

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.

Answer 1

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.