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

[michonamona]

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

Homework Statement

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?

Homework Equations

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

 

[Dick]

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.

 

[michonamona]

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.

 

[Dick]

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.

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

 

[michonamona]

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 what's wrong with my argument?

 

[Dick]

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 what's wrong with my argument?

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?

 

[michonamona]

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.

 

[Dick]

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.

 

[michonamona]

Awesome, thanks man!