Quantifier

A quantifier specifies how many elements in the domain of a variable a logical statement is making a claim about. In other words, it defines the scope of the assertion. A statement with a universal or existential quantifier is a quantified statement. Quantifiers are applied before any logical operations, so be sure to make use of parentheses to indicate order.

Notably, quantifiers bind variables, allowing predicates to become propositions whose truth values can be determined. The variable bound by a quantifier is always specified immediately after the quantifier symbol. If a predicate contains multiple variables, all must be bound (either by quantifiers or by substituting in specific values) in order for it to become a proposition.

Contents

Universal quantifiers

Applying universal quantifiers to statements results in universal statements. If $P(x)$ is a predicate, then $\forall x P(x)$ is the proposition "for all $x$, $P(x)$ is true," or, reworded, "for every $x$, $P(x)$ is true." In order for this universal statement to be true, $P(x)$ must be true for every element in the domain of $x.$

If $x$ has a finite domain $D$ of size $n$, written as $D=\set {a_1, ... a_n}$:

$$\forall x P(x) \equiv P(a_1) \land ... \land P(a_n)$$

As you can see, universally quantifying the predicate $P(x)$ results in the proposition $\forall x P(x)$, which is logically equivalent to the conjunction of all propositions that result from evaluating that predicate for every element in the domain of $x.$

When the domain is small, you can prove a universal statement is true by checking that the predicate is true for every element in the domain. However, when the domain is large or infinite, this becomes totally impractical! That's why universal generalization is preferred, since we often work with infinite domains. To show a universal statement is false, come up with a counterexample.

Existential quantifiers

Applying existential quantifiers to statements results in existential statements. If $P(x)$ is a predicate, then $\exists x P(x)$ is the proposition "there exists an $x$ such that $P(x)$ is true." In order for this existential statement to be true, $P(x)$ must be true for at least one element in the domain of $x.$

If $x$ has a finite domain $D$ of size $n$, written as $D=\set {a_1, ... a_n}$:

$$\exists x P(x) \equiv P(a_1) \lor ... \lor P(a_n)$$

As you can see, existentially quantifying the predicate $P(x)$ results in the proposition $\exists x P(x)$, which is logically equivalent to the disjunction of all propositions that result from evaluating that predicate for every element in the domain of $x.$

You can prove an existential statement is true by coming up with an example, an element in the domain for which the predicate is true. To show an existential statement is false, you will have to prove its negation true, which, by De Morgan's law for quantified statements, is a universal statement. Therefore, you'll need to prove the negation with universal generalization.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort