Lecture Notes on Comparing Sets (COMP11120)

Comparing Sets

Definition : Size of set S is less than or equal to size of set T Definition : A set S is infinite iff there is SES
iff there is an injection from S to
T




.
and f : > S'
5- is injective .




Example : IN and Example :
I is infinite



I # Let S =
1 and S =
2 (o]
: !

3 > 3 I I > I <03
2 2 : M
>




S
N + 1 X20
1 > 1 3n XI "
x else
O > O 2

-
1 1 -




O
fiN > 2
-

-




2 +- 7
-
3 -

1 ?

25
-




:

-


3?




Definition : Two sets S andT have the same size Proposition : A set S is infinite iff there is
f : S <S that is injective and


iff size of S size
of T not surjective.

and size of T & Size
of S




Example : IN and Proposition If : a set S is infinite ,
it is at least as big as IN.

IN is minimal infinite set !

I # I

: ! : know have fi5 >
-
S ,
f is injective , not surjective.
M >
4 : 4 Have seS such that Use S .
fs' = S

3 > 3 93

2 2 : 2
Prove: Want > S
IN- injective
>
is
9 g
:
,

1 > 1 1

O
f
O O
> > x1 Let n
,
m E IN

1
f IN OI S
f fm
-


>
gn gm
- > =
=
: =




fin I 2 11 fs
-



>
- 7




227 fine) fig)
-
3 ~ =O 2
2 +- 7 = 21 7
fs
1 Els &
-

2x -




:
f is injective


Note : Much easier to establish sets have the same size than show there is a W



bijection num >
from = S


- n -
m = 0


>
- n = m




Definition : A set is countable iff its size is at most that of IN

A set is uncountable iff it is not countable
Proposition :
If the size of S is at least the size of IN , then S is infinite.

A set is countably infinite iff it is countable and infinite . Our notion of size , infinity makes sense




Why are these notions important for computer science ?

Set of programs in
your favorite language > Countable
Examples
Set of functions from IN to IN
>
Uncountable
Countable Uncountable
·
N . . Q ·
R ·
SF : IN <
Ny
·
Powerset of IN