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}).