Lecture from: 30.09.2024  Video: Videos ETHZ
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., $∀x$, $∃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 ($∀$):
 Symbol: $∀$
 Meaning: “For all,” “For every”
 Asserts that a statement holds true for every element in the given universe.
 Example: "$∀x∈R,x_{2}≥0$" (For all real numbers $x$, $x_{2}$ is greater than or equal to zero).
Existential Quantifier ($∃$):
 Symbol: $∃$
 Meaning: “There exists,” “At least one”
 Asserts that at least one element in the universe satisfies a given condition.
 Example: "$∃x∈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 ($N$) and integers ($Z$)?
 Universe $N$: “There exists an $x$ such that $x+2=1$” is false because no natural number satisfies this condition.
 Universe $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=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=Z$ (Integers):
 The same statement, “There exists an $x$ such that $x+2=1,"becomes∗∗true∗∗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:
 $¬∀xP(x)≡∃x¬P(x)$
 $¬∃xP(x)≡∀x¬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=N$ (the set of natural numbers).
Statement $S$: “There exists a smallest number.”
In predicate logic, this can be written as:
$S:∃x,∀y,x≤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:
$∀x,∃y,y<x$The negation of this is:
$T:¬(∀x,∃y,y<x)$This means it is not true that every number has a smaller one.
StepbyStep Negation Process
Let’s now show how the negation transforms $T$ into $S$:

Start with $T$:
$T:¬(∀x,∃y,y<x)$ 
Apply negation to $∀$: Using the equivalence $¬∀xP(x)≡∃x¬P(x)$, we negate the universal quantifier:
$T:∃x,¬(∃y,y<x)$ 
Apply negation to $∃$: Next, apply the equivalence $¬∃yQ(y)≡∀y¬Q(y)$:
$T:∃x,∀y,y≥x$ 
Result: This expression simplifies to:
$∃x,∀y,x≤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:
$∀x(P(x)∧Q(x))≡(∀xP(x))∧(∀xQ(x))$

Existential Quantifier Distributes Over Disjunction:
$∃x(P(x)∨Q(x))≡(∃xP(x))∨(∃xQ(x))$

Universal Quantifier Does Not Distribute Over Disjunction:
$∀x(P(x)∨Q(x))is not≡(∀xP(x))∨(∀xQ(x))$

Existential Quantifier Does Not Distribute Over Conjunction:
$∃x(P(x)∧Q(x))is not≡(∃xP(x))∧(∃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:
$∀x∀y∀z((P(x,y)∧P(y,z))→P(x,z)))$Continue here: 05 Proof Types