Symbol | Meaning | Read As |
---|---|---|
∀ | Universal Quantifier | "For all," "For every," "For each," "For any" |
∃ | Existential Quantifier | "There exists," "For some," "There is at least one" |
P(x) | Predicate | Statement about variable x |
⇒ | Conditional | "If...then," "Implies" |
⇔ | Biconditional | "If and only if," "Necessary and sufficient" |
∧ | Logical AND | "And" |
∨ | Logical OR | "Or" |
¬ | Negation | "Not" |
A predicate is a statement containing variables
The truth set of a predicate is the set of all values that make the predicate true
Domain refers to the set of all possible values for the variables
Given Q(n): "n is a factor of 8"
Truth set with domain of positive integers: {1, 2, 4, 8}
Truth set with domain of all integers: {1, 2, 4, 8, -1, -2, -4, -8}
Indicates that a predicate is true for all elements in a domain
Example: ∀x ∈ H, x is mortal (read as "For every x in H, x is mortal")
A universal statement is true when the predicate is true for all elements
A universal statement is false if there exists at least one counterexample
Indicates that a predicate is true for at least one element in a domain
Example: ∃p ∈ P such that p is a student in CSE2500
An existential statement is true if the predicate is true for at least one element
An existential statement is false if the predicate is false for all elements
Form: ∀x, if P(x) then Q(x)
Most important form of statement in mathematics
Can be written informally in various ways:
"If a real number is greater than 2, then its square is greater than 4"
"All integers are rational numbers"
∀x ∈ U, if P(x) then Q(x) ≡ ∀x ∈ D, Q(x) where D is the subset of U where P(x) is true
∀x ∈ D, Q(x) ≡ ∀x, if x is in D then Q(x)
Negation of ∀: ¬(∀x, P(x)) ≡ ∃x, ¬P(x)
"It is not true that all X are Y" ≡ "There exists at least one X that is not Y"
Negation of ∃: ¬(∃x, P(x)) ≡ ∀x, ¬P(x)
"It is not true that there exists an X that is Y" ≡ "All X are not Y"
¬(∀x, if P(x) then Q(x)) ≡ ∃x, P(x) ∧ ¬Q(x)
"Not all X with property P have property Q" ≡ "There exists an X with property P that doesn't have property Q"
Universal statements (∀) are related to AND (∧) statements
If domain is finite: ∀x ∈ {a,b,c}, Q(x) ≡ Q(a) ∧ Q(b) ∧ Q(c)
Existential statements (∃) are related to OR (∨) statements
If domain is finite: ∃x ∈ {a,b,c}, Q(x) ≡ Q(a) ∨ Q(b) ∨ Q(c)
A universal statement is vacuously true if the domain is empty or if the condition P(x) is false for all x
Example: "All elephants in this room are pink" is vacuously true if there are no elephants in the room
Contrapositive: ∀x, if ¬Q(x) then ¬P(x)
Logically equivalent to the original statement
Converse: ∀x, if Q(x) then P(x)
Not logically equivalent to the original statement
Inverse: ∀x, if ¬P(x) then ¬Q(x)
Not logically equivalent to the original statement
P is a sufficient condition for Q means "if P then Q"
P is a necessary condition for Q means "if Q then P" (or "only if P, Q")
"Only if" indicates a necessary condition
"A product is 0 only if one of the factors is 0" means "If a product is 0, then one of the factors is 0"
∀x ∃y P(x,y) ≠ ∃y ∀x P(x,y)
"For every x, there exists a y such that P(x,y)" means you can find a (possibly different) y for each x
"There exists a y such that for every x, P(x,y)" means there is one specific y that works for all x
"∀x ∃y (x loves y)" means "Everyone loves someone" (possibly different for each person)
"∃y ∀x (x loves y)" means "There is someone whom everyone loves" (same person)
Order doesn't matter when quantifiers are the same type:
∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y)
∃x ∃y P(x,y) ≡ ∃y ∃x P(x,y)
¬(∀x ∃y P(x,y)) ≡ ∃x ∀y ¬P(x,y)
¬(∃x ∀y P(x,y)) ≡ ∀x ∃y ¬P(x,y)
∀x in D, P(x) can be written as ∀x (x in D → P(x))
∃x in D such that P(x) can be written as ∃x (x in D ∧ P(x))
Form:
∀x, P(x)
a is a particular element
Therefore, P(a)
Example: "All men are mortal. Socrates is a man. Therefore, Socrates is mortal."
Form:
∀x, if P(x) then Q(x)
P(a), for a particular a
Therefore, Q(a)
Combines universal instantiation with modus ponens
Form:
∀x, if P(x) then Q(x)
¬Q(a), for a particular a
Therefore, ¬P(a)
Combines universal instantiation with modus tollens
Used in proof by contradiction
Universal statements (∀x ∈ A, P(x)) can be represented by placing set A inside the set of things with property P
This helps visualize relationships in arguments to determine validity
Converse Error: Assuming "if P then Q" means "if Q then P"
Inverse Error: Assuming "if P then Q" means "if not P then not Q"
These are invalid unless the original premise is a biconditional (if and only if)
When finding truth values:
For universal statements (∀), check if the predicate is true for ALL elements in the domain
For existential statements (∃), check if the predicate is true for AT LEAST ONE element in the domain
When negating statements:
∀ becomes ∃ (and vice versa)
The predicate gets negated
For multiple quantifiers, negate from left to right, changing each quantifier type
When analyzing arguments:
Use universal instantiation to apply universal statements to specific cases
Check the form of the argument (universal modus ponens or universal modus tollens)
Be careful of converse and inverse errors
When translating between formal and informal language:
"All X are Y" = ∀x, if x is X then x is Y
"No X are Y" = ∀x, if x is X then x is not Y
"Some X are Y" = ∃x such that x is X and x is Y
"Some X are not Y" = ∃x such that x is X and x is not Y
Predicate: A statement that contains variables
Truth Set: Set of values that make a predicate true
Domain: Set of all possible values for variables
Universal Quantifier (∀): Indicates truth for all elements
Existential Quantifier (∃): Indicates truth for at least one element
Vacuous Truth: A universal statement that is true because the condition is never satisfied
Sufficient Condition: If P is sufficient for Q, then P implies Q
Necessary Condition: If P is necessary for Q, then Q implies P