Propositional logic hits a wall surprisingly quickly.

Consider:

All cats are mammals. Fuzzy is a cat. Therefore Fuzzy is a mammal.

If we replace those sentences with:

we have thrown away exactly the information that makes the reasoning work.

We need to look inside propositions.

Objects and predicates

Instead of treating:

Fuzzy is a cat

as one indivisible statement, write something like:

Fuzzy names an object.

Cat(x) is a predicate: something that can be true or false of an object.

Likewise:

means that Fuzzy has the property of being a mammal.

Now the logical relationship has something to work with.

"All"

Suppose we want:

Every cat is a mammal.

First understand the idea:

For every object we consider, if it is a cat, then it is a mammal.

Then introduce the notation:

The symbol

means for every.

Read ∀x aloud initially as:

"for every x..."

There is no prize for learning to stare silently at the symbol.

"Some"

Now:

Some cat is black.

means:

There exists at least one object which is both a cat and black.

Notation:

The symbol

means there exists.

Notice how differently all and some behave. One ranges over every object; the other needs only one successful example.

Scope changes meaning

Here is where predicate logic becomes genuinely interesting.

Compare:

Everyone loves someone.

and:

Someone is loved by everyone.

They sound similar.

Their structures are not.

Everyone loves someone, perhaps a different person:

There is one particular person loved by everyone:

Simply reversing the quantifiers changes the claim dramatically.

That is worth remembering:

usually does not mean the same thing as

Negation gets interesting too

Negating:

Everyone passed.

does not mean:

Nobody passed.

It means:

At least one person did not pass.

Symbolically:

is equivalent to:

Likewise:

It is not true that someone passed

means:

Nobody passed.

These relationships are the quantifier counterparts of De Morgan-style reasoning.

Why this matters

Predicate logic can represent structures that propositional logic simply cannot see:

• every
• some
• none
• exactly one
• relations between objects
• nested claims about different objects.

It is expressive enough to formalize enormous parts of mathematics.

But even predicate logic has trouble expressing ideas such as:

It must be true.

It could have been otherwise.

Those are not merely claims about objects in the actual situation.

They compare the actual situation with alternatives.

And that gives us our bridge into the centerpiece of the next Logic batch: Modal Logic and Kripke Worlds.

Instead of asking only:

Is P true?

we will ask:

In which possible worlds is P true, and which of those worlds are accessible from where we currently are?