A set is defined as a well-defined collection of distinct objects, considered as an object in its
own right. Here, ”well-defined” means that there is a clear criterion that determines whether
any given object belongs to the set or not.
The objects that make up a set are called the elements or members of the set. If x is an
element of the set S , we write x ∈ S . If x is not an element of S , we write x ∉ S .
Formally, a set S can be defined by:
1. Extensionality: Two sets are equal if and only if they have the same elements.
A = B ⟺ ∀x(x ∈ A ⟺ x ∈ B)
2. Unordered collection: The order of elements in a set does not matter.
{a, b, c} = {b, a, c}
3. No Repetition: Each element appears only once.
{a, a, b} = {a, b}
Cardinality
The cardinality of a set S , denoted |S|, is a measure of the “number of elements” in the set.
Two sets A and B have the same cardinality if there exists a Bijection (one-to-one and onto
function) between them.
|A| = |B| ⟺ ∃ f : A → B such that f is a bijection
1. Finite Sets: A set S is finite if there exists a bijection (one-to-one correspondence)
between the set S and a set {1, 2, . . . , n} for some natural number n. In other words, a
set S is finite if there exists a natural number n such that the cardinality of S , denoted
by |S|, is n.
2. Infinite Sets: A set S is infinite if it is not finite. This means there is no natural number n
such that |S| = n. Infinite sets can be further categorised into countably infinite and
uncountably infinite sets.
Countability Infinite Sets: A set S is countably infinite if there exists a bijection
between S and the set of natural numbers N . In other words, S is countably
infinite if its elements can be listed in a sequence s , s , s , . . . . Formally, S is
1 2 3
countably infinite if |S| = |N|
Uncountably Infinite Sets: A set S is uncountably infinite if it is infinite and not
countably infinite. This means there is no bijection between S and N. A typical
example of an uncountably infinite set is the set of real numbers R.
3. Cardinality of Infinite Sets:
Aleph-Null (ℵ ): The cardinality of the set of natural numbers N is denoted by ℵ .
0 0
Any countably infinite set has cardinality ℵ .
0
Continuum (c): The cardinality of the set of real numbers R is denoted by c. The
continuum hypothesis explores the relationship between ℵ and c, positing that
0
there is no set whose cardinality is strictly between ℵ and c.
0
Is Q bigger than Z?
Z and N: The set of integers Z is countably infinite, which means there is a bijection between
Z and N. An example of such bijection is:
2n if n ≥ 0
f (n) = {
−2n − 1 if n < 0
Q and N: The set of rational numbers Q is also countably infinite. A common way to see this
is by listing the rational numbers in a way that covers all of them (like a grid of fractions p
with p, q ∈ Z and q ≠ 0), and then mapping them to N using a systematic process (such as
the diagonal argument).
Therefore, Q and Z both have the same cardinality, ℵ . Thus, Q is not bigger than Z; they
0
are the same size in terms of cardinality.
Is R bigger than Q?
R and N: The set of real numbers R is uncountably infinite. This means there is no
bijection between R and N. Cantor's diagonal argument shows that the set of real
numbers cannot be listed in a sequence that includes every real number.
Q and N: As previously stated, Q is countably infinite, meaning there is a bijection
between Q and N.
Since R is uncountably infinite and Q is countably infinite, the cardinality of R (denoted by c)
is strictly greater than the cardinality of Q (denoted by ℵ ). 0
Subsets
A set B is a subset of a set A, denoted B ⊆ A, if every element of B is also an element of A.
Formally:
∀x (x ∈ B ⟹ x ∈ A)
Proper Subset: If B ⊆ A and B ≠ A, then B is a proper subset of A, denoted B ⊂ A.
Note
A set can be a subset of itself. Formally, for any set A, it is true that A ⊆ A. This is
because every element of A is also an element of A, which satisfies the definition of a
subset.
Empty Set: The empty set ∅, a set with no elements, is a subset of every set. By the
definition of a subset, for any set A, every element of the empty set ∅ is also an element of A
, simply because the empty set has no elements.
Formally, for any set A, the statement ∀x (x ∈ ∅ ⟹ x ∈ A) is vacuously true, because
there are no elements in ∅ that could fail to be in A.
Power Set: The power set of a set A is the set of all subsets of A, denoted by P(A). The
power set always includes A and the empty set ∅.
Cardinality of Power Set: If A has n elements, then P(A) has 2 elements, including the
n
empty set and A itself.
