Talk:Countable set

From Wikipedia, the free encyclopedia

You have new messages (last change).

Contents

[edit] Archive 1

This page was getting rather long and unwieldy, so I've moved old discussions (going from 10 December 2001 to 7 March 2006) to Talk:Countable set/Archive 1; I hope no one minds. Ruakh 20:58, 29 April 2006 (UTC)

[edit] Mentionable numbers

This section currently asserts that the set of all infinite strings in English is countable. Since there is a one-to-one correspondence between {decimal expansions of real numbers} and {infinite lists of digits in English}, surely this is false? —The preceding unsigned comment was added by 193.170.117.10 (talk • contribs) .

I'm not sure I agree that the section asserts quite that; rather, it asserts that {numbers that can be completely characterized by finite or infinite strings of English} is countable. Your argument is sound, though, and that definitely needs to be fixed; I'll take care of it. Thank you! Ruakh 19:39, 29 April 2006 (UTC)

Agreed, thanks. Having thought about mentionable numbers a little more, I came up with the following: create a list of all English sentences which describe a number, listing sentences firstly by length and then by lexicographic order. Removing multiple entries, we obtain an enumeration of the mentionable numbers. Apply a Cantor diagonal argument to create a number 'x' which is not on the list. Since 'x' is not on the list, it is not mentionable; but we have succeeded in describing it precisely in finitely many words, so it is mentionable. What is the resolution to this apparent paradox?

I'm not sure that this discussion is necessary for the article, but I'd be interested to read an answer :o)

Invisible Capybara 08:34, 9 May 2006 (UTC)

Define Dm as "The real number between zero and one whose n-th digit after the decimal point is '7' if the n-th mentionable number is a real number whose n-th digit after the decimal point is '2', '3', or '4' and is '3' otherwise.". Now suppose that this is the k-th mentionable number. What happens when you try to compute the k-th digit of Dm? You go into an infinite loop; and never get a value. So you cannot make your list without solving the Halting problem which is impossible. JRSpriggs 09:21, 9 May 2006 (UTC)
To me it looks like Dm above, if it appears in the k-th position of the list, can't have a k-th digit in a manner compatible with its definition, and therefore doesn't appear on the list at all; I don't quite understand where the halting problem comes in. The set of mentionable numbers has to include some uncomputable numbers, but I don't see why not being able to compute the digits of numbers on the list prevents the list's being definable. Invisible Capybara 12:57, 9 May 2006 (UTC)
That's a good point. It's quite easily proved that if the set of mentionable numbers is well defined, then it must be countable (assuming that mention means complete characterized by a finite English string), but Cantor's diagonal argument implies that if a set is countable, then you can mention a real number that's not in the set. Here, that implies that if the set of mentionable numbers is well defined, then you can mention a number that's not in the set of mentionable numbers, which is impossible. Ergo, the set of mentionable numbers cannot be well defined. (I'm not sure if this is appropriate to this article, though; it's an interesting example of a proof that makes use of countability, but it might constitute original research. Plus, there have got to be better examples of proofs that make use of countability.) Ruakh 18:14, 9 May 2006 (UTC)
I think it's reasonable to doubt that mentionable numbers are well-defined. I'm inclined to say that the mentionable numbers section should be removed unless a reference can be found which addresses this issue satisfactorily. Invisible Capybara 13:57, 10 May 2006 (UTC)
It's more than reasonable to doubt it, seeing as it's easily disproved (using what we've already said). Ruakh 04:02, 11 May 2006 (UTC)

To Invisible Capybara: I was just trying to make your idea more concrete, so that we could see what the source of the paradox is and whether it can be fixed. If Dm did not appear in the list of mentionable numbers, then this looping problem would not prevent it from being well-defined. And so it would be a real number definable by an English expression and thus mentionable. So leaving it off the list is not the solution. You are right that something does not have to be computable to be definable. So my comment about the halting problem was inapt (although there are similarities).

To Ruakh: The problem is that English is not sufficiently well defined itself to allow it to be used to define all other things. So really, we should delete that section, since it is incorrect to talk about the set of all numbers definable in English, that is, the mentionable numbers. JRSpriggs 08:55, 10 May 2006 (UTC)

I disagree with your assessment. Some numbers that are clearly mentionable, e.g. one and pi. True, English isn't perfect, and there exist ambiguous English strings; but I don't think that's the problem here: even if English were completely well defined, the set of mentionable numbers could not be, as shown above. Ruakh 04:02, 11 May 2006 (UTC)
I did not mean that there are not some numbers which are clearly mentionable. I said that the *SET* of *ALL* mentionable numbers does not exist. As compensation for the loss of that section, I added a section on the minimal model of set theory which includes most numbers that people are likely to mention in practice (unless they are interested in large cardinals). JRSpriggs 07:24, 11 May 2006 (UTC)
By the way, I think that the paradox which we have been discussing here is a version of the Berry paradox. JRSpriggs 07:37, 13 May 2006 (UTC)

[edit] Countable/denumerable

The OED only lists 'denumerable' as synonymous with 'countable', and I have never heard of it used to mean 'countably infinite'. I have swapped round the terms in the article so that it defines the terms as synonyms, but then mentions the alternative use in the following paragraph. Oliverkroll 13:13, 15 May 2006 (UTC)

That looks fine. I think it's less confusing this way, anyway. Ruakh 15:05, 15 May 2006 (UTC)
According to "Webster's Encyclopedic Unabridged Dictionary of the English Language (1989)" and to my memory of what I was taught in school and what I have used all my long life, "countable" means either finite or equinumerous with the natural numbers and "denumerable" means equinumerous with the natural numbers (not finite). I am changing it accordingly. JRSpriggs 06:30, 16 May 2006 (UTC) P.S. As a practical matter, it is more useful to have "denumerable" have a different meaning than to have the same meaning as "countable".
On closer reading the OED actually does have 'denumerable' = 'countably infinite' as the primary meaning. Sorry about that Oliverkroll 14:35, 16 May 2006 (UTC)
Incidentally, it defines countable (in the mathematical sense) as simply denumerable, with no elaboration. Indeed, I can't find any source that defines countable and denumerable differently; rather, it seems to me that mathematicians tend to use countable almost exclusively, and define it the broader way, while dictionaries tend to define both countable and denumerable the narrower way, with the broader way given as an afterthought or not at all. Ruakh 14:47, 16 May 2006 (UTC)
Rudin's Introduction to Real Analysis defined countable as countably infinite, and "at most countable" as finite or countably infinite. So yes, the term does vary by author. I think authors use countable or denumerable and not both though. Althai 07:09, 30 November 2006 (UTC)

[edit] Cartesian product

In the explanatory text of the article this paragraph appears: "The resulting mapping is like this: 0 ↔ (0,0), 1 ↔ (0,1), 2 ↔ (1,0), 3 ↔ (2,0), 4 ↔ (1,1), 5 ↔ (0,2), … It is evident that this mapping will cover all such ordered pairs." It beguilingly asks us to believe what is taken to be an obvious correlation between the set of natural numbers and the cartesian product NxN, but no mapping is given to bolster the veracity of the correlation. I believe I have worked out the mapping to be such that the pair (i,j) correlates to the number (i+j)(i+j+1)/2 + (i+1). Thus, (0,0) maps to 1. My maths is sufficient to show that the mapping is unique in that for (i,j) and (i,k) then j=k to get the same number; and similarly for (i,j) and (k,j). However, my maths is not sufficient to show that if the mapping is the same for (i,j) and (p,q) then we must have i=p and j=q, though, beguilingly, I suspect it's so. Presuming this to be correct then it answers an earlier question concerning the position of the quotient m/n in the sequence. —The preceding unsigned comment was added by Jimalton (talk • contribs) .

I think you're looking at it the wrong way. It's really not trivial to see what natural number gets assigned to each ordered pair — especially since the path goes back and forth, rather than going the same way in each diagonal — but I think it's fairly self-evident that the path covers each ordered pair exactly once, and hence that you can number the ordered pairs by going along the path and numbering them sequentially. I don't think giving a mathematical formula would make that any more clear; indeed, I think it would distract from the real argument. Ruakh 02:55, 5 November 2006 (UTC)
I think it would be nice to at least see an inductive proof. —The preceding unsigned comment was added by 74.109.7.4 (talk) 17:19, 13 February 2007 (UTC).
Oh, question: you do see the image above that paragraph, right? Because if that image failed to load for you, then I can definitely understand your confusion. Ruakh 02:56, 5 November 2006 (UTC)

[edit] Explain why axiom of choice is needed

THEOREM: (Assuming the axiom of choice) The union of countably many countable sets is countable. —The preceding unsigned comment was added by Roadrunner (talk • contribs) .

You're guaranteed that for each of the countable sets you're uniting, there's some bijection from that set to the natural numbers. You are not guaranteed, unless you have the Axiom of Choice, that you can choose one such bijection for each of them. Since the proof assumes that these bijections have already been chosen, the proof relies on the Axiom of Choice (or some other non-ZF axiom). For a fuller explanation, see Talk:Countable set/Archive 1#Axiom of choice. Ruakh 21:33, 28 November 2006 (UTC)
perhaps one could clarify slightly: You are not guaranteed, unless you have the Axiom of Choice, that you can choose one such bijection for each of them "simultaneously", meaning the bijections you choose is an element of a Cartesian product. Mct mht 23:32, 22 December 2006 (UTC)

[edit] Improper tone?

Does anyone else feel that this article is somewhat lacking in the encyclopedic tone? The content seems all well and good, but the style of writing reminds me of a freshman introductory analysis text. Furthermore, the complete lack of citations bothers me. I think it would be best to work on the following: a) Rewriting much of the article to attain a more appropriate tone, b) citing sources (when I come back to work on this, I'll have Rudin's Principles of Mathematical Analysis handy), and c) mentioning the importance of countable sets in mathematics Ojnabieoot 10:48, 30 January 2007 (UTC)

Concur. It seems like it is written as a "how to understand the concept" rather than what the concept itself is. Granted, considering that set theory is not my background, I thoroughly enjoyed it. However I think the article, as it stands, belongs in Wikiversity, rather than Wikipedia. Comments like "This may seem a strange situation" do not belong here.samwaltz 02:08, 5 February 2007 (UTC)
Rubbish. It's written perfectly. The author of this article could quite obviously blow you both out of the water so you don't have any right to comment. I feel that it's nice that a short "laymen's description" is included. Most people out there have no idea what set-theory is and how to understand it, most of the time coming here from other (less complex) articles that link to this one. What the hell is the point of any encylopedia article that doesn't help the reader understand the subject but instead blows off a lot of spiel that the reader won't understand and thus learns nothing? Judging from some of the other rubbish and misleading crud on wikipedia, your time would be better spent on cleaning that up rather than making pedantic and useless comments about a perfectly good article. BTW are you getting paid for doing this? No? The owners of Wikimedia are making a fortune from you. Would I donate to Wiki? ABSOLUTELY NOT, not with people like you around. —The preceding unsigned comment was added by 80.176.233.50 (talk) 22:20, 28 March 2007 (UTC).
Retrieved from "http://en.wikipedia.org../../../c/o/u/Talk%7ECountable_set_d0c6.html"