What is the true definition of countable sets?

[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 $S$ is countable if there exists an injection $f:S\rightarrow \mathbb{N}$. Note it does NOT have to be a surjection as well, in general. IF $f$ also happens to be surjective then we say $S$ 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 $S$ is countably infinite if there exists a bijection $f:S\rightarrow \mathbb{N}$. If $S$ is not countable (i.e. neither countably infinite nor countably finite) then we say $S$ is uncountable. So, for example, $\mathbb{Z},\mathbb{Q}$ are countably infinite but $\mathbb{R}$ 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]

A set $S$ is countably infinite if there exists a bijection $f:S\rightarrow \mathbb{N}$. If $S$ is not countable (i.e. neither countably infinite nor countably finite) then we say $S$ is uncountable. So, for example, $\mathbb{Z},\mathbb{Q}$ are countably infinite but $\mathbb{R}$ 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).

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 $f:\left \{ 1,2 \right \}\rightarrow \mathbb{N}$ (it is just the inclusion map). Does that imply there exists an injection $f:\mathbb{N}\rightarrow \left \{ 1,2 \right \}$? 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 $Y$ such that $\forall x\in Y$, there exist only countably many $y\in Y$ such that $y < x$. 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.