Representation

Question 1

For finite sets S, T
The following statements are equivalent:
1. |S| less than or equal to |T|
2. There exists one-to-one f : S --> T
3. There exists onto g : T --> S

True or False: 1 implies that there’s a one to one function between S and T

Answer 1

1 => 2
2 => 3
3 => 1

Doesn’t mean there’s a single function that makes it one to one!

Question 2

Proof: For finite sets S,T:

|S| less than or equal to |T| => There exists one-to-one f : S –> T

Answer 2

Define f st. f(s_i) = t_i. Done! One-to-one because every input s in S is connected to at most one t in T.

Question 3

Proof: For finite sets S, T:

There exists one-to-one f : S –> T => There exists onto g : T –> S

Answer 3

Define g(t) = s s.t. f(s) = t; if some t are not connected to s (i.e. f(s) doesn’t exist), set g(t) = s_0. Done! Onto because every output t in T is connected to S.

Question 4

Proof: There exists onto g : T –> S => |S| less than or equal to |T|

Answer 4

|S| equal to |T| in the strictest definition of onto
|S| less than |T| since T can have many elements not accounted for by the definition of onto
|S| not greater than |T| because a function input (t in T) can’t have more than one output (s in S)

Question 5

What is a digital representation? What properties does a representation have?

Answer 5

A digital representation R uses discrete symbols to capture a set of objects O. A representation has:

1. 1-to-1 encoding function E: O –> R
2. onto decoding function D: R –> O
3. for all o in O, D(E(o)) = o

Question 6

How do I represent lists? What about lists of lists?

Answer 6

Lists can be represented by the 3-letter alphabet {0, 1, ,}, encoded by {0, 1}^2

Lists of lists can be represented by the 5-letter alphabet {0, 1, {, }, ,}, encoded by {0, 1}^3

Question 7

How do we represent all possible natural numbers?

Answer 7

infinite set of finite strings

Question 8

How do we represent all possible functions that take natural numbers to [0,1]?

Answer 8

infinite set of infinite strings