Condition for Countability

CAF123

I seem to have a couple of contradictory statements of what a countable set is defined to be:
In my textbook I have:
'Let E be a set. E is said to be countable if and only if there exists a 1-1 function which takes ##\mathbb{N}## onto E.'

This implies to me that that there has to exist a beijection from ##\mathbb{N}## to E since they use 1-1 and onto in the defintion.

In my notes I have: E is said to be countable if there is a bijection ##f: \mathbb{N} \mapsto E##'

However, when I looked on Wikipedia, I read:
A set S is called countable if there exists an injective function f from S to the natural numbers N.

Is there a contradiction here and if so, what is the true defintion?

WannabeNewton

The true definition is: a set [itex]S[/itex] is countable if there exists an injection [itex]f:S\rightarrow \mathbb{N}[/itex]. Note it does NOT have to be a surjection as well, in general. IF [itex]f[/itex] also happens to be surjective then we say [itex]S[/itex] is countably infinite.

CAF123

That was a quick reply. What exactly does countably infinite mean?
If I understand correctly, then if a set is finite it is automatically countable. So an infinite set is countable provided there exists a bijection from N to E?

WannabeNewton

A set [itex]S[/itex] is countably infinite if there exists a bijection [itex]f:S\rightarrow \mathbb{N}[/itex]. If [itex]S[/itex] is not countable (i.e. neither countably infinite nor countably finite) then we say [itex]S[/itex] is uncountable. So, for example, [itex]\mathbb{Z},\mathbb{Q}[/itex] are countably infinite but [itex]\mathbb{R}[/itex] is uncountable (the proof of this is one of the most beautiful proofs in mathematics and was shown by Cantor using the extremely elegant diagonal argument).

CAF123

I have in my notes that '....bijection from N to S'. But you have bijection from S to N. I suppose it won't matter here. But for an injection N to S, is an injection S to N the same thing. (it seems so, but I just want to clarify).

WannabeNewton

No it doesn't mean the same thing. There exists an injection [itex]f:\left \{ 1,2 \right \}\rightarrow \mathbb{N}[/itex] (it is just the inclusion map). Does that imply there exists an injection [itex]f:\mathbb{N}\rightarrow \left \{ 1,2 \right \}[/itex]? It doesn't of course!

Bacle2

Just to add that the Cantor-Schroder-Bernstein says that if there are injections between N and S and between S and N , then there is a bijection between N and S .

WannabeNewton

A fun and short exercise is to show, using the well ordering theorem, that there exists an uncountable well - ordered set [itex]Y[/itex] such that [itex]\forall x\in Y[/itex], there exist only countably many [itex]y\in Y[/itex] such that [itex]y < x[/itex]. It's a pretty awesome result considering we are talking about an uncountable, totally ordered set!

micromass

Different authors tend to use different terminology. Some authors use countable to denote that there is a bijection to the natural numbers. In their terminology, finite sets are not countable. Other authors (the majority, I guess), allow finite sets to be countable.

CAF123

For sets that are finite and said to be countable does that mean there always exists an injection from S to N?

In your example, an injection could be ##1 \mapsto 1## and ##2\mapsto 2##?

Or if we take a set {1} then the injection could be ##1 \mapsto a##, ##a \in \mathbb{N}##.

WannabeNewton

Yes to all your questions.