First-Order Logic: Quantifiers, Predicates, and Logical Equivalences

Introduction to Logical Quantifiers

• Universal Quantifier ($\forall$): Represented by an upside-down 'A', this symbol stands for "for all" or "for every". It indicates that a property or predicate holds true for every element within a specified universal set.

• Existential Quantifier ($\exists$): Represented by a backward 'E', this symbol stands for "there exists". It indicates that there is at least one element in the universal set for which the property or predicate is true.

Predicates and Universal Sets

• Definition of a Predicate: A predicate (e.g., $P(X)$) is similar to a proposition but contains a variable. Because of the variable, a predicate does not have a fixed truth value until a specific value from the universal set is substituted for the variable.

• Universal Set ($U$): The set of all objects under consideration. In the examples provided, the universal set consists of all people in the world.

• Practical Example 1:

  • $P(X)$: $X$ was born in New Zealand.

  • $Q(X)$: $X$ grew up in New Zealand.

  • Logical Statement: $\exists X(P(X) \land Q(X))$

  • Interpretation: There exists a person who was born in New Zealand AND grew up in New Zealand.

  • Proof: This statement is proved "true by example." Finding just one individual who meets both criteria (e.g., a student in the lecture hall) suffices for the proof.

  • Caveat: Definitions must be precise, such as determining the exact number of years and specific age ranges required to satisfy the "grew up in New Zealand" condition.

Negation of Quantified Statements

The placement of the negation symbol ($\neg$) significantly alters the meaning and truth value of logical statements.

• Negating Existential Statements:

  • $\exists X(\neg P(X))$: "There is a person such that they were not born in New Zealand." This is true, illustrated by the example of Nick the lecturer.

  • $\neg \exists X(P(X))$: "There does not exist a person who was born in New Zealand." This can be simplified to "Nobody was born in New Zealand," which is false. A counterexample is Jacinda Ardern.

• Negating Universal Statements:

  • $\forall X(\neg P(X))$: "For every person $X$, $X$ was not born in New Zealand." This is the logical equivalent of saying "Nobody was born in New Zealand."

  • $\neg \forall X(P(X))$: "Not everyone was born in New Zealand." This is equivalent to saying there is at least one person who was not born in New Zealand ($\exists X(\neg P(X))$).

Quantifier Equivalence and Shifting Rules

Moving a negation across a quantifier causes the quantifier to change type:

• Rule 1: $\neg \exists X(P(X)) \equiv \forall X(\neg P(X))$

• Rule 2: $\neg \forall X(P(X)) \equiv \exists X(\neg P(X))$

Logical Laws for Complex Propositions

To analyze complex arguments and translate them between logic and English, several logical laws are utilized:

1. Conditional Law: $(A \rightarrow B) \equiv (\neg A \lor B)$

2. De Morgan's Laws:

   • $\neg(A \land B) \equiv (\neg A \lor \neg B)$

   • $\neg(A \lor B) \equiv (\neg A \land \neg B)$

3. Double Negation Law: $\neg (\neg A) \equiv A$

Application: "Not everyone who grew up in New Zealand was born in New Zealand."

• Logical Translation: $\neg (\forall X(Q(X) \rightarrow P(X)))$

• Step-by-step simplification:

  • Shift the negation: $\exists X(\neg(Q(X) \rightarrow P(X)))$

  • Apply Conditional Law: $\exists X(\neg(\neg Q(X) \lor P(X)))$

  • Apply De Morgan's Law: $\exists X(\neg(\neg Q(X)) \land \neg P(X))$

  • Apply Double Negation: $\exists X(Q(X) \land \neg P(X))$

• Simplified English sentence: "There is someone who grew up in New Zealand but was not born in New Zealand."

Number Theory Examples in Logic

Using natural numbers ($U = \{1, 2, 3, \dots\}$) as the universal set, where $P(X)$ is "$X$ is even" and $Q(X)$ is "$X$ is a prime number":

• Statement Analysis: $\neg \exists X(\neg P(X) \land Q(X))$

  • Literal: "There does not exist a natural number which is not even and is prime."

  • Simplified: "There are no odd primes."

  • Status: False. Counterexample: $3$.

• Logical Equivalence Proof:

  • $\neg \exists X(\neg P(X) \land Q(X)) \equiv \forall X \neg(\neg P(X) \land Q(X))$

  • Using De Morgan's: $\forall X(\neg(\neg P(X)) \lor \neg Q(X)) \equiv \forall X(P(X) \lor \neg Q(X))$

  • Sentence: "All natural numbers are either even or not prime."

• Translation of "All odd numbers are prime":

  • Represented as an if-then rule: $\forall X(\neg P(X) \rightarrow Q(X))$

  • Using the conditional law, this is equivalent to: $\forall X(P(X) \lor Q(X))$ ("All numbers are either even or prime.")

Multi-Variable Predicates (Nested Quantifiers)

Predicates can involve more than one variable, such as $P(X, Y)$ meaning "$X$ is taller than $Y$". The order of variables and quantifiers is critical.

• $\exists X \exists Y(P(X, Y))$: "There is a person who is taller than someone else."

• $\exists X \forall Y(P(X, Y))$: "There is a person who is taller than every person in the world."

  • Truth Value: This is false.

  • Reasoning: Unless specified otherwise, $X$ can equal $Y$. A person cannot be taller than themselves ($P(X, X)$ is false). Even the tallest person in the world is a member of the universal set, so the condition fails when $Y$ is that same tallest person.

  • Correction: To make the statement true, it would need to be written as: $\exists X \forall Y(X \neq Y \rightarrow P(X, Y))$

Questions & Discussion

• Question (Student): How can we prove that there exist people born and raised in New Zealand?

• Answer: By asking for a volunteer to reveal their history. If one person in the room raised their hand having been born and grown up there, the existential statement is proved true by example.

• Question (Interjection): Does the word "and" translate differently in logic?

• Answer: In logic, "and" is a conjunction ($\land$), but in English, words like "but" can also function as logical conjunctions depending on the context of the sentence (e.g., "…grew up in New Zealand BUT wasn't born there").

• Question (Student): Why are we using these logic laws?

• Answer: To analyze whether arguments are valid or equivalent. Translating real-world problems into logical structures allows for rigorous analysis that might not be intuitive in plain language as expressions become more complex.