Section 3: Quantifiers
- Page ID
- 1052
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)We are now ready to introduce quantifiers. Consider these sentences:
- Everyone is happy.
- Everyone is at least as tough as Donald.
- Someone is angry.
It might be tempting to translate sentence 6 as \(Hd\) & \(Hg\) & \(Hm\). Yet this would only say that Donald, Gregor, and Marybeth are happy. We want to say that everyone is happy, even if we have not defined a constant to name them. In order to do this, we introduce the ‘∀’ symbol. This is called the universal quantifier.
A quantifier must always be followed by a variable and a formula that includes that variable. We can translate sentence 6 as ∀\(xHx\). Paraphrased in English, this means ‘For all \(x\), \(x\) is happy.’ We call ∀\(x\) an \(x\)-quantifier. The formula that follows the quantifier is called the scope of the quantifier. We will give a formal definition of scope later, but intuitively it is the part of the sentence that the quantifier quantifies over. In ∀\(xHx\), the scope of the universal quantifier is \(Hx\).
Sentence 7 can be paraphrased as, ‘For all \(x\), \(x\) is at least as tough as Donald.’ This translates as ∀\(xT\)2\(xd\).
In these quantified sentences, the variable \(x\) is serving as a kind of placeholder. The expression∀\(x\) means that you can pick anyone and put them in as \(x\). There is no special reason to use \(x\) rather than some other variable. The sentence ∀\(xHx\) means exactly the same thing as ∀\(yHy\), ∀\(zHz\), and ∀\(x\)5\(Hx\)5.
To translate sentence 8, we introduce another new symbol: the existential quantifier, ∃. Like the universal quantifier, the existential quantifier requires a variable. Sentence 8 can be translated as ∃\(xAx\). This means that there is some \(x\) which is angry. More precisely, it means that there is at least one angry person. Once again, the variable is a kind of placeholder; we could just as easily have translated sentence 8 as ∃\(zAz\).
Consider these further sentences:
- No one is angry.
- There is someone who is not happy.
- Not everyone is happy.
Sentence 9 can be paraphrased as, ‘It is not the case that someone is angry.’ This can be translated using negation and an existential quantifier: ¬∃\(xAx\). Yet sentence 9 could also be paraphrased as, ‘Everyone is not angry.’ With this in mind, it can be translated using negation and a universal quantifier: ∀\(x\)¬\(Ax\).
Both of these are acceptable translations, because they are logically equivalent. The critical thing is whether the negation comes before or after the quantifier.
In general,∀\(xA\) is logically equivalent to ¬∃\(x\)¬\(A\). This means that any sentence which can be symbolized with a universal quantifier can be symbolized with an existential quantifier, and vice versa. One translation might seem more natural than the other, but there is no logical difference in translating with one quantifier rather than the other. For some sentences, it will simply be a matter of taste.
Sentence 10 is most naturally paraphrased as, ‘There is some \(x\) such that \(x\) is not happy.’ This becomes ∃\(x\)¬\(Hx\). Equivalently, we could write ¬∀\(xHx\).
Sentence 11 is most naturally translated as ¬∀\(xHx\). This is logically equivalent to sentence 10 and so could also be translated as ∃\(x\)¬\(Hx\).
Although we have two quantifiers in QL, we could have an equivalent formal language with only one quantifier. We could proceed with only the universal quantifier, for instance, and treat the existential quantifier as a notational convention. We use square brackets [ ] to make some sentences more readable, but we know that these are really just parentheses ( ). In the same way, we could write ‘∃\(x\)’ knowing that this is just shorthand for ‘¬∀\(x\)¬.’ There is a choice between making logic formally simple and making it expressively simple. With QL, we opt for expressive simplicity. Both ∀ and ∃ will be symbols of QL.
Universe of Discourse
Given the symbolization key we have been using, ∀\(xHx\) means ‘Everyone is happy.’ Who is included in this everyone? When we use sentences like this in English, we usually do not mean everyone now alive on the Earth. We certainly do not mean everyone who was ever alive or who will ever live. We mean something more modest: everyone in the building, everyone in the class, or everyone in the room.
In order to eliminate this ambiguity, we will need to specify a universe of discourse— abbreviated UD. The UD is the set of things that we are talking about. So if we want to talk about people in Chicago, we define the UD to be people in Chicago. We write this at the beginning of the symbolization key, like this:
UD: people in Chicago
The quantifiers range over the universe of discourse. Given this UD, ∀\(x\) means ‘Everyone in Chicago’ and ∃\(x\) means ‘Someone in Chicago.’ Each constant names some member of the UD, so we can only use this UD with the symbolization key above if Donald, Gregor, and Marybeth are all in Chicago. If we want to talk about people in places besides Chicago, then we need to include those people in the UD.
In QL, the UD must be non-empty; that is, it must include at least one thing. It is possible to construct formal languages that allow for empty UDs, but this introduces complications.
Even allowing for a UD with just one member can produce some strange results. Suppose we have this as a symbolization key:
UD: the Eiffel Tower
Px: \(x\) is in Paris.
The sentence∀\(xPx\) might be paraphrased in English as ‘Everything is in Paris.’ Yet that would be misleading. It means that everything in the UD is in Paris. This UD contains only the Eiffel Tower, so with this symbolization key ∀\(xPx\) just means that the Eiffel Tower is in Paris.
Non-referring terms
In QL, each constant must pick out exactly one member of the UD. A constant cannot refer to more than one thing— it is a singular term. Each constant must still pick out something. This is connected to a classic philosophical problem: the so-called problem of non-referring terms.
Medieval philosophers typically used sentences about the chimera to exemplify this problem. Chimera is a mythological creature; it does not really exist. Consider these two sentences:
12. Chimera is angry.
13. Chimera is not angry.
It is tempting just to define a constant to mean ‘chimera.’ The symbolization key would look like this:
UD: creatures on Earth
Ax: \(x\) is angry.
c: chimera
We could then translate sentence 12 as \(Ac\) and sentence 13 as ¬\(Ac\).
Problems will arise when we ask whether these sentences are true or false.
One option is to say that sentence 12 is not true, because there is no chimera. If sentence 12 is false because it talks about a non-existent thing, then sentence 13 is false for the same reason. Yet this would mean that \(Ac\) and ¬\(Ac\) would both be false. Given the truth conditions for negation, this cannot be the case.
Since we cannot say that they are both false, what should we do? Another option is to say that sentence 12 is meaningless because it talks about a nonexistent thing. So Ac would be a meaningful expression in QL for some interpretations but not for others. Yet this would make our formal language hostage to particular interpretations. Since we are interested in logical form, we want to consider the logical force of a sentence like \(Ac\) apart from any particular interpretation. If \(Ac\) were sometimes meaningful and sometimes meaningless, we could not do that.
This is the problem of non-referring terms, and we will return to it later (see p. 71.) The important point for now is that each constant of QL must refer to something in the UD, although the UD can be any set of things that we like. If we want to symbolize arguments about mythological creatures, then we must define a UD that includes them. This option is important if we want to consider the logic of stories. We can translate a sentence like ‘Sherlock Holmes lived at 221B Baker Street’ by including fictional characters like Sherlock Holmes in our UD.