Discrete Mathematics I Definitions

Fall 2025

Natural Numbers

"The set of counting numbers. Either N = {1,2,3,...} or N₀ = {0,1,2,3,...}. Instructor specifies the convention."

Rational Number

A number that can be written as a ratio of two integers with a nonzero denominator: q = a/b where a,b ∈ ℤ and b ≠ 0.

a divides b (a | b)

a | b means there exists an integer k such that b = ak. Dividing b by a leaves no remainder.

Even Integer

An integer n is even if n = 2k for some integer k.

Odd Integer

An integer n is odd if n = 2k + 1 for some integer k.

Prime Number

A positive integer p > 1 whose only positive divisors are 1 and itself.

Composite Number

A positive integer n > 1 that has a divisor other than 1 and itself; equivalently, n = ab for integers a,b with 1 < a < n.

Theorem

A mathematical statement that has been proven true using logical reasoning and previously established results such as axioms, definitions, and earlier theorems.

Conditional (if–then) Statement

A logical statement of the form 'if P, then Q'. Written P → Q. It is false only when P is true and Q is false.

Biconditional (iff) Statement

A statement of the form 'P if and only if Q'. Written P ↔ Q. It is true exactly when P and Q have the same truth value.

Converse

For a conditional P → Q, the converse is Q → P.

Inverse

For a conditional P → Q, the inverse is ¬P → ¬Q.

Contrapositive

For a conditional P → Q, the contrapositive is ¬Q → ¬P. A conditional and its contrapositive always have the same truth value.

Truth Table

A table listing all possible truth values of the component statements and showing the resulting truth value of a compound statement for each case.

Existential Quantifier (∃)

The logical symbol ∃ meaning 'there exists'. A statement ∃x P(x) asserts that at least one element in the domain satisfies P(x).

Universal Quantifier (∀)

The logical symbol ∀ meaning 'for all'. A statement ∀x P(x) asserts that every element in the domain satisfies P(x).

Direct Proof

A proof method that assumes the hypothesis P of an implication P → Q is true and uses logical reasoning and known facts to show that the conclusion Q must also be true.

Counterexample

A specific example that shows a universally quantified statement is false. To disprove '∀x P(x)', it is enough to find one x for which P(x) is false.

List

An ordered collection of elements where repetition is allowed and position matters; often written using angle brackets or parentheses, such as ⟨a,b,c⟩.

Factorial

For a nonnegative integer n, the factorial n! is the product of all positive integers from 1 to n. Defined as n! = n(n−1)(n−2)…1, with 0! = 1 by convention.

Set

A well-defined collection of distinct objects, called elements or members.

Element

An object that belongs to a set; written x ∈ A to mean x is an element of set A.

Cardinality

The number of elements in a set A, written |A|.

Empty Set

The set with no elements, written ∅ or {}. Its cardinality is 0.

Subset

A set A is a subset of B, written A ⊆ B, if every element of A is also an element of B.

Power Set

The set of all subsets of a set A, including ∅ and A itself; written P(A). If |A| = n, then |P(A)| = 2^n.

Union

The set of elements that are in A or in B (or in both); written A ∪ B.

Disjoint

Two sets A and B are disjoint if their intersection is empty: A ∩ B = ∅.

Pairwise Disjoint

A collection of sets is pairwise disjoint if every two distinct sets in the collection are disjoint from each other.

Set Difference

The set of elements in A that are not in B; written A \ B or A − B.

Symmetric Difference

The set of elements in A or B but not both; written A △ B or (A \ B) ∪ (B \ A).

Complement

Given a universal set U, the complement of A is the set of elements in U that are not in A; written Aᶜ.

Cartesian Product

The set of all ordered pairs (a,b) with a ∈ A and b ∈ B; written A × B.

Relation

A relation from A to B is any subset of the Cartesian product A × B; it pairs elements of A with elements of B.

Function

A relation f from A to B such that every element of A is paired with exactly one element of B; written f: A → B.

Domain

The set of all input values for which a function or relation is defined.

Image

For a function f: A → B, the image of an element a ∈ A is f(a); the image of a set S ⊆ A is {f(x) : x ∈ S}.

Codomain

The set B in a function f: A → B; the set of possible outputs (not necessarily all achieved).

Inverse

For a relation R, the inverse is R⁻¹ = {(b,a) : (a,b) ∈ R}. A function has an inverse only if it is bijective.

Injective (One-to-One)

A function f: A → B is injective if different inputs map to different outputs: f(a₁)=f(a₂) implies a₁=a₂.

Surjective (Onto)

A function f: A → B is surjective if every element of the codomain B is the image of some element of A.

Bijective

A function that is both injective and surjective; equivalently, a function with a two-sided inverse.

Composition

Given functions f: A → B and g: B → C, the composition g∘f is the function from A to C defined by (g∘f)(x) = g(f(x)).

Identity Function

For a set A, the identity function id_A is the function id_A(x) = x for all x ∈ A. It leaves every element unchanged.

Common Divisor

An integer d is a common divisor of a and b if d divides both: d | a and d | b.

Greatest Common Divisor

The greatest common divisor (gcd) of integers a and b is the largest integer d such that d | a and d | b; written gcd(a,b).

Euclid's Algorithm

An efficient method for computing gcd(a,b) using repeated division: gcd(a,b) = gcd(b, a mod b) until the remainder is 0.

Bézout's Identity

For integers a and b, their gcd can be written as a linear combination: gcd(a,b) = ax + by for some integers x and y.

Relatively Prime

Two integers a and b are relatively prime if gcd(a,b) = 1.

Modular Addition

Given integers a and b modulo n, their sum is (a + b) mod n; results are always reduced modulo n.

Modular Subtraction

Given integers a and b modulo n, their difference is (a - b) mod n; results are reduced modulo n.

Modular Multiplication

Given integers a and b modulo n, their product is (a · b) mod n; results are reduced modulo n.

Modular Division

To compute a / b mod n, we multiply a by the modular inverse of b modulo n (only valid if b has an inverse).

Modular Reciprocal

For integer a modulo n, the modular reciprocal (inverse) is an integer x such that a·x ≡ 1 (mod n); it exists exactly when gcd(a,n) = 1.

x ∈ A

x is an element of set A.

x ∉ A

x is not an element of set A.

A ⊆ B

A is a subset of B; every element of A is in B.

A ⊂ B

A is a proper subset of B; A ⊆ B but A ≠ B.

A ⊇ B

A is a superset of B.

A ∪ B

Union: elements in A or B (or both).

A ∩ B

Intersection: elements common to both A and B.

A \ B

Set Difference: elements in A that are not in B.

A △ B

Symmetric difference: elements in exactly one of A or B.

Aᶜ

Complement of A: all elements not in A (relative to a universal set).

P(A)

Power set: the set of all subsets of A.

|A|

Cardinality: the number of elements in A.

A × B

Cartesian product: all ordered pairs (a,b) with a ∈ A and b ∈ B.

(a,b)

An ordered pair with first component a and second component b.

f: A → B

Function f from domain A to codomain B.

f(x)

The image of x under function f.

f⁻¹

Inverse relation (or inverse function if f is bijective).

g ∘ f

Composition: (g ∘ f)(x) = g(f(x)).

id_A

Identity function on A: id_A(x) = x.

R ⊆ A × B

R is a relation from A to B.

∀

Universal quantifier: 'for all'

∃

Existential quantifier: 'there exists'.

¬P

Negation of P.

P ∧ Q

Logical AND

P ∨ Q

Logical OR

P → Q

Conditional: 'if P, then Q'

P ↔ Q

Biconditional: 'P if and only if Q'.

P'

Complement of proposition P (alternate notation for ¬P)

a | b

a divides b: there exists k such that b = ak.

gcd(a,b)

Greatest common divisor of a and b.

lcm(a,b)

Least common multiple of a and b.

a ≡ b (mod n)

a is congruent to b modulo n: n divides (a−b).

a mod n

Remainder when a is divided by n.

n!

Factorial: n! = n·(n−1)·...·1, with 0! = 1.

ℕ

Set of natural numbers.

ℤ

Set of integers.

ℚ

Set of rational numbers.