Talk:Countable set

Archives:

• Talk:Countable set/Archive 1

Countable rationals

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) = ¹/_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

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 66.67.96.142 (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. 195.197.240.134 (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 41.241.23.249 (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 4.249.3.202 (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?

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

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 N², 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 N² into N, for example f(m,n) = 2^m3ⁿ, that don't require a diagram to explain. --Vaughan Pratt (talk) 15:55, 17 August 2009 (UTC)

Wikipedia is not a math textbook

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?

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

Combinatorics

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'

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?

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 194.132.104.253 (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)

Question

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 (talk • contribs) 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?

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 24.63.136.210 (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. 24.63.136.210 (talk) 02:13, 3 February 2012 (UTC)

Nevertheless, the given definition is wrong (If THIS f is also surjective...). You don't suppose the function f which showed you that S is countable to be surjective in case S is countably infinite. Example: f(n):=n+1 as function from N to N is injective. So this shows us N is countable. But f is not surjective. So N is not countably infinite? To correct the definition you have to find a new function which is bijective (in case f is only injective but not surjective). --Jobu0101 (talk) 20:37, 9 December 2014 (UTC)

1) What's with the Jainist thing in history? It would be cool if that were accurate, but I'm doubtful given some of the dates and the complete lack on non-Jainist material. 2) What's with all the "citation needed"'s on the Jainist material. It is plenty well cited, much more thoroughly cited than the rest of the article to say the least. If you wish to *dispute* the citations, which seems reasonable, do that clearly, don't just paste 'citation needed' on all of the clearly cited material. Also, text citations that aren't available online are valid citations, if that's what's drawing your ire. 73.170.107.159 (talk) 06:45, 15 April 2015 (UTC)

I guess most the the 'citation needed' originate from me. I gave a detailled reason for each of it. If it doesn't appear when you move the mouse pointer over it, you can see it in the source code. - Jochen Burghardt (talk) 07:50, 15 April 2015 (UTC)

Definition of mapping is not precise

Q can be defined as the set of all fractions a/b where a and b are integers and b > 0. This can be mapped onto the subset of ordered triples of natural numbers (a, b, c) such that a ≥ 0, b > 0, a and b are coprime, and c ∈ {0, 1} such that c = 0 if a/b ≥ 0 and c = 1 otherwise.

If a ≥ 0 and b > 0 then by definition a/b ≥ 0. — Preceding unsigned comment added by 24.84.237.14 (talk) 03:48, 9 September 2015 (UTC)

Perhaps more varied examples would be needed. For instance, the rational number -4/2 would be mapped to the triple (2, 1, 1) as would all rational numbers that are equivalent to -2. The fraction formed by the first two coordinates will always be positive as you say, but the sign of the number is determined by the third coordinate. I hope this helps. Bill Cherowitzo (talk) 04:31, 9 September 2015 (UTC)

I understand the intention from the examples, but the text cited by 24.84.237.14 says something different, and does not make sense.

Moreover, it is not too clear why such a mapping will lead to a proof of countability of Q. Apparently the two preceeding theorems, and the sole corollary given later in the article are tacitly used, aren't they? In this case I'd suggest that their use should be made explicit, and the injectivity of the mapping (needed for the corollary) should be stated, if not established. - Jochen Burghardt (talk) 08:24, 9 September 2015 (UTC)

I thought that the question was about the mechanics of this map ... maybe I was wrong in that. The existence of this map does not, as far as I can tell, lead to a proof of the countability of Q. All that is done is to map Q onto a countable set (this countablity is established by the earlier two theorems) and you can map any infinite set onto a countable one. The standard proof here is to establish that (an isomorphic copy of) Q is a subset of N × N which has been previously established to be countable (say, by using the two previous theorems). You could use the inverse of this map in that setting, but you would have to use a proper definition of Q as a set of equivalence classes to do so. It does not appear to me that this would be in keeping with the level of the current article. The set-up for the standard proof has already been made in establishing the countability of N × N, so I think a simple rewrite of this section would set things right. Bill Cherowitzo (talk) 17:50, 9 September 2015 (UTC)

On second thought, this can be fixed by simply removing the requirement that a and b be coprime. This map is then a bijection between the sets (fractions and these triples). We just have to point out that the fractions are not reduced and equivalent fractions are not treated as equal.Bill Cherowitzo (talk) 22:36, 9 September 2015 (UTC)

When I realized the mistake I made above (and have struck out) I also gained some insight into what is happening on this page. The correction is that Q is shown to be a subset of Z × Z, not N × N. The argument (standard in most elementary treatments) depends on first showing that Z is countable, which in turn usually uses the result that the union of two countable sets is countable. In the treatment we are looking at, this last result is being avoided and therefore there is no mention of Z in the early going. This then causes this convoluted representation of Q as integer triples of natural numbers (rather than integers, since these have not yet been shown to be countable). The fix I proposed above is still valid, but I am finding the article to be a strange mix of a rather sophisticated approach (which I am sure makes the logicians happy) with a very naive treatment of Q (making some mathematicians unhappy). The statements in the article that we are concerned with are exactly where these two approaches conflict and I am not surprised that this was incorrectly presented. Bill Cherowitzo (talk) 18:23, 10 September 2015 (UTC)

An additional issue for cleanup is that right after the Corollary, the section starts all over again ("Proposition: Any subset of a countable set is countable. ..."). So several theorems are given twice; both versions of each should be merged into one. The second proof of countability of Q is based on that of Z × N, along the lines you sketched above, and is easier than the first one. - Jochen Burghardt (talk) 11:24, 11 September 2015 (UTC)

And the definition is given two times: in section Countable set#Definition and in Countable set#Formal definition and properties. The latter section, as well as Countable set#Introduction, is written in epic style, which is better suited for wikiversity than for wikipedia. However, much of its contents is useful here as it explains the background of the "countability" notion (notion of "size" for infinite sets; "proper subset" not implying "smaller size"; nevertheless existence of infinite sets of different sizes, "countably infinite" being their smallest one). - Jochen Burghardt (talk) 14:56, 11 September 2015 (UTC)

Looking at the page history I see what happened. Back in 2010 two sections were merged into one without much thought being given to the merger. The formal definition overview section was a gentle introduction that used no formulae to describe functions (hence the rather long lists of function assignments). The next section was called Basic properties and covered the same ground only this time using explicitly described functions. Some of the natural duplication in these sections (the Basic Theorem for instance) was removed. Besides this difference there was also a difference in approach; the first section putting off the theorem on the union of countable sets, while the other does it earlier and gets the countability of Z to work with. If we go through this and properly merge this material, one or the other of these approaches will be sacrificed, and I find value in each. I think I favor separating the sections again and explaining the difference in the approaches. Bill Cherowitzo (talk) 20:20, 11 September 2015 (UTC)

Problem with lede

The lede makes the misleading statement:"Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a natural number." This statement has gone too far attempting to use simple concepts to explain what a countable set is. First, both element and set should be linked to the appropriate article, but that is a minor point. There are two major problems, imho, with the statement: #1. Time should NOT be brought in to the discussion ("one at a time", "may never finish"). This is so blatantly blindingly obvious that it should not need to be said. #2. "associated with a natural number" is wrong. So, if I have a set of, say 10^10^100 elements and associate EACH and EVERY one of them with the natural number 1, then the set is countable???? WRONG! Each element of the set must be able to be set into a one-to-one correspondence with a UNIQUE natural number. There are usually many ways to set up such a correspondence. That is, which natural number is assigned to label a particular element will depend on how the "numbering" or "counting" is chosen. (Take the set consisting of the three elements {A,B,C}. They may be put into correspondence with 1,2,3 or 2,1,3 or 6,4,2, or even 2,3,5 or 100,10,1000.) A countable set is one in which each element can be assigned a unique natural number. It turns out that some infinite sets have this property, countable sets may be finite or infinite. (some, actually most, infinite sets are not countable.)72.172.10.197 (talk) 13:48, 10 October 2015 (UTC)

Booleans

Wikipedia at the moment doesn't include Booleans as a countable set or indeed as a number system. Should Booleans be added, as a subset of the natural numbers with their own arithmetic just like any of the other sets listed in Template:Number_systems? 80.42.172.137 (talk) 11:43, 29 November 2016 (UTC)

What do you mean by "Booleans"? JRSpriggs (talk) 18:09, 30 November 2016 (UTC)

Set of polynomials countable ?

The section Countable_set#Some_technical_details outlines a proof of the proposition 'The algebraic numbers A are countable'. The outline of the proof relies on the set of n-degree polynomials to be countable, since their coefficient space can be one-to-one mapped to the set of rational numbers. As far as I can see, this only holds if each polynomial coefficient is integer (or rational, but that makes no difference). So it should either be stated that the polynomial coefficients are integer (or explained how the proof holds for non-integer (actually irrational) coefficients, in which case I missed something). Thanks. Lklundin (talk) 08:29, 12 September 2018 (UTC)

Thanks for the remark. The coefficients must be rational; by multiplying with the least common denominator, they can always be made integer. Admitting arbitrary real numbers as coefficients would make e.g. $\pi$ algebraic; admitting algebraic numbers as coefficients would use them in their own definition; both wouldn't make sense. - Jochen Burghardt (talk) 10:49, 12 September 2018 (UTC)

Thanks (also because I no longer doubt that I understand the underlying math). Although the text now mentions 'integer coefficients' twice which is possibly one more than necessary, it is very clear now. Thanks again. Lklundin (talk) 15:00, 12 September 2018 (UTC)

Encyclopedic tone

I've removed the "encyclopedic tone" cleanup tag. The specific objection (from the edit summary when the tag was added) was to the use of "you" and "we". There were only five occurrences of "you" in the article, and I've removed all five by rephrasing. The use of "we" is much more pervasive, but it is not clear that it is really a problem. The Manual of Style exhorts us to avoid "we" but admits that this can create problems with the readability of mathematics articles. I doubt seriously that removing "we" would improve this article. If anyone thinks it would, please demonstrate your point by actually making the desired changes; retagging the article is unlikely to accomplish anything useful.

—Syrenka V (talk) 11:17, 16 April 2019 (UTC)

"Denumerable" deserves a special note

Readers arriving at this page to learn what denumerable means would benefit from a special note to confirm whether or not it is synonymous with countable and/or enumerable. Because of its de prefix, the word gives the strong sense that it might mean the opposite of numerable, or somehow refers to being capable of having its numerability removed. It is especially unevocative when used in the term non-denumerable, adding to the value that could be provided to readers by having its meaning deliberately spelled out unambiguously. Gwideman (talk) 13:31, 22 February 2021 (UTC)

Originally, I would have guessed that "denumerable" requires the mapping f:S→N to be computable, while "countable" does not. However, that is apparently wrong — a quick web search showed that 5 of 5 URLs use "denumerable" to mean the same as "countable": [1] [2] [3] [4] [5]. I hesitate to add a corresponding note before a native English speaker has commented on this issue. - Jochen Burghardt (talk) 15:22, 22 February 2021 (UTC)

@Jochen Burghardt: actually all five of your links seem to use "denumerable" to mean "countably infinite" rather than "countable". I also had a vague recollection that "denumerable" typically meant "countably infinite". However I'm not completely sure that it's not also sometimes used to mean just "countable" (that is, including finite sets). In any case I think it's a fairly uncommon word to use in research mathematics today, irrespective of meaning. --Trovatore (talk) 21:13, 20 August 2021 (UTC)

 Done It's discussed in the note on terminology. AFAICT it's ambiguous just like countable. Mathnerd314159 (talk) 18:16, 11 September 2022 (UTC)

Terminology - 20% is "common"?

Since the phrasing was changed from the original quote by User:Trovatore I thought I'd pull some numbers in from Google n-grams. "Countably infinite" is at 5.6 units and rising in popularity, while "at most countable" is at 1.3 units and mostly flat. (81% vs 19%) So clearly the countably infinite terminology is the most common terminology and the right one to use for the article. But as far as the other convention, can I say that the convention appears in 20% of publications? Or is that original research? Regardless 20% doesn't seem "common" so maybe it should be described as "alternative". --Mathnerd314159 (talk) 17:21, 17 September 2021 (UTC)

So it's not totally clear from the above which convention you are ascribing the 20% to. If an author uses the phrase "countably infinite", it's a good indication that he/she intends "countable" to include finite sets (the convention described as "common"), whereas using "at most countable" would seem to suggest he/she is using the convention that excludes finite sets (since otherwise he/she would just say "countable"). So taking this to be a quick-and-dirty estimate of the frequency of each convention, your results would give that 80% use the inclusive definition (finite sets are countable), the one used in the article currently, and 20% use the exlusive definition (finite sets are not countable). Is that what you meant?

I don't think this is a very reliable guide, because many authors may not have occasion to use either phrase, and those that do may use it more than once, but to the extent that it is reliable, it seems to point in the direction of confirming the existing text. --Trovatore (talk) 18:18, 17 September 2021 (UTC)

Yes, that's what I meant. So I guess citing N-grams is out as the reasoning is somewhat tenuous, but changing "common" to "alternative" for the exclusive definition should be fine? --Mathnerd314159 (talk) 19:01, 17 September 2021 (UTC)

Oh, I see -- I stopped at the first hit for the word "common". Yes, "alternative" sounds good to me. --Trovatore (talk) 19:03, 17 September 2021 (UTC)

Examples of countable sets

Example of countable set 117.98.98.174 (talk) 06:47, 4 May 2022 (UTC)

intro is bad

sadly, the intro, as is the case for so many wiki articles on math, is not written at a level appropriate for a general encylopedia it is written at much high level, and uses way to much jargon (injective function !!) please delte and re write thanks — Preceding unsigned comment added by 72.43.78.113 (talk) 15:10, 11 September 2022 (UTC)

I have edited the lead. D.Lazard (talk) 17:06, 11 September 2022 (UTC)

Rationale of "citation needed"

Regarding the "citation needed" in the section "A note on terminology": A citation for what is asked for? The fact that the total number of letters in "at most countable" plus "countably infinite" exceeds bot the total number of letters in "at most countable" plus "countable" and the total number of letters in "countable" plus "countably infinite"? Hagman (talk) 20:22, 14 November 2023 (UTC)

I agree the "citation needed" is nonsensical there. If nobody objects, I'd remove the complete part , although with respect to concision this is the worst of both worlds.^{[citation needed]}. I'd also like to remark that checking the definition is generally a good idea in mathematics. - Jochen Burghardt (talk) 21:19, 14 November 2023 (UTC)

The CN is from a deleted citation that was there before: https://en.wikipedia.org/w/index.php?title=Countable_set&diff=prev&oldid=1044657089. In the source there was a sentence "To avoid this ambiguity [countable vs. countably infinite], the term at most countable may be used when finite sets are included and countably infinite, enumerable, or denumerable otherwise". From what I can tell, deleting that citation was correct, it is the same as a sentence added to the article in 2014 and therefore WP:CIRCULAR. But when I was writing that paragraph, it was there in the article, and I thought that source was good, so I preserved it as best I could.

The citation needed is for the whole sentence, to establish that there is indeed this convention of using the combo "at most countable" + "countably infinite" to avoid ambiguity. Looking at Google Books, besides the deleted citation, the only books that show up in a search for both phrases are Marat Marvin's books, such as [6], with the sentence "To avoid ambiguity, the term 'at most countable' may be used when finite sets are included in the consideration". It also is suspiciously similar to the Wikipedia sentence but I think De Gruyter is at least not a scam publisher. I'm not sure the reference actually shows this convention exists though, he follows the countable/countably infinite convention in the rest of the book and never again mentions "at most countable".

So I would say to either delete the sentence entirely or to revise it to explain that although the combo "at most countable" + "countably infinite" is unambiguous nobody uses it in practice. Mathnerd314159 (talk) 02:52, 16 November 2023 (UTC)

Flawed definition?

"A set is countable if [...] it can be made in one to one correspondence with the set of natural numbers." How can this definition make sense when the "natural numbers" (as defined by Peano's axioms) have models of any cardinality (Löwenheim-Skolem)? Is countability inherently a concept of second-order logic? — Preceding unsigned comment added by Herpesklaus (talk • contribs) 12:06, 24 November 2024 (UTC)

The definition that you quote belongs to second-order logic, since it quantifies on infinite sets, and it supposes that the natural numbers form a set (the axiom of infinity postulates the existence of a set whose elements can be identified with the natural numbers). Also, you must not confuse the cardinality inside a theory and the cardinality of a model of the theory; they have not to agree. D.Lazard (talk) 16:22, 24 November 2024 (UTC)