3

In order theory, there's a variety of duality principles, like:

If a sentence involving only the meet and join operations is a consequence of the lattice axioms, then: the dual sentence, obtained by

  • replacing all meets in the sentence with joins, and

  • replacing all joins in the sentence with meets

is also a consequence of the lattice axioms.

Is there something similar for classical first-order logic? (and/or free logic that allows for empty domains?)

goblin GONE
  • 67,744

2 Answers2

3

In propositional logic you have the notion of a dual sentence.

Let $\varphi$ be a sentence (in propositional logic) written only by using $\land,\lor,\lnot$, we define the dual sentence $\varphi^*$ by replacing all the $\lor$ with $\land$, and vice versa.

Given an assignment, $\sigma$, we define the dual assignment to be $\sigma^*=\mathbf t_\lnot\circ\sigma$, that is $\sigma^*(p)=\sf T$ if and only if $\sigma(p)=\sf F$. (Where $\mathbf t_\lnot$ is the truth function of the $\lnot$ symbol.)

Now we have a nice duality theorem:

$$\operatorname{val}(\varphi,\sigma)^*=\operatorname{val}(\varphi^*,\sigma^*)$$

That is, $\operatorname{val}(\varphi^*,\sigma^*)=\mathbf t_\lnot\circ\operatorname{val}(\varphi,\sigma)$.

Asaf Karagila
  • 393,674
  • Does this principle not extend to predicate logic? Like, what if we require sentences to be written using only $\forall ,\exists \wedge \vee \neg$ and we permute $\forall$ and $\exists$ in addition to $\wedge$ and $\vee$? – goblin GONE May 25 '13 at 09:51
  • That's possible. I haven't ran into this notion, though. To be fair I only know about this one because when I was a TA (and a student) in intro to logic and set theory we gave this as an exercise about propositional logic, to let the students practice the whole "by induction on the complexity of the formula" technique. For predicate logic we had better things to do with them... :-) – Asaf Karagila May 25 '13 at 10:00
1

If ∃xLx, where Lx is the predicate, is a consequence of some axiom set A, then if the all the axioms of A are true, so is ∃xLx. But, this does not imply that A implies ∀xLx. That said, there does exist the quantifier exchange rules of predicate logic which read:

$\lnot$∀x$\lnot$...==∃x... and

$\lnot$∃x$\lnot$...==∀x...

Where "==" indicates logical equivalence.

Doug Spoonwood
  • 11,211