Countability of Set S: Finite vs Denumerable

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

 

[g_edgar]

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

 

[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).

 

[slider142]

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

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.

 

[ImAnEngineer]

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.

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.

 

[slider142]

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.

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.

 

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

 

[slider142]

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?

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

 

[ImAnEngineer]

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.

I know that 'or' in mathematics is always "inclusive or", however in this sentence it says "either...or".

The Oxford English Dictionary explains “either … or” as follows:

The primary function of either, etc., is to emphasize the indifference of the two (or more) things or courses … but a secondary function is to emphasize the mutual exclusiveness, = either of the two, but not both.

http://en.wikipedia.org/wiki/Exclusive_disjunction

 

[ImAnEngineer]

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

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

 

[slider142]

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

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. ;)

 

[slider142]

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

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 [itex]f = g^{-1} \circ h[/itex] 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.

 

[ImAnEngineer]

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

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

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?

 

[slider142]

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?

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 [tex]g(x) = \left(\cos\left(\frac{2\pi x}{n}\right), \sin\left(\frac{2\pi x}{n}\right)\right)[/tex] so we have [itex]h:\mathbb{N}\rightarrow S^1:x \mapsto g(f(x))[/itex]. Let p be the bijection between S and the set {1, ..., n} in N, then let k be the map [itex]k = p^{-1}\circ g^{-1} \circ g \circ f = p^{-1}\circ f[/itex]. 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.

 

[ImAnEngineer]

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 [tex]g(x) = \left(\cos\left(\frac{2\pi x}{n}\right), \sin\left(\frac{2\pi x}{n}\right)\right)[/tex] so we have [itex]h:\mathbb{N}\rightarrow S^1:x \mapsto g(f(x))[/itex]. Let p be the bijection between S and the set {1, ..., n} in N, then let k be the map [itex]k = p^{-1}\circ g^{-1} \circ g \circ f = p^{-1}\circ f[/itex]. 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.

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.

 

[blkqi]

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?

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

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

 

[ImAnEngineer]

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

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]

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]

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]

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 [tex]\aleph_0[/tex])

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 [tex]\aleph_0[/tex]- contradiction)

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

If [tex]S=\{S_i | i \in I\}[/tex] is a collection of nonempty sets (indexed by a set [tex]I[/tex]),
then there exists a function [tex]f_c[/tex] (sometimes called a "choice" function) [tex]f_c : S \rightarrow \bigcup_{i \in I} S_i[/tex]
so that [tex]f_c{(S_i)} \in S_i[/tex]

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

 

[ImAnEngineer]

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