First-order Equivalences When we upgrade from propositional logic to first-order logic, what changes do we need to make to the laws of boolean algebra? Well first off, we can keep all the existing propositional equivalences. For example, x φ ψ x φ ψ . (Technically, we're even making those equivalences stronger, since those meta-variables φ, ψ, θ can now stand for any first-order formula, rather than merely propositional formulas.) But, we also need additional identities to deal with our new-fangled quantifiers. What should these be? The most interesting are those that relate the two kinds of quantifiers. Universal quantification (∀) says that something holds for all members of the domain, and existential quantification (∃) says that something holds for at least one member. Clearly, x φ implies x φ , but the other direction doesn't hold, so that is not an equivalence. Wait just a minute! That implication holds only if the domain is non-empty, so that there is at least one member in it. We'll see this restriction appear a few times. What about x φ ? In English, “for all items x, φ(x) does not hold”. A more natural way to say this is that there is no item x such that φ(x) does hold — that is, x φ . Indeed, this will be one of our new boolean algebra rules. See a list of equivalences with quantifiers. As before, we can use these to show other pairs of formulas equivalent, as in the following examples. Using these identities, we can simplify formulas such as the following: y x Rx Qxy z Rz . 1 y x Rx Qxy z Rz 2≡ y x Rx Qxy z Rz Complementation of ∃ 3≡ y x Rx Qxy z Rz Double Complementation 4≡ x y Rx Qxy z Rz Reordering ∀s 5≡ x y Rx y Qxy z Rz Distribution of ∀ over ∧ 6≡ x Rx y Qxy z Rz Simplification of ∀ (y not free in Rx) 7≡ x Rx y Qxy x Rx renaming 8≡x Rx y Qxy Rx Distribution of ∀ over ∧ 9≡x y Qxy Rx Rx Commutativity of ∧ 10≡x y Qxy Rx Rx Associativity of ∧ 11≡x y Qxy Rx Idempotency of ∧

Admittedly, some of these steps are rather small and obvious (e.g., our use of commutativity and associativity); we include them to illustrate how the identities of propositional logic are also used in first-order logic. An example of xψ ψ where ψ doesn't contain x occurring free: Let ψ be the formula we've seen before, asserting that a positive integer n was noncomposite: j k j k n j 1 k 1 . Since n occurs free, the truth of this formula depends on the value of n. The formula xψ really is equivalent to ψ: It's true for exactly the same values of n. The use of x is essentially a bit of a rus, since x plays no part of the meat of the ψ. However, the following formula is certainly not equivalent: nψ. This formula asserts that all elements of the domain are non-composite (and it doesn't depend on choosing a particular interpretation for n). Because n occurred free, we can't use the “simplification of quantifiers” identity on it. Finally, one more variant: jψ. This is equivalent to the original, just like xψ was. Why? The j that occurs inside ψ is a local variable, and is different from any enclosing bindings' j. As we saw, local variables shadow less-local ones, just as in most programming languages. The equivalences for distributing implication over equivalences seem counterintuitive at first glance. Show that the following one holds, given all the identities which don't involve both implication and quantifiers. Assuming that ψ does not have any free occurrences of variable x, x φ ψ x φ ψ . 1x φ ψ 2≡x φ ψ Definition of ⇒ 3≡ x φ ψ Distribution of ∀ over ∨ 4≡ x φ ψ Complementation of ∃ 5≡ x φ ψ Definition of ⇒

Are the following two sentences true? “All flying pigs wear top hats.” p wears_top_hatp (over the domain of flying pigs). “All numbers in the empty set are even.” x evenx (over the empty domain). “Every Pulitzer prize winner I've met thinks I'm smart, and cute, too!” x thinksImSmartAndCutex (over the empty, since I haven't met any Pulitzer prize winners). Each sentence states that some property holds for every member of some set (flying pigs or the empty set), but there are no such members. Such sentences are considered vacuously true. Okay, maybe you believe that the sentences aren't false, but you still want some reason to consider them true. Well, think of their negations: “There exists a flying pig not wearing a top hat.” p wears_top_hatp , over the (empty) domain of flying pigs. You can't go off and find a flying pig which contradicts this, since you can't find any flying pig at all. (Note that the negation isn't “No flying pigs wear top hats.”) “There exists a number in the empty set that is even.” xevenx, over the empty domain. (The negation isn't “No numbers in the empty set are even.”) Since these negations are false, the original sentences must be true. This is also similar to the fact that a simple propositional implication, a b is true, if a is in fact false, regardless of the truth of b; in this crude analogy, a corresponds to “in the domain”. In boolean algebra, we only allow the values and , with no third option. This is sometimes called the law of the excluded middle. Philosophers have developed “trimodal” logics which have a third option, but everything in those logics can be translated into something in traditional logic; such logics might be more convenient in some cases, but they aren't more expressive. ¶ Fuzzy Logic, on the other hand, is a variant where every proposition has a degree of truth (from zero to one). While this is different than propositional logic (and, it is the right way to model many real-world problems), as a logic it hasn't yielded interesting new mathematical results. Even more silliness can ensue when the domain is empty: For example, not only is every member of the empty set even, but every member is simultaneously odd! That is, x Rx Rx is true (only) when the domain is the empty set. Even more degnerately, x is a true (only) on the emtpy domain.