# I encountered a problem and was wondering if anyone can give me some

1. Dec 18, 2005

### feefoo

I encountered a problem and was wondering if anyone can give me some advice on figuring out this problem.

The problem states that P is a set of total functions from the set of positive integers to the set {0} and Q is the set of total and partial functions from the set of positive integers to the set {0}. Show that P is enumerable and Q is not.

Thanks in advance for any advice you can offer.

2. Dec 18, 2005

### mathwonk

i do not know what totalk and partial functions are, but it sounds like maybe partial functions are a way to describe all subsets of the positive integers. it is classical that the set of all subsets of a given set, has more elements than the set.

to see this try to define a surjection f from the set onto its collection of subsets. then produce a subset that is not in the image of the function as follows:

given each element x, put it in the subset if x does not belong to f(x). Then you have a collection A of elements that cannot have the form f(x) for any x, since x then could be neither in A nor not in A. i.e. if x were in A, then it would not belong to f(x), so f(x) cannot be A. But if x were not in A, and A = f(x), then x would belong to A.

so f is not surjective since it cannot take the value A.

this stuff is cute, but mostly parlor tricks. actually though it has a "use" making laypersons and students uncomfortable by proving the existence of varioius things we have difficulty to actually produce, like non algebraic numbers, and so on.

3. Dec 19, 2005

### AKG

What have you tried so far?

4. Dec 20, 2005

### matt grime

It would appear that total function means a genuine function on N and partial function means one defined on some subset of N. The statement is then equivlant to showing fun(N,pt) and fun(N,2pts) are countable and uncountable respectively. pt and 2pts mean some set with one point and 2 points in it respectively. The first is obviously finite, containing as it does one element and the second is just the power set of N.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook