Homework Help: Countable sets | If k:A->N is 1-to-1, then A is

1. Sep 14, 2010

michonamona

Countable sets | If k:A-->N is 1-to-1, then A is...

1. The problem statement, all variables and given/known data
Suppose we found a 1-to-1 function k that maps the set A to the set N, where N is the set of natural numbers. What can we say about the set A?

2. Relevant equations

3. The attempt at a solution

The answer is 'A is at most countable.' I understand this. But my question is, is it also possible for A to be finite, as well as infinite? i.e. its possible for A to be either

{a1, a2, a3}

or

{a1, a2, a3, a4, a5,...}

all the way to infinity.

Thanks,

M

2. Sep 14, 2010

Dick

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

Depends on what you mean by '1-to-1'. k(a1)=1, k(a2)=2 and k(a3)=3 is a 1-to-1 (if you mean injective) map from {a1,a2,a3}->N. But it's not onto (surjective). If you take '1-to-1' to be bijective, then sure, A is countably infinite.

3. Sep 14, 2010

michonamona

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

k is injective and that's all we know. I just want to know if its possible, given that k is injective, for A to be finite or infinite, not whether if it actually is.

4. Sep 14, 2010

Dick

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

I already gave you an example where k is injective and A is finite. You give me an example where it's infinite.

5. Sep 14, 2010

michonamona

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

Ok, suppose k is injective.

k(a1)=1, k(a2)=2, k(a3)=3, k(a4)=4, k(a5)=5, k(a6)=6,..., k(am)=m, k(a(m+1))=m+1,...

So k is a mapping from {a1, a2, a3, a4, a5, a6,..., am, a(m+1),...} --->N.

So thus, A is allowed to be a countably infinite set.

All right, now whats wrong with my argument?

6. Sep 14, 2010

Dick

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

Why do you think there is anything wrong with it? The solution said 'A is at most countable'. So yes, A can be either finite or countably infinite. Isn't that what 'at most countable' means? What's the question again?

7. Sep 14, 2010

michonamona

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

Thank you for your help, I really appreciate it.

All right then, I was just confused by the phrase "at most countable." It would have been clearer for me if they said "A is, at the very least, countable" but we don't know whether it's finite or infinite.

My question was whether its possible for A to be finite or infinite given that k is an injection from A to N.

8. Sep 14, 2010

Dick

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

Ok, then we agree. A is either finite or countably infinite. "at most countable" means the same thing as "A is, at the very least, countable". You knew the answer from the beginning, it was just the phrasing.

9. Sep 14, 2010

michonamona

Re: Countable sets | If k:A-->N is 1-to-1, then A is...

Awesome, thanks man!