2Sets, functions and relations
IA Numbers and Sets
2.1 Sets
Definition
(Set)
.
A set is a collection of stuff, without regards to order. El-
ements in a set are only counted once. For example, if
a
= 2
, b
=
c
= 1, then
A
=
{a, b, c}
has only two members. We write
x ∈ X
if
x
is a member of the set
X.
Example. Common sets and the symbols used to denote them:
– N = {1, 2, 3, ···} is the natural numbers
– N
0
= {0, 1, 2, ···} is the natural numbers with 0
– Z = {··· , −2, −1, 0, 1, 2, ···} is the integers
– Q = {
a
b
: a, b ∈ Z, b 6= 0} is the rational numbers
– R is the real numbers
– C is the complex numbers
It is still debated whether 0 is a natural number. Those who believe that 0 is a
natural number usually write
N
for
{
0
,
1
,
2
, ···}
, and
N
+
for the positive natural
numbers. However, most of the time, it doesn’t matter, and when it does, you
should specify it explicitly.
Definition (Equality of sets). A is equal to B, written as A = B, if
(∀x) x ∈ A ⇔ x ∈ B,
i.e. two sets are equal if they have the same elements.
Definition
(Subsets)
. A
is a subset of
B
, written as
A ⊆ B
or
A ⊂ B
, if all
elements in A are in B. i.e.
(∀x) x ∈ A ⇒ x ∈ B.
Theorem. (A = B) ⇔ (A ⊆ B and B ⊆ A)
Suppose
X
is a set and
P
is the property of some elements in
x
, we can write
a set
{x ∈ X
:
P
(
x
)
}
for the subset of
x
comprising of the elements for which
P (x) is true. e.g. {n ∈ N : n is prime} is the set of all primes.
Definition
(Intersection, union, set difference, symmetric difference and power
set). Given two sets A and B, we define the following:
– Intersection: A ∩ B = {x : x ∈ A and x ∈ B}
– Union: A ∪ B = {x : x ∈ A or x ∈ B}
– Set difference: A \ B = {x ∈ A : x 6∈ B}
–
Symmetric difference:
A
∆
B
=
{x
:
x ∈ A xor x ∈ B}
, i.e. the elements in
exactly one of the two sets
– Power set: P(A) = {X : X ⊆ A}, i.e. the set of all subsets
New sets can only be created via the above operations on old sets (plus
replacement, which says that you can replace an element of a set with another
element). One cannot arbitrarily create sets such as
X
=
{x
:
x is a set and x 6∈
x}. Otherwise paradoxes will arise.
We have several rules regarding how these set operations behave, which
should be intuitively obvious.
Proposition.
– (A ∩ B) ∩ C = A ∩ (B ∩ C)
– (A ∪ B) ∪ C = A ∪ (B ∪ C)
– A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Notation. If A
α
are sets for all α ∈ I, then
\
α∈I
A
α
= {x : (∀α ∈ I)x ∈ A
α
}
and
[
α∈I
A
α
= {x : (∃α ∈ I)x ∈ A
α
}.
Definition
(Ordered pair)
.
An ordered pair (
a, b
) is a pair of two items in which
order matters. Formally, it is defined as
{{a}, {a, b}}
. We have (
a, b
) = (
a
0
, b
0
)
iff a = a
0
and b = b
0
.
Definition
(Cartesian product)
.
Given two sets
A, B
, the Cartesian product
of
A
and
B
is
A × B
=
{
(
a, b
) :
a ∈ A, b ∈ B}
. This can be extended to
n
products, e.g.
R
3
=
R × R × R
=
{
(
x, y, z
) :
x, y, z ∈ R}
(which is officially
{(x, (y, z)) : x, y, z ∈ R}).