Part 9: Predicate Logic

Why Predicate Logic Matters

Propositional logic treats entire statements as indivisible units (propositions). But often we want to talk about properties of objects or relationships between objects. For example, "All cats are mammals" or "Some numbers are prime." Propositional logic can't easily express "all" or "some" — it would just see "All cats are mammals" as a single black box statement. Predicate logic (also known as first-order logic) allows us to peek inside that box. It lets us use variables and quantifiers to say things about many instances at once, greatly expanding the expressiveness of our logic.

In simpler terms, predicate logic answers questions like: - How do we say every member of a category has some property?
- How do we say there exists something with a certain property?

These abilities are crucial in mathematics, computer science (database queries, AI), and philosophy.

From Aristotle to Modern Logic

Aristotle's syllogisms (e.g., "All men are mortal; Socrates is a man; therefore Socrates is mortal") were an early form of predicate logic dealing with categories and membership. Modern predicate logic (developed by Frege in 1879 and others) formalized these ideas with quantifiers and variables, laying the groundwork for much of modern mathematics and computer science.

From Propositions to Predicates

A predicate is like a property or relation that can be true or false of something. It’s often represented as a capital letter with parentheses, e.g. $P(x)$ might mean "x is prime" or "x is a philosopher", depending on context. The variable $x$ can stand for an object in the domain of discourse (the set of things we're talking about).

Example: Let $M(x)$ mean "x is mortal" and $H(x)$ mean "x is human." The statement "All humans are mortal" can be expressed in predicate logic, whereas propositional logic could not directly capture it.

Quantifiers: Universal and Existential

Predicate logic introduces quantifiers to indicate how many or which elements of the domain we’re talking about:

Universal Quantifier ($\forall$): Means "for all" or "for every".
$\forall x\, P(x)$ says "for all $x$, $P(x)$ is true." (Every $x$ has property $P$.)
Existential Quantifier ($\exists$): Means "there exists" or "for at least one".
$\exists x\, P(x)$ says "there exists at least one $x$ such that $P(x)$ is true." (Some $x$ has property $P$.)

Let's see them in use:

"All" statements (Universal)

All cats are mammals.
Domain: animals.
Let $C(x)$ = "x is a cat", $M(x)$ = "x is a mammal."
In logic: $\forall x\, (C(x) \to M(x))$.
This says: for every creature $x$, if $x$ is a cat, then $x$ is a mammal.
No dogs can fly.
Let $D(x)$ = "x is a dog", $F(x)$ = "x can fly."
"No dogs can fly" can be written as: $\forall x\, (D(x) \to \neg F(x))$.
(For every $x$, if $x$ is a dog, then $x$ cannot fly.)

Alternatively, one could write $\neg \exists x (D(x) \land F(x))$ meaning "there does not exist an $x$ that is a dog and can fly," which is logically equivalent.

"Some" statements (Existential)

There exists a prime number greater than 100.
Domain: numbers.
Let $P(x)$ = "x is prime", $G(x)$ = "x > 100$.
In logic: $\exists x\, (P(x) \land G(x))$.
(There is at least one number $x$ such that $x$ is prime and $x > 100$.)
Someone in the class speaks French.
Domain: people (in the class).
Let $F(x)$ = "x speaks French."
$\exists x\, F(x)$ says "There is at least one person $x$ such that $x$ speaks French."

Combining Quantifiers and Logic

We can make more complex statements:

"Every even number greater than 2 is not prime."
Domain: natural numbers.
$E(x)$ = "x is even", $P(x)$ = "x is prime", $G(x)$ = "x > 2$.
Logic: $\forall x\, ((E(x) \land G(x)) \to \neg P(x))$.
(For any number, if it's even and >2, then it is not prime.)
"There is a student who is in both the chess club and the debate club."
Domain: students.
$C(x)$ = "x is in the chess club", $D(x)$ = "x is in the debate club".
$\exists x\, (C(x) \land D(x))$.
(At least one student is in both clubs.)

Translating 'none' or 'no one'

Statements like "No $x$ satisfy condition Y" can be translated in two equivalent ways:
- Universal form: $\forall x\, (\text{if Y}(x) \text{ then false})$ – e.g., $\forall x (Y(x) \to \text{false})$, which simplifies to $\forall x\, \neg Y(x)$ (if we mean no x at all have property Y). But more typically, "No $X$ are $Y$" is translated as $\forall x (X(x) \to \neg Y(x))$.
- Negated existential form: $\neg \exists x\, Y(x)$ – "There does not exist an $x$ with property Y."
These are equivalent: saying no $x$ has property Y is the same as saying "for all $x$, $x$ does not have property Y."

Domains and Scope of Quantifiers

When we write $\forall x$ or $\exists x$, we presume a domain of discourse for $x$ (the set of all things $x$ could refer to). Sometimes it's stated explicitly ("for all people x, ..."), other times it's implied by context (if we're talking about numbers, $x$ ranges over numbers).

Quantifiers have a scope similar to how parentheses or logical operators have scope. For example, in $\forall x\, (P(x) \lor Q(y))$, the $\forall x$ applies only to the $P(x)$ part (and not to $Q(y)$ which might involve a different variable).

If we need multiple quantifiers, we can use different variables or nest them:

"Every student admires some professor."
Domain: people at a university.
Let $S(x)$ = "x is a student", $Prof(y)$ = "y is a professor", $A(x,y)$ = "x admires y".
Logic: $\forall x\, [S(x) \to \exists y\, (Prof(y) \land A(x,y))]$.
(For each person x, if x is a student, then there exists at least one person y who is a professor and x admires y.)
Order matters for different quantifiers:
$\forall x \exists y\, A(x,y)$ is not the same as $\exists y \forall x\, A(x,y)$. The first says "for each $x$, you can find a (potentially different) $y$ such that $A(x,y)$." The second says "there is a single $y$ that works for every $x$." This distinction is huge.

Order of Quantifiers

Pay attention to quantifier order:
- $\forall x \exists y\, P(x,y)$: For each $x$, maybe different $y$s can witness the truth.
- $\exists y \forall x\, P(x,y)$: There is one particular $y$ that works for all $x$.
These can mean very different things. For example, "For every person, there is someone whom they love" versus "There is a person whom everyone loves."

Translating Between English and Predicate Logic

It takes practice to capture English precisely in symbols:

Each, every, all $\rightarrow \forall$
Some, there is/are, at least one $\rightarrow \exists$
None, no $\rightarrow$ use $\forall$ with a negation, or $\neg \exists$

Example translations:

"Every car has wheels."
Domain: vehicles (or things).
$C(x)$ = "x is a car", $W(x)$ = "x has wheels".
$\forall x\, (C(x) \to W(x))$.
"Some cars have no wheels."
$C(x)$ = "x is a car", $W(x)$ = "x has wheels".
$\exists x\, (C(x) \land \neg W(x))$.
(There exists an object that is a car and does not have wheels — perhaps this is false in reality, but that's the logical form.)
"Not every car has wheels."
This is the negation of "every car has wheels."
We can write: $\neg \forall x (C(x) \to W(x))$, which is equivalent to $\exists x \neg (C(x) \to W(x))$ which simplifies to $\exists x (C(x) \land \neg W(x))$.
So "Not all have wheels" means "Some car has no wheels" — note how English "not every" turns into an existential statement logically.
"At least two people have the same birthday." (A bit trickier)
Domain: people.
$B(x,d)$ = "Person $x$ has birthday on date $d$".
One way: $\exists x \exists y \exists d\, [(x \neq y) \land B(x,d) \land B(y,d)]$.
(There exist two different people $x$ and $y$ and a date $d$ such that $x$ and $y$ both have birthday $d$.)

Real-World Applications of Predicate Logic

Database Queries: SQL and other query languages are built on predicate logic. A query like "SELECT * FROM Employees WHERE age > 30 AND department = 'Sales'" is basically finding all $x$ such that $Age(x) > 30$ and $Dept(x, "Sales")$.
Artificial Intelligence: Knowledge representation often uses first-order logic to encode facts and rules. E.g., in an expert system: $\forall x (Cat(x) \to Mammal(x))$ encodes a general fact about the world.
Mathematics: Almost all definitions and theorems in mathematics are expressed in predicate logic ("For every $\varepsilon > 0$, there exists a $\delta > 0$ such that ...", which is a $\forall \exists$ statement).
Formal Verification: When verifying hardware or software, one often writes specifications like "for all possible inputs satisfying condition P, the output will satisfy Q" ($\forall x (P(x) \to Q(x))$) and uses automated theorem provers to check it.

Common Misconceptions

"$\forall x\, P(x)$ means the same as $P(x)$ for a generic x."
Reality: $\forall x\, P(x)$ means every possible x in the domain makes $P(x)$ true. You can't assume a specific one without stating it. It's a statement about the entire domain at once.
"$\exists x\, P(x)$ asserts the existence but we know nothing else about that x."
Reality: Yes, existential just guarantees at least one exists, but we usually can't give it a name unless we use a witness. It's a logical guarantee without identification (unless the context or proof finds a concrete example).
"If $\forall x\, P(x)$ is true, then $\exists x\, P(x)$ must be true."
Reality: True. If everything has property P, certainly at least one thing does. (In logic, $\forall x P(x)$ implies $\exists x P(x)$ provided the domain is nonempty. Usually we assume domains are nonempty.)
"If $\exists x\, P(x)$ is true, then $\forall x\, P(x)$ might be true."
Reality: Having one example doesn't mean all have it. E.g., "There exists a number that is even" is true, but "For all numbers, they are even" is false.
Mixing up $\forall$ and $\exists$: It's common but critical to keep them straight. "Every" vs "Some" are not interchangeable.

Exercises

9.1. Translate into predicate logic: "All birds can fly." (Define appropriate predicates for being a bird and being able to fly.)

9.2. Translate: "Some birds cannot fly." (You might know real examples, but just do it logically.)

9.3. Translate: "Every student in this class has taken at least one programming course." (Define predicates like $S(x)$ for "x is a student in this class", and $P(x,y)$ for "x has taken course y", and maybe a set or predicate for programming courses.)

9.4. Translate: "There is a prime number that is even." (Remember what the only even prime is!)

9.5. Consider the statement: "If a number is rational, then it can be written as a ratio of two integers." Express this as a logical statement with a universal quantifier. (Let $R(x)$ = "x is rational", and define a predicate for "x can be written as m/n with m,n integers".)

9.6. Express the negation of the statement in 9.5 in a normalized way (so that negation symbol directly precedes the predicate, not the quantifier). Explain the meaning of the negation in words.

9.7. Translate: "Not every book is interesting." Then contrast it with "No book is interesting." (They are different! Provide both translations.)

9.8. Translate: "Everyone has exactly one mother." (Hint: This one is a bit advanced. It means: for every person $x$, there exists a person $y$ such that $y$ is the mother of $x$, and for all $z$, if $z$ is a mother of $x$ then $z = y$.)

9.9. Is the following statement true or false (in ordinary arithmetic)? "For every integer $y$, there exists an integer $x$ such that $x < y$." Translate it to logic as well, then answer.

9.10. Explain in your own words the difference between $\forall x \exists y\, P(x,y)$ and $\exists y \forall x\, P(x,y)$. Give a real-life example where one is true but the other is false.

Advanced: Predicate logic is a powerful tool, but with great power comes additional complexity. In further studies, you'll encounter concepts like relations, functions, multiple quantifiers, and even logical paradoxes that arise with unrestricted domains (like Russell's paradox about "the set of all sets that don't contain themselves"). Predicate logic is the gateway to these deeper explorations, including the foundations of mathematics and computer science.