# Countable sets

1. Nov 21, 2009

### 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?

2. Nov 21, 2009

### g_edgar

Well, when you give the definition that way, "denumerable" means your set is in one-to-one correspondence with the set $\mathbb{N}$ of natural numbers. So in that case your set is definitely not finite.

3. Nov 21, 2009

### ImAnEngineer

I don't think that answers my question. You've shown that a denumerable set is not finite, but I wanted to see the reverse; how a finite set can be not denumerable (if possible with an example of such a set).

Last edited: Nov 21, 2009
4. Nov 21, 2009

### slider142

Every finite set is denumerable, but not all denumerable sets are finite. The class of finite sets is properly contained within the class of denumerable sets.

5. Nov 21, 2009

### ImAnEngineer

That makes a lot of sense.

Maybe it's just a language issue. If I read something is either A or B, I interpret it as it being one or the other and never both (so A and not B, or B and not A). Apparently this is a misinterpretation... English is not my mother tongue.

6. Nov 21, 2009

### slider142

In mathematics (logic), 'or' without qualification is always "inclusive or". It means A or B or both. Exclusive or has to be explicitly said: "excluding both", or the use of xor. Read more here.

7. Nov 21, 2009

### ImAnEngineer

This brings me to a new question. I was wondering if this is a correct argument:
If S is finite, then |S|<|N|, so there exists a function f:N->S such that f is onto.

Is this argument correct? How can the implication f:N->S => f is onto be proven?

8. Nov 21, 2009

### slider142

By explicit construction. Ie., wrap N around S as if the elements of S were identified with points on the unit circle.

9. Nov 21, 2009

### ImAnEngineer

I know that 'or' in mathematics is always "inclusive or", however in this sentence it says "either...or".
http://en.wikipedia.org/wiki/Exclusive_disjunction

10. Nov 21, 2009

### ImAnEngineer

I don't think this is possible if the elements of S are unknown... correct?

11. Nov 21, 2009

### slider142

I haven't seen that use of either...or to denote exclusive or. In either case, you will have to decipher yourself whether the author of the text means exclusive or or not by searching for counterexamples. This will happen often if you keep reading mathematics/physics/engineering texts. ;)

12. Nov 21, 2009

### slider142

The actual elements of S are not relevant to f. Use the definition of countable to construct f. If that is the definition your book gives above, then use the definitions of "finite" and "denumerable".
Most likely these definitions will be similar to "There exists a bijective function g such that the image of S under g is a subset of N." Consider the function g as a "coordinate system" or "index" for S (it assigns a natural number to each element of S). Let $f = g^{-1} \circ h$ where h is now a function of your choice that deals with numbers.
For example, suppose you have an unknown set S such that |S| = 4. Let h(n) = n mod 4. Then f defined above is onto S.

Last edited: Nov 21, 2009
13. Nov 21, 2009

### ImAnEngineer

In that case I am not sure what you mean by wrapping N around S as if the elements of S were identified with points on the unit circle. Could you elaborate a little bit more?

14. Nov 21, 2009

### slider142

It was meant to be visual stimulus only, but it can be made symbolically explicit. Let |S| = n. Consider the regular n-gon inscribed in the unit circle. Label the vertices of this n-gon 1, ..., n. Wrap N around the unit circle by composing f(x) = (x mod n) + 1 with $$g(x) = \left(\cos\left(\frac{2\pi x}{n}\right), \sin\left(\frac{2\pi x}{n}\right)\right)$$ so we have $h:\mathbb{N}\rightarrow S^1:x \mapsto g(f(x))$. Let p be the bijection between S and the set {1, ..., n} in N, then let k be the map $k = p^{-1}\circ g^{-1} \circ g \circ f = p^{-1}\circ f$. k is the map being sought.
The previous argument is much better when drawn on a board as actually wrapping N around a unit circle instead of looking at the resultant symbolic function.

Last edited: Nov 21, 2009
15. Nov 21, 2009

### ImAnEngineer

I've thought about it for a while and I think I get your point. Though it is still not clear to me if/how you've proven that |S|<|N| implies that there exists a function f:S->N such that f is onto. But it's past midnight for me so my brain isn't fully functioning. I'll take another look at it tomorrow and then I'll probably post another reply.

Anyhow, thanks for your help so far!

PS: I see you just edited your post. It looks quite a bit clearer what you mean now.

16. Nov 21, 2009

### 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 $$f: \![\![1,n]\!]\!] \to A$$
where here $$\![\![1,n\!]\!] := \{1,2,...,n\}\subset \mathbb{N}.$$

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

Last edited: Nov 21, 2009
17. Nov 22, 2009

### ImAnEngineer

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)

18. Nov 22, 2009

### 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.

19. Nov 22, 2009

### tauon

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.

20. Nov 22, 2009

### tauon

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 $$\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 $$\aleph_0$$- contradiction)

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

If $$S=\{S_i | i \in I\}$$ is a collection of nonempty sets (indexed by a set $$I$$),
then there exists a function $$f_c$$ (sometimes called a "choice" function) $$f_c : S \rightarrow \bigcup_{i \in I} S_i$$
so that $$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.

Last edited: Nov 22, 2009