12. “All” and “some”

[latexpage]

12.1  The challenge of translating “all” and “some”

We are still not able to translate fully Aristotle’s argument.  It began:

All men are mortal.

What does this “all” mean?

Let’s start with a simpler example.  Suppose for a moment we consider the sentence

All is mortal.

Or, equivalently,

Everything is mortal.

How should we understand this “all” or “everything”?  This is a puzzle that stumped many generations of logicians.  The reason is that, at first, it seems obvious how to handle this case.  “All”, one might conclude, is a special name.  It is a name for everything in my domain of discourse.  We could then introduce a special name for this, with the following translation key.

ε:  all (or everything)

Mx:  x is mortal

And, so we translate the sentence

Mε

So far, so good. But now, what about our first sentence?  Let’s add to our translation key

Hx: x is human

Now how shall we translate  “all men are mortal”?  Most philosophers think this should be captured with a conditional (we will see why below), but look at this sentence:

(Hε→Mε)

That does not at all capture what we meant to say.  That sentence says:  if everything is a human, then everything is mortal.  We want to say just that all the humans are mortal.

Using a different connective will not help.

(Hε ^ Mε)

(Hε v Mε)

(Hε ↔ Mε)

All of these fail to say what we want to say.  The first says everything is human and everything is mortal.  The second, that everything is human or everything is mortal. The third that everything is human if and only if everything is mortal.

The problem is even worse for another word that seems quite similar in its use to “all”:  the word “some”.  This sentence is surely true:

Some men are mortal.

Suppose we treat “some” as a name, since it also appears to act like one.  We might have a key like this:

σ :  some

And suppose, for a moment, that this meant, at least one thing in our domain of discourse.  And then translate our example sentence, at least as a first attempt, as

(Hσ ^ Mσ)

This says that some things are human, and some things are mortal.  It might seem at first to work.  But now consider a different sentence.

Some things are human and some things are crabs.

That’s true.  Let us introduce the predicate Kx for x is a crab.  Then, it would seem we should translate this

(Hσ ^ Kσ)

But that does not work.  For σ, if it is a name, must refer to the same thing.  But, then something is both a human and a crab, which is false.

“All” and “some” are actually subtle.  They look and (in some ways) act like names, but they are different than names.  So, we should not treat them as names.

ε:  all (or everything)

σ :  some

This perplexed many philosophers and mathematicians, but finally a very deep thinker whom we have already mentioned—Gottlob Frege—got clear about what is happening here, and developed what we today call the “quantifier”.

The insight needed for the quantifier is that we need to treat “all” and “some” as special operators that can “bind” or “reach into” potentially several of the arity places in one or more predicates.  To see the idea, consider first the simplest case.  We introduce the symbol ∀ for all.  However, we also introduce a variable—in this case we will use x—to be a special kind of place holder.  (Or:  you could think of ∀ as meaning every and x as meaning thing, and then ∀x means everything.)  Now, to say “everything is human”, we would write

∀xHx

Think of this sentence as saying, you can take any object from our domain of discourse, and that thing has property H.  In other words, if ∀xHx is true, then Ha is true, and Hb is true, and Hc is true, and so on, for all the objects of our domain of discourse.

So far, this is not much different than using a single name to mean “everything”.  But there is a very significant difference when we consider a more complex formula.  Consider “All men are mortal”.  Most logicians believe this means that “Everything is such that, if it is human, then it is mortal”.  We can write

∀x(Hx→Mx)

So, if ∀x(Hx→Mx) is true, then (Ha→Ma) and (Hb→Mb) and (Hc→Mc) and so on are true.

This captures exactly what we want.  We did not want to say if everything is human, then everything is mortal.  We wanted to say, for each thing, if it is human, then it is mortal.

A similar approach will work for “some”.  Let “∃” be our symbol for “some”.  Then we can translate

Some men are mortal

With

∃x(Hx^Mx)

(We will discuss in section 13.3 below why we do not use a conditional here; at this point, we just want to focus on the meaning of the “∃”.)  Read this as saying, for this example, there is at least one thing from our domain of discourse that has properties H and M.  In other words, either (Ha ^ Ma) is true or (Hb ^ Mb) is true or (Hc ^ Mc) is true or etc.

These new elements to our language are called “quantifiers”.  The symbol “∀” is called the “universal quantifier”.  The symbol “∃” is called the “existential quantifier” (to remember this, think of it as saying, “there exists at least one thing such that…”).  We say that they “quantify over” the things that our language is about (that is, the things in our domain of discourse).

We are now ready to provide the syntax for terms, predicates, and quantifiers.

12.2  A new syntax

For the propositional logic, our syntax was always trivial.  For the first order logic our syntax will be more complex.  We will need a new concept, the concept of a “well-formed formula”.  And we will need to make more explicit use of the fact that our syntax is a recursive syntax, which means that our rules must be stated with a first case, and then a way to repeatedly apply our syntactic rules.  We are, also, going to change one feature of our metalanguage.  The symbol Φ will no longer mean a sentence.  Instead, it is any well-formed expression of our language.  We can write Φ(a) to mean that the name a appears in Φ; this does not mean that Φ is an arity-one predicate with the single name a.  Φ can be very complex.  For example, Φ could be the expression ((Fa↔Gbc)^Hd).

A symbolic term is either a name, an indefinite name, an arbitrary term, or a variable (we will explain what indefinite terms and arbitrary terms are later).  Names are a, b, c, d….  Indefinite names are p, q, r….  Variables are u, v, w, x, y, z.  Arbitrary terms are u′, v′, w′, x′, y′, z′.

A predicate of arity n followed by n symbolic terms is a well-formed formula.

If Φ and Ψ are well-formed formulas, and α is a variable, then the following are well-formed formulas:

¬Φ

(Φ → Ψ)

(Φ ^ Ψ)

(Φ v Ψ)

(Φ↔Ψ)

∀αΦ

∃αΦ

If the expression Φ(α) contains no quantifiers, and α is a variable, then we say that α is a “free variable” in Φ(α).  If the expression Φ(α) contains no quantifiers, and α is a variable, then we say that α is “bound” in ∀αΦ(α) and α is “bound” in ∃αΦ(α).  A variable that is bound is not free.

If Φ is a well-formed formula with no free variables, then it is a sentence.

If Φ and Ψ are sentences, then the following are sentences:

¬Φ

(Φ→Ψ)

(Φ ^ Ψ)

(Φ v Ψ)

(Φ↔Ψ)

This way of expressing ourselves is precise; but, for some of us, when seeing it for the first time, it is hard to follow.  Let’s take it a step at a time.  Let’s suppose that F is a predicate of arity one, that G is a predicate of arity two, and that H is a predicate of arity three.  Then the following are all well-formed formulas.

Fx

Fy

Fa

Gxy

Gyx

Gab

Gax

Hxyz

Haxc

Hczy

And, if we combine these with connectives, they form well-formed formulas.  All of these are well-formed formulas:

¬Fx

(Fx→Fy)

(Fa^Gxy)

(Gyx v Gab)

(Gax↔Hxyz)

∀xHaxc

∃zHczy

For these formulas, we say that x is a free variable in each of the first five well-formed formulas.  The variable x is bound in the sixth well-formed formula.  The variable z is bound in the last well-formed formula, but y is free in that formula.

For the following formulae, there are no free variables.

∀xFx

∃zGza

Fa

Gbc

Each of these four well-formed formulas is, therefore, a sentence.  If combined using our connectives, these would make additional sentences.  For example, these are all sentences:

¬∀xFx 

(∀xFx→∃zGza)

(Fa ^ Gbc)

(Gbc ↔ ∃zGza)

(Gbc v ∃zGza)

The basic idea is that in addition to sentences, we recognize formulae that have the right shape to be a sentence, if only they had names instead of variables in certain places in the formula.  These then become sentences when combined with a quantifier binding that variable, because now the variable is no longer a meaningless placeholder, and instead stands for any or some object in our language.

What about the semantics for the quantifiers?  This will, unfortunately, have to remain intuitive during our development of first order logic.  We need set theory to develop a semantics for the quantifiers; truth tables will not work.  In chapter 17, you can read a little about how to construct a proper semantics for the quantifiers.  Here, let us simply understand the universal quantifier, “∀”, as meaning every object in our domain of discourse; and understand the existential quantifier, “∃”, as meaning at least one object in our domain of discourse.

A note about the existential quantifier.  “Some” in English does not often mean at least one.  If you ask your friend for some of her french fries, and she gives you exactly one, you will feel cheated.  However, we will likely agree that there is no clear norm for the number of french fries that she must give you, in order to satisfy your request.  In short, the word “some” is vague in English.  This is a useful vagueness—we don’t want to have to say things like, “Give me 11 french fries, please”.  But, our logical language must be precise, and so, it must have no vagueness.  For this reason, we interpret the existential quantifier to mean at least one.

12.3  Common sentence forms for quantifiers

Formulas using quantifiers can have very complex meanings.  However, translating from English to first order logic expressions is usually surprisingly easy, because in English many of our phrases using “all” or “some” or similar phrases are of eight basic forms.  Once we memorize those forms, we can translate these kinds of phrases from English into logic.

Here are examples of the eight forms, using some hypothetical sentences.

Everything is human.

Something is human.

Something is not human.

Nothing is human.

All humans are mortal.

Some humans are mortal.

Some humans are not mortal.

No humans are mortal.

Our goal is to decide how best to translate each of these.  Then, we will generalize.  Let us use our key above, in which “Hx” means x is human, and “Mx” means x is mortal.

The first two sentences are straightforward.  The following are translations.

∀xHx

∃xHx

What about the third sentence?  It is saying there is something, and that thing is not human.  A best translation of that would be to start with the “something”.

∃x¬Hx

That captures what we want.  At least one thing is not human.  Contrast this with the next sentence.  We can understand it as saying, It is not the case that something is human.  That is translated:

¬∃xHx

(It turns out that “∃x¬Hx” and “¬∀xHx” are equivalent and “¬∃xHx” and “∀x¬Hx” are equivalent; so we could also translate “Something is not human” with “¬∀xHx”, and “Nothing is human” with “∀x¬Hx”.  However, this author finds these less close to the English in syntactic form.)

The next four are more subtle.  “All humans are mortal” seems to be saying, if anything is human, then that thing is mortal.  That tells us directly how to translate the expression:

∀x(Hx→Mx)

What about “some humans are mortal”?  This is properly translated with:

∃x(Hx^Mx)

Many students suspect there is some deep similarity between “all humans are mortal” and “some humans are mortal”, and so want to translate “some humans are mortal” as ∃x(Hx→Mx).  This would be a mistake.  Remember the truth table for the conditional; if the antecedent is false, then the conditional is true.  Thus, the formula ∃x(Hx→Mx) would be true if there were no humans, and it would be true if there were no humans and no mortals.

That might seem a bit abstract, so let’s leave off our language about humans and mortality, and consider a different first order logic language, this one about numbers.  Our domain of discourse, let us suppose, is the natural numbers (1, 2, 3, …).  Let “Fx” mean “x is even” and “Gx” mean “x is odd”.  Now consider the following formula:

Some even number is odd.

We can agree that, for the usual interpretation of “odd” and “even”, this sentence is false.  But now suppose we translated it as

∃x(Fx→Gx)

This sentence is true.  That’s because there is at least one object in our domain of discourse for which it is true.  For example, consider the number 3 (or any odd number). Suppose that in our logical language, a means 3.  Then, the following sentence is true:

(Fa→Ga)

This sentence is true because the antecedent is false, and the consequent is true.  That makes the whole conditional true.

Clearly, “∃x(Fx→Gx)” cannot be a good translation of “Some even number is odd”, because whereas “Some even number is odd” is false, “∃x(Fx→Gx)” is true.  The better translation is

∃x(Fx^Gx)

This says, some number is both even and odd.  That’s clearly false, matching the truth value of the English expression.

To return to our language about humans and mortality.  The sentence “some human is mortal” should be translated

∃x(Hx^Mx)

And this makes clear how we can translate, “some human is not mortal”:

∃x(Hx ^ ¬Mx)

The last sentence, “No humans are mortal” is similar to “Nothing is human”.  We can read it as meaning It is not the case that some humans are mortal, which we can translate:

¬∃x(Hx^Mx)

(It turns out that this sentence is equivalent to, “all humans are not mortal”.  Thus, we could also translate the sentence with:

∀x(Hx→¬Mx).)

We need to generalize these eight forms.  Let Φ and Ψ be expressions (these can be complex).  Let α be any variable.  Then, we can give the eight forms schematically in the following way.

Everything is Φ

∀αΦ(α)

Something is Φ

∃αΦ(α)

Something is not Φ

∃α¬Φ(α)

Nothing is Φ

¬∃αΦ(α)

All Φ are Ψ

∀α(Φ(α)→Ψ(α))

Some Φ are Ψ

∃α (Φ(α) ^ Ψ(α))

Some Φ are not Ψ

∃α (Φ(α) ^ ¬Ψ(α))

No Φ are Ψ

¬∃α (Φ(α)^ Ψ(α))

These eight forms include the most common forms of sentences that we encounter in English that use quantifiers.  This may not, at first, seem plausible, but, when we recognize that these generalized forms allow that the expression Φ or Ψ can be complex, then, we see that the following are examples of the eight forms, given in the same order:

Everything is a female human from Texas.

Something is a male human from Texas.

Something is not a female human computer scientist from Texas.

Nothing is a male computer scientist from Texas.

All male humans are mortal mammals.

Some female humans are computer scientists who live in Texas.

Some female humans are not computer scientists who live in Texas.

No male human is a computer scientist who lives in Texas.

The task in translating such sentences is to see, when we refer back to our schemas, that Φ and Ψ can be complex.  Thus, if we add to our key the following predicates:

Fx:  x is female

Gx: x is male

Tx:  x is from Texas

Sx:  x is a computer scientist

Lx:  x is a mammal

Then, we can see that the following are translations of the eight English sentences, and they utilize the eight forms.

∀x((Fx^Hx) ^ Tx)

∃x((Gx^Hx)^Tx)

∃x ¬((Fx^Hx)^(Sx^Tx))

¬∃x((Gx^Sx)^Tx)

∀x((Gx^Hx) → (Mx^Lx))

∃x((Fx^Hx) ^ (Sx^Tx))

∃x((Fx^Hx) ^ ¬(Sx^Tx))

¬∃x((Gx^Hx)^(Sx^Tx))

Another important issue to be aware of when translating expressions with quantifiers is that “only” plays a special role in some English expressions.  Consider the following sentences.

All sharks are fish.

Only sharks are fish.

The first of these is true; the second is false.  We will start a new logical language and key.  Let Fx mean that x is a fish, and Sx mean that x is a shark.  We know how to translate the first sentence.

∀x(Sx → Fx)

However, how shall we translate “Only sharks are fish”?  This sentence tells us that the only things that are fish are the sharks.  But then, all fish are sharks.  That is, the translation is:

∀x(Fx → Sx)

It would also be possible to combine these claims:

All and only sharks are fish.

Which should be translated:

∀x(Sx ↔ Fx)

This indicates two additional schemas for translation that may be useful.  First, sentences of the form “Only Φ are Ψ” should be translated:

∀α(Ψ(α) → Φ(α))

Second, sentences of the form “all and only Φ are Ψ” should be translated in the following way:

∀α(Φ(α) ↔ Ψ(α))

12.4  Problems

1. Which of the following expressions has a free variable?  Identify the free variable if there is one.  Assume F is an arity one predicate, and G is an arity two predicate.

1. Fa
2. Fx
3.  Gxa
4.  ∃xFx
5.  ∀xGxa
6.  ∀xGxy
7.  ∀x(Fx → Gxa)
8.  (∀xFx → Gxa)
9. (∀xFx → ∀xGxa)
10.  ∀x(Fx → Gxy)

2. Provide a key and translate the following expressions into first order logic.  Assume the domain of discourse is Terrestrial organisms.  Thus, ∀xFx would mean all Terrestrial organisms are F, and ∃xFx would mean at least one Terrestrial organisms is F.  Don’t be concerned that some of these sentences are obviously false.

1. All horses are mammals.
2. Some horses are mammals.
3. No horses are mammals.
4. Some horses are not mammals.
5. Some mammals lay eggs, and some mammals do not.
6. Some chestnut horses are mammals that don’t lay eggs.
7. No chestnut horses are mammals that lay eggs.
8. Some egg-laying mammals are not horses.
9. There are no horses.
10. There are some mammals.
11. Only horses are mammals.
12. All and only horses are mammals.

3. Provide your own key and translate the following expressions of first order logic into natural sounding English sentences.  All the predicates here are meant to be arity one.  Do not worry if some of your sentences are obviously false; you rather want to show you can translate from logic to normal sounding English.

1. ∀x((Fx^Gx) →Hx)
2. ∀x(Fx→¬Hx)
3. ∃x((Fx^(Gx^Hx))
4. ∃x((Fx^¬(Gx^Hx))
5. ¬∃x(Fx^Gx)