Countable sets

**ImAnEngineer** · Nov22-09, 06:37 AM

Originally Posted by blkqi

Actually, you can define a finite set in the following way:

A set A is finite iff there exists a natural number n and bijection $LaTeX Code: f: \\![\\![1,n]\\!]\\!] \\to A$
where here $LaTeX Code: \\![\\![1,n\\!]\\!] := \\{1,2,...,n\\}\\subset \\mathbb{N}.$

So your implication that such a surjection exists is certainly correct.

Ah thanks that helps a lot.

Again a new question comes to mind. Is the following a true statement?
If |S|<|N|, then S is finite or denumerable.

(I'm quite sure it is, but I don't know how to argue why)

**ImAnEngineer** · Nov22-09, 08:14 AM

I think the answer to my previous question is probably quite complicated.

On wikipedia I found:

Finite, countable and uncountable sets

If the axiom of choice holds, the law of trichotomy holds for cardinality. Thus we can make the following definitions:

* Any set X with cardinality less than that of the natural numbers, or | X | < | N |, is said to be a finite set.

So apparently it follows from the axiom of choice and the law of trichotomy, and I'm not familiar with either of them, so I'll sort that out first.

**tauon** · Nov22-09, 08:47 AM

Originally Posted by ImAnEngineer

A set S is countable if it is either finite or denumerable. What I don't understand is why S can be finite but not denumerable. Could anyone give an example?

a set is countable if there exists a bijection between that set and a subset of N (or an equivalent definition: a set is countable if there is an injective function from that set to N).

a set is denumerable if it is countably infinite, or to be more precise if there is a bijection between that set and N. examples of denumerable sets: N, Q, Z...

a finite set can't be denumerable because it is not countably infinite: there is no bijection between a finite set and the whole N.
but all in all it's just a matter of definitions. I've seen some textbooks where a countable set is defined as a set with the same cardinality as N, and finite sets defined as at most countable or something similar.

**tauon** · Nov22-09, 09:13 AM

Originally Posted by ImAnEngineer

I think the answer to my previous question is probably quite complicated.

On wikipedia I found:

So apparently it follows from the axiom of choice and the law of trichotomy, and I'm not familiar with either of them, so I'll sort that out first.

the law of "trichotomy" is equivalent with the axiom of choice (in ZFC at least) so there is a redundancy there- the axiom of choice will suffice.
also the axiom of choice is equivalent (albeit, weaker than) the theorem of well-ordering -meaning that you can use the AC or well-ordering theorem together with the axioms of ZF to prove the well-ordering theorem or AC respectively- , so if the axiom of choice holds that means that cardinal numbers are well-ordered, thus also that there is a "smallest" infinite cardinal (which can be easily argumented to be $LaTeX Code: \\aleph_0$ )

if all these conditions are assumed than if |S|<|N| it immediately follows that S is finite (because if we assume the contrary, then that would mean there is an infinite cardinal smaller than $LaTeX Code: \\aleph_0$ - contradiction)

as for what the axiom of choice is, one version/formulation of the axiom of choice is:

If $LaTeX Code: S=\\{S_i | i \\in I\\}$ is a collection of nonempty sets (indexed by a set

),
then there exists a function

(sometimes called a "choice" function) $LaTeX Code: f_c : S \\rightarrow \\bigcup_{i \\in I} S_i$
so that $LaTeX Code: f_c{(S_i)} \\in S_i$

which means that you can always pick at least one element from each set of a collection of nonempty sets.

**ImAnEngineer** · Nov22-09, 09:26 AM

That was really enlightening Tauon! I get it now :) ! Thanks a lot!