Discrete Math — Symbols Cheat Sheet

Quick reference: logic, sets, quantifiers, number sets, intervals, and truth sets.

Number Sets & Interval / Set-Builder Notation

Set Meaning Examples
ℕ Natural numbers 0,1,2,3,...
ℤ Integers ..., -2,-1,0,1,2,...
ℚ Rational numbers (fractions) 1/2, -3/4, 7
ℝ Real numbers (including decimals) -2.5, 0, 3.1415
ℂ Complex numbers 2+3i
Notation Meaning / Example
(a,b) Interval: all real numbers x where a < x < b
[a,b] Interval: a ≤ x ≤ b
{x ∈ ℝ | a < x < b} Set-builder: "x in ℝ such that a < x < b"
{x ∈ ℤ | n / x ∈ ℤ} All integers dividing n (truth set)
| or : "Such that" in set-builder notation

Interval ↔ Set-Builder Conversion

Interval Set-Builder Equivalent
(a,b) { x ∈ ℝ | a < x < b }
[a,b] { x ∈ ℝ | a ≤ x ≤ b }
(a,b] { x ∈ ℝ | a < x ≤ b }
[a,b) { x ∈ ℝ | a ≤ x < b }
(-∞, b) { x ∈ ℝ | x < b }
(a, ∞) { x ∈ ℝ | x > a }
(-∞, ∞) { x ∈ ℝ }

Quick reference: "(" or ")" = not included, "[" or "]" = included.

Conditional Statement Variations

Let the original conditional statement be: If P, then Q.

Form Symbolic Example (P: it rains, Q: the ground is wet)
Original P → Q If it rains, then the ground is wet.
Negation ~(P → Q) It is not true that if it rains then the ground is wet.
Converse Q → P If the ground is wet, then it rains.
Inverse ~P → ~Q If it does not rain, then the ground is not wet.
Contrapositive ~Q → ~P If the ground is not wet, then it does not rain.

Note: The contrapositive is logically equivalent to the original statement, but the converse and inverse are not necessarily equivalent.

Quick Truth Set Reference

For predicates of the form n / x ∈ ℤ with x ∈ ℤ:

Example Truth Set
10 / x ∈ ℤ {-10, -5, -2, -1, 1, 2, 5, 10}
12 / x ∈ ℤ {-12,-6,-4,-3,-2,-1,1,2,3,4,6,12}
7 / x ∈ ℤ {-7,-1,1,7}

Tip: This works for any integer n; just list all nonzero divisors.

Logic

Symbol Meaning
~P NOT (negation)
P ∧ Q AND (conjunction)
P ∨ Q OR (inclusive disjunction)
P ⊕ Q XOR (exclusive OR)
P → Q Implication (“if P then Q”)
P ↔ Q Biconditional (“iff”)
Other Notes
∴ Therefore
∵ Because
P → Q ≡ ~P ∨ Q Useful equivalence
P ↔ Q ≡ (P → Q) ∧ (Q → P) Biconditional = two implications

Set Theory

Symbol Meaning
∈ Element of (e.g. 3 ∈ A means 3 is in A)
∉ Not element of (e.g. 5 ∉ A means 5 is not in A)
∅ Empty set (contains no elements)
{ } Set braces — list elements, e.g. {1,2,3}
⊆ Subset — A ⊆ B means every element of A is also in B
⊂ Proper subset — A ⊂ B means A ⊆ B and A ≠ B
Symbol Meaning / Operation
∪ Union — all elements in A or B (A ∪ B)
∩ Intersection — elements in both A and B (A ∩ B)
− Difference — elements in A but not in B (A − B)
Ac Complement — everything not in A (relative to the universe)
× Cartesian product — all ordered pairs (a,b) where a ∈ A, b ∈ B
|A| Cardinality — number of elements in A

Quick examples: A ∪ B = everything in either set; A ∩ B = overlap; A − B = only A’s leftovers; Ac = opposite of A (if U is the universe).

Quantifiers & Number Sets

Symbol Meaning
∀ For all (universal quantifier)
∃ There exists (existential quantifier)
∄ There does not exist
| Such that (in set-builder)
Symbol Meaning
ℕ Natural numbers (0,1,2,...)
ℤ Integers (...,-2,-1,0,1,2,...)
ℚ Rational numbers
ℝ Real numbers
ℂ Complex numbers

Other Useful Symbols

Symbol Meaning / Example
≡ Congruence / equivalence (e.g. 7 ≡ 1 (mod 3))
mod Modulo operation (14 mod 5 = 4)
⌊x⌋ Floor (round down)
⌈x⌉ Ceiling (round up)
⇒ / ⇔ Implies / iff (often used in proofs)

Equivalence Relations

A relation is an equivalence relation if it satisfies all three:

Equivalence Classes

The equivalence class of an element a under relation R is:

{ x ∈ A | x R a }

Example Equivalence Classes
Congruence mod n Numbers with the same remainder mod n
Truth-table equivalence All statements with identical truth tables

Relation Properties

Property Definition Notes
Reflexive ∀a, (a,a) ∈ R Everything relates to itself
Symmetric (a,b) ∈ R ⇒ (b,a) ∈ R Can reverse direction
Transitive (a,b),(b,c) ∈ R ⇒ (a,c) ∈ R Chaining property
Antisymmetric (a,b),(b,a) ∈ R ⇒ a=b Used in ≤, ≥ and partial orders

Functions & Mapping Types

Type Definition Example / Notes
Injective (One-to-One) f(a₁)=f(a₂) ⇒ a₁=a₂ No two inputs share an output
Surjective (Onto) Every element of codomain has a preimage Covers entire codomain
Bijective Both injective and surjective Perfect pairing → invertible

Modular Arithmetic

Definition: a ≡ b (mod n) means n | (a − b).

Property Rule
Addition a ≡ b, c ≡ d ⇒ a+c ≡ b+d (mod n)
Multiplication a ≡ b ⇒ ac ≡ bc (mod n)
Transitivity a ≡ b, b ≡ c ⇒ a ≡ c (mod n)
Equivalent Rewrite a ≡ b ⇔ a mod n = b mod n

GCD & The Euclidean Algorithm

To compute gcd(a, b), repeatedly apply:

a = bq + r

until r = 0. The final nonzero remainder = gcd.

Properties