Semantic consequence as a partial order

127 Views Asked by At

It is known that semantic consequence is a binary relation over a set of well formed formulas Form(V) (where V is a set of propositional variables). Writing AB means that B is a semantic consequence of A, i.e. every interpretation f for which A is true (f(A)=1) is an interpretation for which B is true (if f(A)=1 then f(B)=1). This binary relation ⊨ is clearly not a partial order in Form(V) as it can be easily shown that it is not antisymmetric. It is however a partial order in Form(V)/≡ where ≡ means “semantic equivalence” (an equivalence relation).

Is the POSET (Form(V)/≡, ⊨) a lattice?

1

There are 1 best solutions below

1
On

You probably mean that $\models$ is not antisymmetric, because it is definitely transitive. Indeed, without taking the quotient we can have different formulas $A$ and $B$ that are equivalent (so $A \models B$ and $B \models A$).

Other than that, transitivity and reflexivity are clear. So $\models$ defines a preorder on the set of formulas, and so we get a partial order on the set of equivalence classes under the relation of "semantic equivalence" as you call it.

This partial order actually has quite a nice structure, namely that of a Boolean algebra (assuming your logic is Boolean), and what you are essentially describing is the Lindenbaum-Tarksi algebra. Note that the Lindenbaum-Tarski algebra is usually formulated in provability, but this will coincide with semantics because of the soundness and completeness theorems.

Edit: I just noticed you were talking about propositional logic. The Lindenbaum-Tarski algebra is actually formulated for full first-order logic. So you get the propositional case as a special case.