# Quantifying over an empty set: first-order logic

In mathematics it sometime occurs that we might quantify a variable over the empty set. In which case a predicate P is always true. For example, we might have a predicate P(x) which is true for all whole numbers, and predicate Q(y) which is false for all whole numbers.

In such a case the statement

"For all x and y in the natural numbers P(x) implies Q(y)"

Is false. However, the proceeding statement

"For all x in the empty set, and y in the natural numbers P(x) implies Q(y)"

is true, because there are no numbers in the empty set. So, P(x) is a void statement.

My Question Since in the second statement the P(x) is a void statement, why do we conclude that it is false (at least in mathematics)? It could just as well be true, after all it is void.

Note that P(x), without qualifiers or any information describing x as a constant, is neither true nor false: x is a free variable, which is to say a place-holder for an not-yet-specified term. As such, P(x)⇒Q(y), equivalently ¬P(x) ∨ Q(y), is a constraint on as-yet unsupplied terms.

In asking whether ∀x∈∅.P(x)⇒Q(y) is true for some y, we ask whether there is any value of x for which the constraint may be violated. There is not: and this is not because ∀x∈∅.¬P(x) per se (though this is also true), but simply because there are no values of x, and thus none for which P(x) is true.

If you prefer, using the construction ∀x∈D.Φ ≡ ∀x.x∈D⇒Φ, the cause of the truth of ∀x∈∅.P(x)⇒Q(y) is not because P(x) is always false, but because x∈∅ is always false.

• Thanks! I was also thinking that the same thing that "the cause of the truth of ∀x∈∅.P(x)⇒Q(y) is not because P(x) is always false, but because x∈∅ is always false." However, I was wondering if this was the correct way to look at it, because I have never been taught (or have read) to assign a truth value to a quantification. Although, it seemed natural to say that the quantifier is false, and therefore the proposition is false. (Pardon any abuse of vocabulary, my training is quite informal). Nov 17, 2013 at 17:58
• @JimmyJackson: The quantifier isn't what's false, the premise which is implicit in the quantification (rather, the restriction of the quantification) is false for all terms which one might substitute for x. For instance, it isn't clear how one might interpret any truth-valuation for the quantifier in `∀x∈ℤ .(x even and a perfect square ⇒ x a multiple of 4)` if we consider ℤ as a term in ZF set theory. Nov 17, 2013 at 18:38
• In, the example just given we clearly have a true statement. However the validity of the truth-valuation of the quantifier itself is uncertain, because considering the number 1.5 the premise of the quantifier would be false, right? In which case the following predicate statement need not be evaluated, we move on until we find a value which makes the premise of the quantifier is true, then we see that the predicate statement is true. Once we conclude that every time the premise of the quantifier is true, so is the predicate statement.So, the statement is true; is this the right idea? Nov 17, 2013 at 18:59
• @JimmyJackson: yes, basically. Notice that you are actually replacing x in your interpretation with individual terms, so you are not so much "evaluating the quantifier" as you are considering examples and evaluating the restriction of the quantification. For universal quantifiers, the sort of interpretation you describe is broadly correct. Nov 17, 2013 at 22:22

Your example is a little bit tricky : what are we meaning with

"quantifying a variable over the empty set" ?

It depends on the way we choose to restrict the quantifiers.

I'll try to discuss your examples in a more "formal" setting.

1) "For all x and y in the natural numbers, P(x) implies Q(y)", where the predicate P(x) is true for all whole numbers, and the predicate Q(y) is false for all whole numbers.

If we want to have "sets" os values for the variables, we need to use the language of set theory, with the relation ∈ and the individual constant ∅; we will also assume that we have proved in our f-o set theory (e.g.ZFC) the existence of the set N of the natural numbers with the usual properties (like order).

Thus, we may translate 1) as :

(∀x) (∀y) [ (x∈N ∧ y∈N) → (P(x) → Q(y)) ]

Let's define an interpretation where :

P(x) := x >= 0 ; i.e.a predicate that is always true of the natural numbers,

and :

Q(y) := x < 0 ; i.e.a predicate that is always false of the natural numbers.

With this interpretation, (P(x) → Q(y)) is always false of the natural numbers.

But we have the antecedent : (x∈N ∧ y∈N); if we restrict our domain of interpretation to N, it is trivially true but, in a domain D whatever, it need not be so.

Thus, if the domain of the interpretation D is a model of our set theory, we have in it N, but the above formula is again true, because it is not true that all sets are in N.

2) "For all x in the empty set and y in the natural numbers, P(x) implies Q(y)".

Now we translate it as :

(∀x) (∀y) [ (x∈∅ ∧ y∈N) → (P(x) → Q(y)) ]

With the same interpretation as above, (P(x) → Q(y)) is still false, and the antecedent (x∈∅ ∧ y∈N) is always false (because there are no x in ∅). Thus, the complete formula is true in a domain D whatever.

But we may change strategy and forget about set theory.

We will consider now a "pure" f-o formula :

(∀x) (∀y) [ P(x) → Q(y) ].

With the above interpretation of P and Q, in the domain N of the natural numbers it is always false (for the same reason above).

But now we have problems with 2) ; in "pure" f-o language, there is no relation ∈. So, how to translate it ?

We may use a predicate E (for Empty) such that E(x) is always false for each object in the domain (i.e.N) and we get :

(∀x) (∀y) [ E(x) → (P(x) → Q(y)) ] .

In this case, the formula is always true by "definition" of E.

Conclusion

We need to be precise in setting the formal language we are using , because different languages have different "expressive capabilities".

Note

I do not like the expression "P(x) is a void statement"; in "standard" f-o language all predicates are always defined. I.e., for all object d in the (not-empty) domain of interpretation D, P(d) holds or P(d) does not hold.

If in the domain D there are something that is not a number, (∀x) (x >= 0) is false.