Quantifiers in connection to AND and OR
In the most common forms of predicate logic, ∀ and ∃ act like a sort of logical conjunction (AND) across all objects, and logical disjunction (OR) across all objects, respectively.
Connection between ∀ and 'AND'
Consider an argument in which the only 'objects' are Scottish people, and let EPP(x) = "x eats their porridge plain". Then
∀x : EPP(x)
translates (with somewhat less social grace than one might use in daily speech) as
For every [Scottish person] x: x eats their porridge plain
which we might better render as
Every Scot eats their porridge plain.
If we suppose that one is a 'Scot' if and only if one was either born in Scotland, or is a British citizen living in Scotland for at least 90% of their life, then there are only finitely many Scots; so we could also imagine producing a list of all Scots ("Angus", "Maeve", "Bruce", "Caroline", ...), in which case it's equivalent to
(Angus eats his porridge plain) AND (Maeve eats her porridge plain) AND ...
which is not a terribly convenient way to express the same thing, but it is still equivalent so long as we list all Scots, and no person (or thing) which is not a Scot. The ∀ symbol is more powerful in this way — it allows us to express a notion
- without having to refer to every object meeting some criterion;
- without even having to commit to a definite list of all objects in the universe of discourse; and
- in other contexts, such as when the universe of discourse are mathematical objects such as numbers, without even commenting on whether there even exists a finite list of objects under consideration.
Especially in the last case, ∀ allows us to potentially express something which is true about a collection which is infinite, or whose extent we do not yet know. But even so, the way in which it behaves is very much like a logical 'AND' of the same property, across all of the objects in the "domain of discourse".
Connection between ∃ and 'OR'
In the same way as ∀ expresses something like an 'AND' across all objects being considered, ∃ expresses something like an 'OR'. Suppose the domain of discourse is people in some specific room (which I will refer to as 'this' room; you can imagine the speaker being in the room themselves), and M(x) = "x is a murderer". Then
∃x : M(x)
translates as
There exists a [person in this room] x: x is a murderer
which we might better render as
Some person in this room is a murderer.
We sometimes say instead something like 'There is a murderer in this room', but without meaning to definitely assert that there is exactly one such person. Again, if we suppose that there are only finitely many people in the room ("Colonel Mustard", "Mrs. Peacock", "Professor Plum", ...) then this statement is equivalent to
Either (Colonel Mustard is a murderer) OR (Mrs. Peacock is a murderer) OR ...
which again is inconvenient but in principle equivalent to the statement with ∃ so long as the list contains all people in the room, and only people in the room.
Restricted quantification
It would be nice to be able to talk about All Scottish people who drink whiskey instead, but without changing the universe of discourse; or indeed to talk about more than just Scottish people all the time. The way we do this is by introducing ways to restrict the quantification.
For the existential quantifier, this is easy and obvious. For instance, suppose we let the universe of discourse be everything on Earth, inlcuding Scottish people, Chinese people, honey, molasses, ants, and so forth. We can recover statements about Scottish people using a predicate S(x) = "x is a Scottish person"; so that we can render
There is a Scot who eats their porridge plain
as "there is [something] which is both a Scottish person and who eats their porridge plain"; or
∃x: S(x) & EPP(x).
We can do something similar for universal quantification. For instance, if we want to talk about things which are true for all Scots, we can do this by making a statement which is true of any object x, if x is a Scot. For instance,
All Scots eat their porridge plain
may be described as "any [thing] which is a Scottish person eats their porridge plain", or "for any [thing] x: if x is a Scottish person, then x eats their porridge plain", which we can render as
∀x: S(x) ⇒ EPP(x).
This tends to be so useful a way of describing things that we define a notation for it, perhaps along the following lines:
∃x∈S: P ≡ ∃x: [ S(x) & P ]
∀x∈S: P ≡ ∀x: [ S(x) ⇒ P ]
where what I've written on the left is basically treating S as the description of a set — for instance, the set of all Scottish people. (Notations will vary in different communities.) These two 'limited' quantifications act exactly as though they are normal ∀ and ∃ quantifiers, except that they range over those objects x which satisfy S(x).
Connection between ∀ and ∃ using de Morgan's Laws
You might wonder why, with the restricted quantifcation over S, we use S(x) & P for the existential quantification over S, and S(x) ⇒ P for the universal quantification over S. The answer is hidden in the connection between the quantifiers and the AND and OR connectives: there is a connection between ∀ and ∃ through de Morgan's Laws in classical logic. This is true whether we use restricted quantifiers, or unrestricted quantifiers.
For instance, consider the case where Scottish people are again the universe of discourse. Suppose that we interpret ¬EPP(x) as meaning "x adds something to their porridge when they eat it". Then the following statements are equivalent:
∀x: EPP(x) — Every Scot eats their porridge plain
¬∃x: [¬EPP(x)] — No Scot adds anything to their porridge
(Why do we change the word 'something' to 'anything' in the sentence above? Basically because the opposite of "some" in English is "not any".) We can see this using the description in terms of AND and OR:
¬ ∃x: [¬EPP(x)] — No Scot adds anything to their porridge when they eat it
can be interpreted, using our list of Scottish people, as
¬[ (Angus eats his porridge with something added) OR (Maeve eats her porridge with something added) OR ... ]
which is equivalent to
¬(Angus eats his porridge with something added) AND ¬(Maeve eats her porridge with something added) AND ...
≡ (Angus eats his porridge plain) AND (Maeve eats her porridge plain) AND ...
which is the same as ∀x: EPP(x) as before. Conversely, if there is some Scot who eats their porridge with something added, we have
∃x: [¬EPP(x)] — Some Scot adds something to their porridge when they eat it
which with our list of Scottish people becomes
(Angus eats his porridge with something added) OR (Maeve eats her porridge plain) OR ...
≡ ¬(Angus eats his porridge plain) OR ¬(Maeve eats her porridge plain) OR ...
which, using de Morgan's Law, gives us
¬[ (Angus eats his porridge plain) AND (Maeve eats her porridge plain) AND ... ]
which is just ¬∀x:EPP(x), or
Not all Scots eat their porridge plain.
In summary, for any property P, we have the following equivalences:
No object x is P — All objects x are not-P; or
¬∃x: P(x) ≡ ∀x: ¬P(x).
Some object x is not-P — Not all objects x are P; or
∃x: ¬P(x) ≡ ¬∀x: P(x).
The same is true if we use restricted quantification. For any property S, and any proposition P, we have the following equivalences:
¬∀x∈S: P
≡ ¬∀x: [ S(x) ⇒ P ]
≡ ¬∀x: [ ¬S(x) ∨ P ]
≡ ∃x: ¬[ ¬S(x) ∨ P ]
≡ ∃x: [ S(x) & ¬P ]
≡ ∃x∈S: ¬P
and also
¬∃x∈S: P
≡ ¬∃x: [ S(x) & P ]
≡ ∀x: ¬[ S(x) & P ]
≡ ∀x: [ ¬S(x) ∨ ¬P ]
≡ ∀x: [ S(x) ⇒ ¬P ]
≡ ∀x∈S: ¬P .
The reason for the different connectives, when defining the restricted quantifications, is essentially that this is what we need to have in order to allow the restricted quantifications to behave as if they were 'normal' quantifications on the smaller domain.
Understanding ∀ and ∃ in plain English
Using all of the above, we can understand how sentences in everyday language can be described in terms of the quantifiers. In the end, it boils down to understanding things in terms of "some" or "all", and then translating them formally.
"No X" or "None of X" are universal statements.
Why? Because "none" is the negation of "some". So, if we say "No X is P", we are really saying
There does not exist an X which is P
or equivalently
¬∃x∈X: P(x)
≡ ∀x∈X: ¬P(x)
which is a universal statement.
"Some X" statements are existential statements.
This is true whether or not we're talking about some X having a property, or some X lacking a property. Why? In this case, it's right there in the language. If we say "some X are P", we are saying
There exists an X which is P
or equivalently
∃x∈X: P(x).
Similarly, if we say "some X are not P", we are saying
There exists an X which is not-P
or equivalently
∃x∈X: ¬P(x).
So both of these are obviously existential.
"All X" and "every X" statements are universal statements.
This is again true whether or not we're talking about some X having a property, or some X lacking a property, and as in the case of "some" statements, it's right there in the language: an "all" statement will boil down to something of the form
∀x∈X: P(x) or ∀x∈X: ¬P(x),
depending on whether it's about whether every object is P, or every object is not-P.
"Any X" statements are universal statements.
You have to be careful to think about how the word 'any' is used. We often ask in English: are there any of [some object]? This
question might be one about existential quantification, but it
certainly is not an existential proposition — nor a
proposition of any kind.
If you think of any statement (as opposed to the question) of the form "any X", it should be fairly clear that it has to do with something which said to be true of all obejcts. "Anyone who is born in Scotland is Scottish" is a statement about all people who are born in Scotland; "The square of any integer is another integer" is a statement about something which holds for every integer. So an "Any X is P" statement translates as
∀x∈X: P.
This is also true of "there aren't any X" statements, of the sort connected with the question "are there any?" If we say that there aren't any, we assert that there are none of X; so as we observed above, we're asserting
¬∃x∈X: P ≡ ∀x∈X: ¬P.
In this way, by carefully considering what is being stated, we can convert it to a statement about existence, not-existence, or something which is true for all objects, and then transform it into something which is obviously existential (∃) or obviously universal (∀).
On the order of quantifiers
It's important to remember that the order of the quantifiers matter — you often cannot re-order them without changing the meaning.
You can change the order of two adjacent existential quantifiers, essentially because OR is commutative and associative: remember that a v b v c is the same as c v a v b, and so on. So if c = "eating cheese", and if A(x,t,a) means that "x is a place and t is a time when doing a is appropriate", then
∃x ∃t: A(x,t,c) and ∃t ∃x: A(x,t,c)
both mean essentially there is a time and a place for eating cheese; the difference amounts to whether the disjunction first iterates through possible places and then (for each place) considers possible times to find if there is an appropriate time at that place; or whether instead the disjunction first iterates through possible times and then, for each time, considers possible places to find out if there is an appropriate place at that time.
Similarly, you can change the order of any adjacent universal quantifiers. If you're an extreme cheese enthusiast, you might want to assert the following (both of which are equivalent):
∀x ∀t: A(x,t,c) and ∀t ∀x: A(x,t,c)
both of which mean that every time and every place is a good time and place to eat cheese — it doesn't matter which time you consider, every place is good; and it doesn't matter what place you're at, anytime is good.
HOWEVER — you cannot change the order of universal quantifiers and existential quantifiers without changing the meaning. Rather than just fixating on eating cheese, let's consider all possible sorts of activity. Then
∀ a ∃x ∃t: A(x,t,a)
means that for every activity, there is a time and a place when it is appropriate; often said aloud as "there is a time and a place for everything". This is not, however, the same as
∃x ∃t ∀ a: A(x,t,a)
which means that there is a time and a place where everything simultaneously is appropriate. (This is something you might also describe as "there is a time and a place, for everything"; this just goes to show that everyday speech is ambiguous and that you have to exercise judgement in how to interpret it.) To use a more poignant example, if L(x,y,t) means "x loves y at time t", then the proposition
∀x ∃y ∃t: L(x,y,t)
could be interpreted as "everybody loves somebody sometime"; whereas
∃y ∀x ∃t: L(x,y,t)
means that there is some single person whom everyone loves at some point in their lives;
∃t ∀x ∃y: L(x,y,t)
means that there is a time at which everyone is in love with someone else; and
∃y ∃t ∀x: L(x,y,t)
means that there is some single person whom, at least one point in time, was loved by everyone at once — all of which mean quite different things.
Unique existence
Finally, using the theory of definite descriptions, we can characterize unique existence using a combination of existential quantification, universal quantification, and equality. For instance, if E(x) = "x is Elvis Presley" and i = myself, I could render I am the one and only Elvis Presley by
E(i) & ∀y: [ (y ≠ i) ⇒ ¬E(y) ]
or "I am Elvis Presley, and anyone who is not me is not Elvis Presley". We can simplify this logically (albeit at the cost of making it slightly perverse phrasing in normal speech) by taking the contrapositive in the second part:
E(i) & ∀y: [ E(y) ⇒ (y = i) ]
or "I am Elvis Presley, and anyone who is Elvis Presley is none other than myself". If I wanted to say that there is one and only one Elvis Presley, without claiming that I am myself Elvis, I could write instead
∃x: [ E(x) & ∀y: [ E(y) ⇒ (x = y) ]]
which we might interpret as "there is someone who is Elvis Presley, and [he is unique, i.e.] anyone who is Elvis Presley is none other than the Elvis Presley". (Using the definitions of the restricted quantifications, we could even write this as ∃x∈E ∀y∈E: (x=y): "there is an Elvis Presley, and all Elvises Presley are the same person".)
If we wanted to say that there are at least two Elvises Presley, we could negate only that part of the proposition above where we claim uniqueness:
∃x: [ E(x) & ¬∀y: [ E(y) ⇒ (x = y) ]]
or equivalently
∃x: [ E(x) & ∃y: [ E(y) & (x ≠ y) ]]
(The restricted quantification version would be written as ∃x∈E ∃y∈E: (x≠y), or "There are two [different] Elvises Presley".)
We can carry out the inner quantifier to the front, which is putting the formula in prenex normal form:
∃x ∃y: E(x) & E(y) & (x ≠ y).
If we wanted to say that there are exactly two Elvises Presley, we could then assert that anyone who is Elvis Presley must be one of the two that we have identified, that is
∃x ∃y: E(x) & E(y) & (x ≠ y) & (∀z: [ E(z) ⇒ (z=x ∨ z=y) ]).
or again, bringing the inner quantifier outward to put the formula into prenex normal form, we may write
∃x ∃y ∀z: E(x) & E(y) & (x ≠ y) & [ E(z) ⇒ (z=x ∨ z=y) ].
