Talk:Countable set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated C-class, High-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
High Importance
 Field: Foundations, logic, and set theory
WikiProject Citizendium Porting (Last updated: Never)
WikiProject icon This article is within the scope of WikiProject Citizendium Porting, a collaborative effort to improve Wikipedia articles by working in any useful content from their Citizendium counterparts. If you would like to participate, you can visit the project page, where you can join the project and see a list of open tasks.
Note icon
This article is out of date with its Citizendium counterpart and needs to be updated.
Current with its Citizendium counterpart article as of: Never


Countable rationals[edit]

There are lesser-known sequences for counting the rationals other than Cantor's mapping. For example, the following sequence assigns each natural to a unique positive rational:

S(0) = 0
S(1) = 1
S(2n) = S(n) + 1 for all n > 0
S(2n+1) = 1/S(2n) for all n > 0

This sequence is based on Farey sequences and Stern-Brocot trees. It can be extended to cover the negative rationals as well. — Loadmaster (talk) 17:40, 3 February 2008 (UTC)

Cantor: A Mathematical Charlatan[edit]

Consider the set of natural numbers listed in the usual order. That is, starting with 1,2,3... and written from left to right. By Cantorian definition, this set is both "countable" and infinite. Therefore we should be able to place the elements of this set in 1 to 1 correspondence with the set of natural numbers listed in any other order. Let us choose to use 'reverse order' for this second set. Now suppose we place the first set above the second and try to match elements. Then we should find one and only one entry under the number "1" in the first set. What is this number? Clearly, there is no such number! The concept of "countably infinite sets" is inherently flawed. This concept is the basis of the pseudo-mathematics of Cantor and his followers.

What can be counted can not possibly be infinite, and what is infinite can not be counted. Carl Friedrich Gauss pointed this out when he wrote "I protest against the use of infinite magnitude as something completed, which is never permissible in mathematics". The flaw in the 'diagonal argument' has precisely this defect. —Preceding unsigned comment added by (talk) 22:16, 23 May 2008 (UTC)

Sets do not distinguish order. The set of the natural numbers in any other order is the exact same thing as the set of the natural numbers in their usual order. Therefore the bijection is trivial. (talk) 11:08, 28 May 2008 (UTC)
It doesn't matter whether there is any way of arranging the elements so that they do not form a correspondence. All that matters is that there exists even one way or more to arrange them so that there is a one-to-one correspondence between the sets. And for the infinite sets there are infinitely many different ways of arranging the elements so that they correspond.
"What is infinite cannot be counted" -- not so either. Countably infinite is defined as having a bijection to the set of natural numbers. —Preceding unsigned comment added by (talk) 15:19, 2 September 2008 (UTC)
This sounds like Weyl's position which I was just reading about. I personally am very curious whether Weyl changed his mind and why he said he changed it. Either here or in his bio would be a good place (talk) 20:15, 2 July 2009 (UTC)
What sounds like Weyl's opinion, exactly? — Carl (CBM · talk) 20:33, 2 July 2009 (UTC)

Why drag topology into this article?[edit]

The new section Countable set#Topological proof of the uncountability of the real numbers seem to be out of place in this article. It is about topology, not really about countable sets. Also, from my limited knowledge of topology, the proof appears to be incorrect. Specifically, in the indiscrete topology one-point sets are not open. JRSpriggs (talk) 17:16, 13 June 2008 (UTC)

Not disagreeing, but the indiscrete topology doesn't satisfy the hypotheses because it is non-Hausdorff. (It is in fact mentioned as a counterexample in the indicated section.) siℓℓy rabbit (talk) 17:21, 13 June 2008 (UTC)

It can make sense to include a short proof that any topological space satisfying certain simple conditions must be uncountable and perhaps that the reals do satisfy those conditions. That the reals are uncountable can be proved more simply from the fact that they are linearly ordered such that between any two points there is another and they satisfy the least-upper-bound property (you certainly DON'T need to talk about decimals, even though that's one way to do it). Michael Hardy (talk) 17:29, 13 June 2008 (UTC)

Some details missing about bijection from Q to N[edit]

How does the proof of the assertion 'Q (the set of all rational numbers) is countable' contradict the intuition that 'the cardinality of Q is larger than that of N'? Either some details are left out or it doesn't.

(0,1,0), (1,1,0), (1,1,1) and so on are not members of N. They are rather triples composed of members of N. Is there assumed another bijection from these tuples to N? If this bijection exists and is assumed, it may be useful to explicitly state it. Johanatan (talk) 23:55, 20 October 2008 (UTC)

Since the article begins by defining a countable set to be one with an injection from it to N, why are people bending over backwards to created bijections when it is much simpler to create injections? For example the nonnegative rationals m/n are obviously a subset of N2, namely those pairs (m,n) for which n is nonzero and m and n are relatively prime (gcd is 1). And there are lots of very simple injections of N2 into N, for example f(m,n) = 2m3n, that don't require a diagram to explain. --Vaughan Pratt (talk) 15:55, 17 August 2009 (UTC)

Wikipedia is not a math textbook[edit]

I am concerned about some recent edits that make use of the "proposition - proof" style of math textbooks. I feel these style elements reduce the accessibility of the article to the layman as they destroy the flow of the text and make heavy use of (standard) math notation. (They also are partially redundant to the section More formal introduction.) I would suggest to at least move the text after the section Gentle introduction and, preferably, to reword it into more accessible prose. —Tobias Bergemann (talk) 11:29, 11 February 2009 (UTC)

I am responsible for the recent additions, but not for the definition (which is in my opinion the correct one). Also the terms injective, surjective, bijective have been around for some time, as has the f: A \to B notation for a function. I have only edited the section called Definition and Basic Properties. The label THEOREM is used many places in the article. I believe the intent (and certainly my intent) was to indicate a precise mathematically correct statement. Mathematics is proofs. It may be valuable in a wikipedia article to give heuristic arguments or give examples. But when a proof is given it I think it is useful for the reader to know "This is a proof, not an example and not a heuristic argument." That is the function of the labels Proof. The proofs given are all extremely short, though, in principle I see no reason not to include longer proofs. Increasingly Wikipedia is becoming a useful place for students to learn serious mathematics, as opposed to popularized versions (which are also very valuable). Indeed many mathematics articles discuss topics at a level not usually encountered until graduate school. This is a 'good thing.'

Achieving a balance between something for the layman (to use your phrase) and something useful for, say, a university level student, is very difficult and has not been achieved in this article. For example the section on the minimal model for set theory is inaccessible even to most professional mathematicians.

While Wikipedia is not a textbook I think it is very useful to have textbook like sections on particular topics like this one. I believe it enhances other entries. If you look, for example, at measure theory which is more highly rated than this article you might imagine that someone reading that would want to refer to an article on countable which had a quick summary of basic properties. I am open to moving the section later if others think that is appropriate. Johnfranks (talk) 16:00, 11 February 2009 (UTC)

I moved the main content of the section "Definition and basic properties" later in the article. I combined the short section "Other results about uncountable sets" with it. I added references at the beginning. Johnfranks (talk) 20:01, 11 February 2009 (UTC)

Thanks, I think these changes really helped to improve the flow of the article. I guess I basically agree with everything you write above, though I would argue that PlanetMath or MathWorld are better places for students to learn serious mathematics.
I don't object to the content so much as to the presentation. My gripe with what I was calling above the "proposition - proof" style is that if used badly the presentation of the subject decays into a sequence of theorems/propositions/corollaries/lemmata without motivation of the proposed statements.
If you haven't already done so, may I suggest you have a look at Wikipedia:Manual of Style (mathematics)? —Tobias Bergemann (talk) 08:40, 12 February 2009 (UTC)
I'm glad to hear you like the new changes. I absolutely agree with your (Tobias's) remarks, but when I looked over the article to fix it, I found myself spending more time doing WP:MOS and WP:MSM fixes in the other sections. Especially with the new content in its current place, the article flows very nicely. I do wish there was more prose and less uninterrupted prop-proof chains, but I don't see how to achieve that without degrading the article. I do worry that future editors may continue the prop-proof chains until the article is the type of mess Tobias and I imagine/have seen, but for now it seems quite good. JackSchmidt (talk) 14:37, 12 February 2009 (UTC)

Is zero a natural number?[edit]

Is there a consensus that zero is a natural number? If so I am happy to go along. I have never seen this usage. Can someone give a reference? The recent edit declaring 0 a natural number broke one statement which assumed one could divide by a natural number. I think I have fixed it. I believe there is another place in this article (in a section I have not edited) that asserts that 0 is not in the natural numbers. Johnfranks (talk) 22:35, 11 February 2009 (UTC)

This is a standard convention that differs in various fields of mathematics. See natural number. Presumably this article is set theoretic, so set theory conventions apply. See ordinal number and von Neumann ordinals for the reason for the convention. JackSchmidt (talk) 22:51, 11 February 2009 (UTC)
OK. I edited the other section which declared natural numbers to start with 1.Johnfranks (talk) 23:50, 11 February 2009 (UTC)
Excellent, thanks for keeping/making-for-the-first-time the article consistent. I usually see 0 as not in the set of natural numbers myself, but while looking for an algebra reference I noticed that Jacobson's Basic Algebra I, section 0.4 (The natural numbers), p15, ISBN 0716704536, defines 0 as a natural number without comment. It looks just like standard Peano arithmetic (successor function), but instead of "1 is not a successor" it has "0 is not a successor". Actually on wikipedia, apparently 0 is the first guy in Peano arithmetic too. At any rate, you asked for a reliable source type of reference as much as whether there was consensus, so I figured it would be nice to provide both. JackSchmidt (talk) 05:03, 12 February 2009 (UTC)
Interesting. I have Jacobson's Lectures in Abstract Algebra I: Basic Concepts which asserts in section 0.4 that the natural numbers are 1,2,... He also says in that section that "As usual, we denote the unique non-successor as 1." Of course he also writes all his functions on the right indicating a strong willingness to buck convention.Johnfranks (talk) 14:56, 12 February 2009 (UTC)
Since it is clear that the smallest cardinal number is zero and the smallest ordinal number is zero, there is a definite advantage in defining the natural numbers to include zero. That way, the natural numbers are just the finite cardinals and also the finite ordinals. JRSpriggs (talk) 05:54, 13 February 2009 (UTC)
There are many issues (including this one) that I would argue should not be done as they currently are if we were starting over in creating mathematical language. Your argument addresses the way things should be done, not the way they are, i.e. not what current conventional usage is. This topic is discussed fairly extensively in two parts of Talk:Natural_number. While I believe the overwhelmingly dominant usage in mathematics written in English is to start the natural numbers with 1, I was surprised to learn this is apparently not true in French. There is even the suggestion that positif can mean non-negative. I certainly defer to others for usage in set theory and computer science.
Johnfranks (talk) 21:46, 14 February 2009 (UTC)
There is a discussion of some of these problems and more in the introduction to MR 2312337 Cohen, Henri. "Number theory. Vol. I. Tools and Diophantine equations." Graduate Texts in Mathematics, 239. Springer, New York, 2007. ISBN 978-0-387-49922-2. As a French number theorist, the problem that "N is the set of positive integers" defines unequivocally two different sets depending on whether the person he is talking to was trained in the French schools, has bugged him to the point of spending a few pages on it. JackSchmidt (talk) 23:46, 14 February 2009 (UTC)
Can you give me a section or page number, please? Or do you mean the short paragraph under "Warning"? Hans Adler 17:23, 17 August 2009 (UTC)


I am removing this from the lede:

But countability has little to do with combinatorics (the mathematical study of counting). Rather, it is a property of certain sets in the mathematical area of set theory.

Of course infinite countable sets have little to do with finite combinatorics, but that is because they are infinite, not because of countability. On the other hand countability is an important concern in infinitary combinatorics, and so it seems wrong to me to say that countability has little to do with combinatorics overall. For example, Martin's axiom uses countability in an central way. — Carl (CBM · talk) 11:04, 28 October 2009 (UTC)

Under 'More Formal Introduction'[edit]

This sections discusses how the set N and 2N have the same cardinality. Not bad so far. However, in the paragraph just below the line "1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ...." it suggests that "(t)his gives an example of a set which is of the same size as one of its proper subsets". Not quite. If 2N were strictly a subset of N, it would be skipping every other number/element in the set, so would DEFINITELY NOT be the exact same size -- it would be exactly half the size! Infinity math or not, if it doesn't include all of the same elements it cannot be both a subset and equal in size. It's only when considering 2N as a strictly independent set that it would have the same cardinality. KhyranLeander (talk) 21:24, 19 August 2010 (UTC)

The cardinality of a set doesn't change, whether you are considering it as the subset of some other set, or not. So the set N = {1, 2, 3, ...} and the set 2N = {2, 4, 6, ...} have the same cardinality, by definition, since the function f(x) = 2x, is a one-to-one correspondence between the two sets. And this is so despite the fact that one set is a prober subset of the other. That's one of the properties of the cardinality of infinite sets that set them apart from finite sets, where the cardinality of a proper subset is always strictly smaller. Since the "size" of N is infinite, in order for your statement that 2N is "exactly half the size" of N, to have any meaning, the notion of "half of infinity" needs to be defined. It turns out this can be done, in a reasonable way, and under the usual definitions, half of infinity equals infinity. In which case both the statements "2N and N have the same size", and "2N is half the size of N" are true. Paul August 22:32, 19 August 2010 (UTC)

An analogy in the introduction?[edit]

How about adding a short analogy to the introduction. Such as a countable set being a set of temperature readings, that may go on for ever but every individual reading is clearly spaced. Where as an uncountable set you can mine more and more numbers simply by increasing the resolution, like the level of detail if you're zooming in on fractal, or dividing 1 by x with x>1. You will allways end up with a number, regardless of what you put in unless the number is infenite in size, so there is really no end to how small 1/x can get. (Axioms that suppose a largest uncountable non infenite number aside) —Preceding unsigned comment added by (talk) 09:33, 29 October 2010 (UTC)

We usually try to avoid analogies in mathematics since they can easily be misunderstood. If you have a precise example, that could be added at the appropriate place in the article, i.e. further down rather than in the lead. JRSpriggs (talk) 10:59, 29 October 2010 (UTC)


In many textbooks, it is said that a set is countable if we can list the elements as a_1, a_2, \dots. My question is: is it true that a set is countable if and only if there exists a Turing machine to enumerate (without termination) all the elements in the set? — Preceding unsigned comment added by Tmbu (talkcontribs) 01:56, 9 March 2011 (UTC)

No, you're confused. The elements of a countable set may themselves be extremely large infinite sets. There's no way that a Turing machine can enumerate such things. — Carl (CBM · talk) 02:02, 9 March 2011 (UTC)
A set which can be enumerated by a Turing machine is a recursively enumerable set. All such set are countable. However, there are many countable sets which are not recursively enumerable, even among subset of the natural numbers. For example, the set of Gödel numbers of true sentences of arithmetic is countable, but not recursively enumerable.
You should not take those textbooks too literally. They are just trying to give you an intuitive feel for what a countable set is. The listing of the elements need not be something that real humans or real machines can do. It is sufficient that there be (in principle) a formula of set theory with parameters (arbitrary sets, possibly undefinable) which associates a distinct natural number with each element of the set in question. JRSpriggs (talk) 05:01, 9 March 2011 (UTC)

Definition wrong?[edit]

Under definition it states : "If f is also surjective and therefore bijective, then S is called countably infinite." A function being surjective does NOT imply it is bijective, however the reverse is true. For instance if a function is bijective it is also therefore surjective. But a surjective function is not always bijective, in the case when more than one element of the first set maps to the same element of the second set. — Preceding unsigned comment added by (talk) 14:22, 2 February 2012 (UTC)

The function f is defined to be injective. So it is surjective if and only if it is bijective. --Zundark (talk) 14:52, 2 February 2012 (UTC)
Thanks for the clarification. I am going to go ahead and specify the reason why it is bijective in paranthesis next to it to avoid confusion. (talk) 02:13, 3 February 2012 (UTC)