Discrete Mathematics Definitions

Fall 2025

What does it mean that a divides b (notation: a | b)?

a divides b if there exists an integer k such that b = ak.

What is an even integer?

An integer of the form 2k for some integer k.

What is an odd integer?

An integer of the form 2k + 1 for some integer k.

What is a prime number?

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

What is a composite number?

A positive integer >1 that is not prime (it has divisors other than 1 and itself).

What is a rational number?

A number that can be written as p/q where p and q are integers and q ≠ 0.

What is a set?

A collection of distinct objects.

What does A ⊆ B mean?

Every element of A is also an element of B.

What is cardinality?

The number of elements in a set.

What is the empty set?

The set with no elements, written ∅.

What is the power set of A?

The set of all subsets of A.

What does it mean for sets A and B to be disjoint?

They share no elements: A ∩ B = ∅.

What does it mean for a collection of sets to be pairwise disjoint?

Every pair of distinct sets in the collection is disjoint.

What is the union A ∪ B?

The set of elements in A, in B, or in both.

What is the intersection A ∩ B?

The set of elements common to both A and B.

What is the set difference A − B?

Elements in A that are not in B.

What is A △ B (symmetric difference)?

Elements in A or B but not both.

What is A × B?

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

What is the contrapositive of “If P, then Q”?

“If not Q, then not P.”

What is a relation between A and B?

Any subset of A × B.

What is a function?

A relation where each input has exactly one output.

What is the inverse of a relation R?

R⁻¹ = { (b, a) | (a, b) ∈ R }.

What is the domain of a function f?

The set of inputs for which the function is defined.

What is the image of an element or set under f?

f(A) = { f(x) | x ∈ A }.

What is the codomain of a function?

The set in which the function’s outputs are declared to live.

What is an injective function?

Distinct inputs give distinct outputs:

What is a surjective function?

Every element of the codomain is hit by the function.

What is a bijective function?

A function that is both injective and surjective.

What does a ≡ b (mod n) mean?

n divides (a − b), or a and b have the same remainder when divided by n.

What is gcd(a, b)?

The largest integer that divides both a and b.

What does it mean for a and b to be relatively prime?

gcd(a, b) = 1.

What is a reciprocal / multiplicative inverse of a modulo n?

An integer b such that ab ≡ 1 (mod n).