Getting confused on the cardinality of infinite sets?

Okay 2 questions to help clear some things up for me.

To show a set A has cardinality equal to the cardinaility of the natural numbers do we need to establish an injection A--->N or an injection N--->A or a bijection A---->N or bijection N---->A? I've seen different notes using different methods so I'm getting confused. Part of me seems to think there is some kind of equivalence between these when we are dealing with infinite sets but I would like some clarity.

secondly I'm on this question and I don't know what it means really:

deduce that the set of all functions f:{0,1}----->N is countably infinite.

Surely it's got to be a bijection $A \rightarrow \mathbb{N}$?

There's an injection from $\{1,2,3\} \rightarrow \mathbb{N}$ but the sets don't have the same cardinality and there's an injection from $\mathbb{N} \rightarrow \mathbb{R}$ and a similar comment applies.



I guess you can consider the set of all possible co-domains of f. For each co-domain C, $C \in \mathbb{N} \times \mathbb{N}$.

Okay thanks I guess that clears it up somewhat for me. Can I just ask why DFranklin said this yesterday "For many of these questions, the "quick way" is to show there's an injection into N; this immediately establishes countability (and that N x N is infinite is obvious)."

I have no idea. As it stands the statement seems to make no sense. What was the context?

Okay thanks I guess that clears it up somewhat for me. Can I just ask why DFranklin said this yesterday "For many of these questions, the "quick way" is to show there's an injection into N; this immediately establishes countability (and that N x N is infinite is obvious)."

Is this because there would be a bijection iff there is an injection show showing that there is an injection is sufficient?

Countability is defined is one of two ways: people either say a set is countable if it has the same cardinality as the naturals (so this definition requires that we exhibit a bijection from our set to the naturals), or if it is 'no bigger' than the naturals (so this requires an injection from our set to the naturals).

So DFranklin obviously uses the second definition. I would too - after all, we can count finite sets, so it would be better if the word countable takes these into account.

Got it thanks!!!!

I kept seeing these differing definitions popping up and I never really had that explained so cheers.

Question: if there is an injection from NxN--->N would there also be a bijection because eventually all n in N would be mapped to by some element of NxN?

What about the other way? (Does an injection N---->NxN also mean a bijection by the same reasoning.)

Well, there must be a bijection between NxN and N, but not for the reason you have given. See http://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem

Well, there must be a bijection between NxN and N, but not for the reason you have given. See http://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem

Countability is defined is one of two ways: people either say a set is countable if it has the same cardinality as the naturals (so this definition requires that we exhibit a bijection from our set to the naturals), or if it is 'no bigger' than the naturals (so this requires an injection from our set to the naturals).

Isn't this back to front?

Surely to show that $A$ has the same cardinality as $\mathbb{N}$, we'd need to show that $\mathbb{N}$ is "no bigger" than $A$ i.e. we need an injection *from* $\mathbb{N}$ *to* $A$.

As I pointed out above, there's an injection from $\{1,2,3\}$ to $\mathbb{N}$, but they don't have the same cardinality.

No.
We're talking about countability.

BTW, as a matter of definition, do you distinguish between "a countable set" and "a countably infinite set"; would you consider a finite set to be "countably infinite" or merely "countable"? To me, those are different things.