Help me out with proof for countable

[happybear]

Homework Statement

If S is a set of function from {2,5} to a set of natural numbers, show S is countable?

The question also ask what if S is from a set of natural number to {2,5}, is that countable

Homework Equations

The Attempt at a Solution

I try to do it like this. Suppose E={2,5}, F be the set of natural numbers. suppose there are n natural numbers there. then
f(2)={n elements}. f(5) = elements, so there are n^2 elements of the function. So S is countable? It that right that I just assume there are n elements in the natural set?

 

[slider142]

It's not really necessary to know the number of elements of each function, just the number of functions. It is also not apparent that the subset of natural numbers is finite. The defining property of a function is that each element of the domain is mapped to exactly one element of the range. Thus, we can count how many ways there are to associate the 2 numbers in the domain to elements of the codomain in ordered pairs (f(2), a), (f(2), b) and so on. Since this is just a relabeling of the existing elements, the cardinality of the set remains unchanged. The same can be done to construct a countable set for f(5). You can then use the theorem that the union of a finite amount of countable sets is countable, or prove it if you haven't already done so (not very difficult).

 

[Dick]

It's not really necessary to know the number of elements of each function, just the number of functions. It is also not apparent that the subset of natural numbers is finite. The defining property of a function is that each element of the domain is mapped to exactly one element of the range. Thus, we can count how many ways there are to associate the 2 numbers in the domain to elements of the codomain in ordered pairs (f(2), a), (f(2), b) and so on. Since this is just a relabeling of the existing elements, the cardinality of the set remains unchanged. The same can be done to construct a countable set for f(5). You can then use the theorem that the union of a finite amount of countable sets is countable, or prove it if you haven't already done so (not very difficult).

That's pretty confusing. The function is defined by the value of the ordered pair (f(2),f(5)). The the cardinality of that is (similar to what the OP said) the cardinality of the cartesian product (not the union) NxN, where N is the integers. Have you shown NxN is countable?

 

[HallsofIvy]

f(2) can be any natural number. f(3) can be any natural number. Since the domain consists only of 2 and 3, there is a natural correspondence between the set of such functions and the set of ordered pairs of natural numbers: f-> (f(2), f(3)). Do you know the proof that N x N is countable?

 

[happybear]

How about the mapping f:N->{2,5}. Is this countable?

 

[Dick]

Yes. Prove that it can be mapped to NxN. That's what people have been trying to point out to you.

 

[happybear]

I get it now.Thanx so much