Set Theory
Introduction
Definitions
- What is a set — A collection of distinct elements.
- What is an element — A member of a set.
- Notation — Usually written using {} e.g. {0,1,2,3,5,8}
- Cardinality — The number of elements in the set. The above set has cardinality 6.
Types of Sets
Countably Infinite Sets
A set is countably infinite if you can line up every element so each one has its own unique index. (One‑to‑one correspondence with the natural numbers.)
Examples: N — Natural numbers
{0,1,2,3,...} or {1,2,3,4,...}
Z — Integers
{..., -2, -1, 0, 1, 2, ...}
Z⁺ — Positive integers
{1,2,3,4,...}
Q — Rational numbers (p/q) where p is an integer and q is a non‑zero integer.
Uncountably Infinite Sets
These sets have “more” elements than there are natural numbers — you cannot assign each element a unique index.
Example: real numbers between 0 and 1
0.1, 0.11, 0.111, 0.2, 0.22, 0.222, ...
R — Real numbers C — Complex numbers
Finite Sets
A set with a limited number of elements. Its cardinality is a natural number.
Examples:
- primary colours (red, yellow, blue)
- days of the week
- hours in the day
Why I’m Here
The set of remainders of integers modulo n.
For a given integer n, the possible remainders are:
{0, 1, 2, ..., n−1}
So for modulo n:
- Cardinality = n
- Largest element = n−1
We are focusing on the **remainder** — the amount left over — not the quotient (how many times it divides exactly).
Example:
(7 + 3) mod 5 7 + 3 = 10 10 = 5 × 2 + 0 Quotient = 2 Remainder = 0
So the answer is 0.