04 Quantifiers

Logical Quantifiers

Logical quantifiers express statements about how many elements in a given set satisfy a certain condition or predicate. They play a key role in formalizing reasoning in mathematics and logic.

These quantifiers operate within a specific universe or domain of discourse—the set from which variables are drawn. Changing this universe can affect the truth of a formula, as certain predicates may be valid in one universe but not in another.

If all variables in a formula are covered by quantifiers (e.g., $\forall x$, $\exists y$), then the formula is considered a statement because it has a definite truth value. However, if there are free variables (those without a quantifier) that require specific values to be substituted (such as in the definition of a prime number), the formula is not a statement but rather a condition that depends on the values of those free variables.

Two Main Types of Quantifiers

Universal Quantifier ($\forall$):

• Symbol: $\forall$
• Meaning: “For all,” “For every”
• Asserts that a statement holds true for every element in the given universe.
• Example: "$\forall x\in \mathbb{R},x^2\ge 0$" (For all real numbers $x$, $x^2$ is greater than or equal to zero).

Existential Quantifier ($\exists$):

• Symbol: $\exists$
• Meaning: “There exists,” “At least one”
• Asserts that at least one element in the universe satisfies a given condition.
• Example: "$\exists x\in \mathbb{Z},x>10$" (There exists an integer $x$ greater than 10).

The Role of the Universe

The truth of quantifier statements hinges on the chosen universe. Remember our example with natural numbers ($\mathbb{N}$) and integers ($\mathbb{Z}$)?

• Universe $\mathbb{N}$: “There exists an $x$ such that $x+2=1$” is false because no natural number satisfies this condition.
• Universe $\mathbb{Z}$: The same statement becomes true in the set of integers, as $x=-1$ solves the equation.

Always clearly define your universe when working with quantifiers!

Changing the Universe: An Example

• Universe $U=\mathbb{N}$ (Natural Numbers):
  • Consider the statement: “There exists an $x$ such that $x+2=1$.”
  • In the natural numbers, this is false because no natural number satisfies $x+2=1$.
• Universe $U=\mathbb{Z}$ (Integers):
  • The same statement, “There exists an $x$ such that $x+2=1,"becomes\ast \ast true\ast \ast inthesetofintegersbecause$x = -1$ solves the equation.

Thus, the universe of discourse directly influences the truth of formulas involving quantifiers. It is essential to clearly specify the universe when reasoning with quantified logical statements.

Negation of Logical Quantifiers

The negation process for quantifier statements involves carefully applying rules:

• $\neg \forall xP(x)\equiv \exists x\neg P(x)$
• $\neg \exists xP(x)\equiv \forall x\neg P(x)$

Consider the following two statements:

• Let $S$ be the statement: “There exists a smallest number.”
• Let $T$ be the statement: “There does not exist, for each number, an even smaller one.”

Intuitively, these statements seem equivalent. We will prove this by converting them into logical predicates and applying negation step by step. Let the universe $U=\mathbb{N}$ (the set of natural numbers).

Statement $S$: “There exists a smallest number.”

In predicate logic, this can be written as:

$$S:\exists x,\forall y,x\le y$$

This means there exists a number $x$ such that $x$ is less than or equal to every number $y$. In other words, $x$ is the smallest number.

Statement $T$: “There does not exist, for each number, an even smaller one.”

First, translate the positive version of this statement:

• “For each number, there exists an even smaller number.”

In predicate logic, this is written as:

$$\forall x,\exists y,y<x$$

The negation of this is:

$$T:\neg \left(\forall x,\exists y,y<x\right)$$

This means it is not true that every number has a smaller one.

Step-by-Step Negation Process

Let’s now show how the negation transforms $T$ into $S$:

1. Start with $T$:

   $$T:\neg \left(\forall x,\exists y,y<x\right)$$

2. Apply negation to $\forall$: Using the equivalence $\neg \forall xP(x)\equiv \exists x\neg P(x)$, we negate the universal quantifier:

   $$T:\exists x,\neg \left(\exists y,y<x\right)$$

3. Apply negation to $\exists$: Next, apply the equivalence $\neg \exists yQ(y)\equiv \forall y\neg Q(y)$:

   $$T:\exists x,\forall y,y\ge x$$

4. Result: This expression simplifies to:

   $$\exists x,\forall y,x\le y$$

This is identical to statement $S$. Thus, $S$ and $T$ are logically equivalent.

Quantifier Distribution

Quantifier distribution essentially says that you can often move a quantifier (either universal or existential) across certain logical operators if you carefully adjust the scope of the quantifier and potentially the negations involved.

Key Rules:

• Universal Quantifier Distributes Over Conjunction:

  $\forall x(P(x)\wedge Q(x))\equiv (\forall xP(x))\wedge (\forall xQ(x))$

• Existential Quantifier Distributes Over Disjunction:

  $\exists x(P(x)\vee Q(x))\equiv (\exists xP(x))\vee (\exists xQ(x))$

• Universal Quantifier Does Not Distribute Over Disjunction:

  $\forall x(P(x)\vee Q(x))\text{ is not}\equiv (\forall xP(x))\vee (\forall xQ(x))$

• Existential Quantifier Does Not Distribute Over Conjunction:

  $\exists x(P(x)\wedge Q(x))\text{ is not}\equiv (\exists xP(x))\wedge (\exists xQ(x))$

Transitive Property

The transitive property is a fundamental rule for binary relations. It states that if one element is related to a second, and that second element is related to a third, then the first element must be related to the third.

Example:

$$\forall x\forall y\forall z((P(x,y)\wedge P(y,z))\to P(x,z)))$$

Continue here: 05 Proof Types