Logic: “all” and “some”

This is the third post (excluding two “books added” posts) in the category “logic”, so if you need to, go back to the earlier posts.

In this post, I want to do two things.

First, I want to show you the duality between “for all” and “there exists”.

Second, I want to show you how to translate “all dogs are clever” and “some dogs are clever”. There is at least one subtle point.

Let me jump right in.

Duality


“Everything is clever” would be written \forall x\  Cx\ .

“Something is clever” would be written \exists x\  Cx\ .

The two symbols \forall\ and \exists\ are called “quantifiers”; to be specific, \forall\ is called the universal quantifier, and \exists\ is called the existential quantifier.

There is a fundamental duality between those statements. If everything is clever, then it is false that “something is not clever” and conversely. That is, we have the equivalence:

\forall x\  Cx \equiv \neg  (\exists x \neg  Cx)\ .

which I will usually write, dropping the parentheses, as

\forall x\  Cx \equiv \neg  \exists x\  \neg  Cx\ .

In a formal system, having defined one of these quantifiers, we could use some form of that duality to define the other quantifier. Oh, let’s get the other forms.

Negate that equivalence, getting

\neg \forall x\  Cx \equiv \exists x\  \neg Cx\ .

That’s plausible. It says that if something is not clever, then it is false that everything is clever. Now we have two different forms of the same fundamental duality.

We can get two more, just by replacing “clever” by “not clever” and conversely. We end up with 4 forms of the duality:

\forall x\  Cx \equiv \neg \exists x\  \neg Cx\

\neg \forall x\  Cx \equiv \exists x\  \neg Cx\

\forall x\  \neg Cx \equiv \neg \exists x\  Cx\

\neg \forall x\  \neg Cx \equiv \exists x\  Cx\

In words, we have:

Everything is clever = nothing is not clever;

Not everything is clever = something is not clever;

Everything is not clever = nothing is clever;

Not everything is not clever = something is clever.

Please note the distinctions between “not everything is clever” and “nothing is clever”.

I would also like to point out that we can eliminate a negation which precedes a quantifier. For example, we can replace

\neg \forall x\  Cx\

by its equivalent

\exists x\  \neg Cx\ .

Now, I have simplified things — no pun intended — by talking about “everything” and “something”.

What if we want to narrow the universe of discourse? That is, what if we want to say “all dogs are clever” instead of “everything is clever”? What if we want to say “some dogs are clever” instead of “something is clever”?

“all” & “some”

Consider statements such as:

all dogs are clever;
no dogs are clever;
some dogs are clever;
some dogs are not clever.

How would we write these using \forall\ (“for all”) and \exists\ (“there exists”)? The first is deceptively easy: we say that if x is a dog, then x is clever, and that’s how we write it.

all dogs are clever is symbolized as \forall x\  Dx \Rightarrow Cx\ .

For the second, no dogs are clever, we say that if x is a dog then x is not clever:

no dogs are clever is symbolized as \forall x\  Dx \Rightarrow \neg Cx\ .

We should note that this implication can be satisfied vacuously. For example, we could say that all unicorns are white…

\forall x\  Ux \Rightarrow Wx\ ,

and that’s a true statement, but we have not asserted that unicorns exist. All of them are white, all zero of them.

How would we say some dogs are clever?

Let us consider a form analagous to “all D are C” and write an implication… better, let me use white unicorns. How would we say some unicorns are white? Consider this expression — which will not do what we want:

\exists x\  Ux \Rightarrow Wx\ .

We should be bothered a little by combining existence with a possibly vacuous implication, but let’s look more closely at it. We know from the effective definition of material implication — we never have the conclusion false and the antecedant true — that we can rewrite the implication… and then apply DeMorgan’s Law to eliminate the parentheses. That is, we write

\exists x\  Ux \Rightarrow Wx \equiv \exists x \neg (\neg Wx \land Ux) \equiv \exists x\  Wx \lor \neg Ux\ .

The leftmost form says “there exists something such that if it’s a unicorn then it’s white”. The rightmost form says “there exists something which is either not a unicorn or is white”. And the middle form says the two outside forms are equivalent.

The part about “or is white” is not an issue; but “not a unicorn”? Here’s what we’ve got: if there exists something which is not a unicorn, say a dog y, then we have \neg Uy\ , hence \neg Uy \lor Wy\ (by “addition”), hence Uy \Rightarrow Wy\ , hence \exists x\  Ux \Rightarrow Wx\ ; in English, there is a dog such that if that dog were a unicorn, then it would be white.

That’s a far cry from “some unicorn is white”.

In other words, the expression \exists x\  Ux \Rightarrow Wx\ would be true if there exists any object x which is not a unicorn. But I don’t want that expression to be true under those circumstances.

(This is the subtlety I spoke of. We simply cannot use material implication to translate the word “some”.)

We have to try something else. How about a simple “and”? Consider

\exists x\  (Ux \land Wx)\ ,

which says there exists something which is both white and a unicorn.

OK, I believe that statement to be false, but I think it does correctly represent “some… are”. It certainly works for clever dogs:

\exists x\  (Dx \land Cx)\ .

That says “there is a dog (at least one dog) and it is clever”. It might be the only dog in all of creation, or it might not be, but it is one clever dog.

Two more things on this sub-topic. One, having decided to use “and” for “some”, could we have used “and” to represent “all”?

Consider

\forall x\  (Dx \land Cx)\ .

Oops, that’s easy to debunk; it says everything is a dog. Yes, it does say that all dogs are clever, but we’ve gone overboard and said far more than just that. We decide to stay with the translation of “all dogs are clever” as \forall x\  (Dx \Rightarrow Cx)\ .

Two, having decided to stay with implication for “all”, we should rewrite it and make sure it isn’t strange, too. That is, rewrite it the same way we rewrote the implication about some unicorns being white. We take all the dogs…

\forall x\  (Dx \Rightarrow Cx) \equiv \forall x\  \neg (\neg Cx \land  Dx) \equiv \forall x\ Cx \lor   \neg Dx\ ,

and the rightmost form says that every x is clever or it’s not a dog, or both. That is, either every thing is clever (in particular, all dogs are clever), or it is not a dog (in which case we don’t care whether it’s clever), or it is both a dog and clever (which is fine).

Conclusion:

All dogs are clever translates to \forall x\  (Dx \Rightarrow Cx)\ .

Some dogs are clever translates to \exists x\ (Dx \land Cx)\ .

No dogs are clever, i.e. all dogs are not clever, translates to \forall x\  (Dx \Rightarrow \neg Cx)\ .

Some dogs are not clever translates to \exists x\  (Dx \land \neg Cx)\ .

Just for the record, I have seen a logic book — “Math Proofs Demystified”, not in my bibliography! — that got this wrong. You can even go here and see the correction posted on the author’s web site. You may have to look closely to tell that he had originally used implication to represent “some boys walk to school”, etc.. This is, incidentally, the logic book that listed only one distributive law.

And I have now found an electrical engineering book that never states the distributivity of “or” over “and”. It uses it, in effect, but never writes it out. I’m not really surprised; once you write logical expressions using arithmetic symbols (“+” for “or” and “juxtaposition” — multiplication — for “and”), the unremarkable

x \lor (y \land z) \equiv (x \lor y) \land (x \lor z)\

becomes the intuition-challenging

x + yz = (x + y) (x+z).

Advertisements
Posted in logic. 1 Comment »

One Response to “Logic: “all” and “some””

  1. Logic: “for all” vs “there exists” | teeradaj.com Says:

    […] 1. https://rip94550.wordpress.com/2010/04/19/logic-all-and-some/ […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: