Talk:Countable set/Archive 1

Archive 1

Whether countable implies infinite (part 1)

This page defined countable to mean "countably infinite". I've changed this, because in my experience it usually means "countably infinite or finite" (i.e., the opposite of uncountable). Note that we already have an article on countably infinite, so there is some duplication here.
Zundark 2001-08-12

Countable ordinals

This page address cardinals, but what does it mean to say an ordinal is countable or uncountable?

A countable ordinal is just an ordinal which is countable as a set, i.e. its cardinal is aleph_0. An uncountable ordinal is an ordinal which is not finite and not countable (as a set). --AV

Proof of the countability of Q

Why would we prove the countability of Q by taking it as a countable union of countable sets? The usual way is just to present an ordering, and is much simpler, IMO.

0, 1, -1, 2, -2, 1/2, -1/2, 3, -3, 1/3, -1/3, 4, -4, 5, -5, 1/5, -1/5, 6, -6, 3/2, -3/2, 2/3, -2/3, 1/6, -1/6, ...

What system are you following here? When will 1/4 and 5/2 show up? --AxelBoldt

Whether countable implies infinite (part 2)

I checked about a dozen random textbooks I have, and all but 2 defined "denumerable" as "countably infinite", although the 2 that defined it as "countable" are quite well-known, so I'll put a comment indicating it's not completely universal agreement. Revolver 19:12, 9 Jul 2004 (UTC)

Whether countable implies infinite (part 3)

By definition of some books (i.e. Walter Rudin's Principles of Mathematical Analysis) a countable set must be infinite, and a finite set is not countable. However, he uses the terminology (not mentioned in Wikipedia): 'at most countable'. Both countable (infinite) and finite sets are 'at most countable'. An infinite sum of finite sets, for example, is at most countable. To prove that this sum is strictly 'countable' one must prove that it is infinite.

Nerses Ohanyan

It's a bit strange that the use of countable to mean countably infinite wasn't mentioned in the article. I've added it now. --Zundark 07:15, 17 Sep 2004 (UTC)

???? But it's in the previous sentence? "A countable set is a set which is either finite or countably infinite." I've reverted. [[User:Noisy|Noisy | Talk]] 09:58, 17 Sep 2004 (UTC)

No, that's a different definition. By that definition every finite set is countable, whereas by the definition Nerses Ohanyan was talking about, no finite set is countable. So I'm going to revert back, perhaps with some extra clarification. --Zundark 10:09, 17 Sep 2004 (UTC)

OK - I think I understood on the third or fourth reading. Boy, I'm glad I'm not a mathematician. ;-) [[User:Noisy|Noisy | Talk]] 10:31, 17 Sep 2004 (UTC)

Query

Does countable mean that an element in set B can be indexed? Or am I missing something In other words set A and set B are bijective if I can write array[n]=Bk, where n is a natural number, is this sufficient for B to be countable? 59.145.141.130 10:49, 19 January 2006 (UTC)

Um, yes. If I understand you correctly, that's the definition of countability. —Keenan Pepper 17:46, 19 January 2006 (UTC)

Axiom of choice

"THEOREM: (Assuming the axiom of choice) The union of countably many countable sets is countable."

I think we don't need the axiom of choice here, as we can choose by order of counting. The Infidel 09:45, 22 January 2006 (UTC)

You do need at least a weak form of the Axiom of Choice. The result can't be proved in ZF. --Zundark 12:48, 22 January 2006 (UTC)

But where? There's scetch of proof in the article. I can't see anything that can not be done by the enumeration functions of these countable sets (and set of sets). 84.160.220.72 14:49, 22 January 2006 (UTC)

But first you must choose those infinitely many enumeration functions. --Zundark 16:04, 22 January 2006 (UTC)

I'm not sure about that. If a set is countable, there exists an enumeration. Any one will do.And I don't need a choice function that gives an enumeration for every subset of enumerations but only one enumeration out of the full set of all enumerations. The Infidel 19:06, 22 January 2006 (UTC)

Let the original sets be A_n, for n in N. You need an enumeration for each A_n. For each n, let E_n be the set of all enumerations for A_n. Each E_n is non-empty (as you point out). You need to choose an element from each of the infinitely many non-empty sets E_n. It's the Axiom of Choice that says you can do this. --Zundark 20:28, 22 January 2006 (UTC)

Look at it this way: let $E=\times E_{n}$ be the cartesian product of all the sets of enumeration on the A_n. Now for any element ${\Phi }=(\varphi _{1},\varphi _{2},\ldots )\in E$ there is an enumeration $\varphi _{1}(1),\varphi _{1}(2),\varphi _{2}(1),\varphi _{1}(3),\varphi _{2}(2),\ldots$. If we have the element $\Phi$, we have the enumeration. No need to choose. If we don't have the element, we at least have the set of all the elements, which is not empty. So we know that an enumeration exists, even if we should not be able to name it. Thus the union of our contably many countable sets is countable. The Infidel 19:04, 23 January 2006 (UTC)

You're implicitly assuming the Axiom of Choice in deciding that it's possible to choose an element out of the Cartesian product of infinitely many sets (since that's equivalent to choosing one element from each of the infinitely many sets). Ruakh 20:55, 23 January 2006 (UTC)

It's not necessary to choose an element, it suffices to know it's in there. No need to choose an enumeration, as long as we can show there is one. The Infidel 21:47, 23 January 2006 (UTC)

The point is that you don't know there's an element in the Cartesian product if you don't have the Axiom of Choice. Without the Axiom of Choice, a Cartesian product of non-empty sets can be empty. --Zundark 22:44, 23 January 2006 (UTC)

That was realy a point. I'm pretty sure I could construct a cartesian product as a restriction of some power set, but I never checked my "tools" if they depend on the axiom of choice or not. Can you provide any source, evidence or hint for your statement? The Infidel 18:26, 24 January 2006 (UTC)

If the Axiom of Choice were false, then there would be a set of non-empty sets without a choice function. The Cartesian product of these non-empty sets would be empty, because any element of the Cartesian product gives a choice function. --Zundark 19:26, 24 January 2006 (UTC)

Ok, for the moment, I will not dispute that the axiom of choice would be necessary to proof the theorem, as I am not able to state such a proof. On the other hand, I did not see a proof that it is necessary.

I feel your proof, if correct, is strong evidence that the axiom of choice holds. Otherwise, the product of some non-zero cardinal numbers is zero or undefined (and as a relation rather than a function, includes zero).

Thinking ever more strictly about sets and proofs, doubting more and more of the usual ways of deduction, how exactly is it that an element of a Cartesian product as you described will give a choice function? You will need a projection to the components, but how do you do that? I would not be astonished to find you will need the axiom of choice here.

PS: is this talk page still the appropriate place for this discussion? Shouldn't we switch to our own talk pages?

The Infidel 20:33, 24 January 2006 (UTC)

PS PS: Don't take too literally what I said about the product of cardinal numbers, I reckon we are talking about classes here rather than sets. The Infidel 20:46, 24 January 2006 (UTC)

Remember that the Axiom of Choice is known to be true for any finite collection of sets; the difficulty comes in when we're talking about an infinite collection of sets. So, 1*2 is well-defined and nonzero, but 1*2*3*... might not be. Now, obviously 1*2*3*... is going to be greater than zero, because obviously the Axiom of Choice is true, but that doesn't change the fact that we're relying on the Axiom of Choice (or some equally non-ZF assumption). Ruakh 20:56, 24 January 2006 (UTC)

I see that for infinite cardinals this is not (provably) incorrect, but still very counterintuitive. After all, as we can't proof axioms, they are not the least choosen because they are intuitive. The Infidel 21:10, 24 January 2006 (UTC)

To answer some of The Infidel's points:

Set theorists have constructed models of ZF in which the union of countably many countable sets is sometimes uncountable. This shows that the Axiom of Choice (or a weak form of it) is necessary for this theorem.

As far as I know, there is no reasonable way to define products of infinitely many cardinal numbers without the Axiom of Choice.

An element of a Cartesian product is a function from the index set I into the union of the base sets A_i such that each i maps into A_i. So an element easily gives you a choice function if the A_i are all distinct. Projection maps can be defined without the Axiom of Choice, but they aren't needed here.

--Zundark 22:16, 24 January 2006 (UTC)

Set theorists have constructed models of ZF in which the union of countably many countable sets is sometimes uncountable. This shows that the Axiom of Choice (or a weak form of it) is necessary for this theorem.

That's cool. I didn't know that. This clarifies a lot. Thank you. The Infidel 18:10, 26 January 2006 (UTC)

Numbers or not numbers

Someone recently added:

Note that the number of elements of the set of natural numbers is not itself a number in the sense that you can do the usual kind of addition and subtraction.

I couldn't tell what this meant exactly, so I removed it. You can add cardinalities of sets, simply by taking two disjoint sets with those cardinalities and taking the cardinality of their union. —Keenan Pepper 17:17, 22 January 2006 (UTC)

After your reverting, the article states "In mathematics the term countable is used to describe the size of a set, i.e. the number of elements it contains.". For infinite sets, this "number" is not a number in the "usual" sense: you cannot add up, subtract or divide it in any way we are used to do with natural numbers or the elements of a field or ring. For the "number" of elements of a countably infinte set, the equation $\aleph _{0}+1=\aleph _{0}$ holds. If you remove anything in wikipedia that you don't understand exactly and without asking, there'll probably be nothing left. The Infidel 18:56, 22 January 2006 (UTC)

The new version by Ruakh is better all around. —Keenan Pepper 21:58, 22 January 2006 (UTC)

Thanks! I try. :-) Ruakh 22:51, 22 January 2006 (UTC)

It looks better now. My main point was that someone without knowledge about cardinal numbers would use everyday maths on equations like $\aleph _{0}+\aleph _{0}=\aleph _{0}$, subtracting aleph on both sides and ask on the help page if zero equals infinity. The Infidel 18:38, 23 January 2006 (UTC)

Question

Normally with infinite sets you work in the direction of infinity (the big end).
Let's go the other way.

Suppose you have an infinite set S.
Now you remove one element.
and another
and another
...

As I see it, you will never come back into the finite world again in this way.
Is this logically valid? Can anybody explain this to me?
Landheha 21:25, 6 March 2006 (UTC)

It seems perfectly valid. What do you need explained? —Keenan Pepper 22:39, 6 March 2006 (UTC)

Well, when you keep removing elements from a set (infinite or not) you should be able to come back to the empty set at one time or another, shouldn't you?
I don't see this happening for infinite sets. Do you? Landheha 22:53, 6 March 2006 (UTC)

If you start with the empty set and add one element at a time at a fixed, finite rate, you'll never have an infinite set. Conversely, if you start with an infinite set and remove one element at a time at a fixed, finite rate, you'll never have an empty set. It makes sense to me; what do you find odd about it? Ruakh 22:56, 6 March 2006 (UTC)

Sorry, but I haven't done any college studies on this topic. OK, so adding or removing an element to an infinite set is invalid?Landheha 23:01, 6 March 2006 (UTC)

No, it's completely valid — but adding or removing one element won't change the cardinality. You'd need to add or remove infinitely many elements, and even then it depends on exactly which elements. (Infinities aren't always very intuitive, I'll admit. |N| = |2N|, but |N \ N| = 0, while |N \ 2N| = |N|. Adding infinities is slightly better, though: if A and B are infinite sets, then |A U B| = |A| and/or |A U B| = |B|.) Ruakh 23:08, 6 March 2006 (UTC)

I AM removing infinitely many elements, one at the time. I think you are again focusing on the big end in your examples by adding, multiplying or dividing. I am subtracting, removing elements infinitely. You say "it depends on exactly which elements you remove". I don't understand this. How can you point to certain elements in an infinite set? Landheha 23:48, 6 March 2006 (UTC)

Re: "I AM removing infinitely many elements, one at the time.": No, you're not. If you remove elements, one at a time, at a fixed, finite rate, then you'll never have removed an infinite number of elements. Ruakh 00:10, 7 March 2006 (UTC)

Re: "I think you are again focusing on the big end in your examples by adding, multiplying or dividing. I am subtracting, removing elements infinitely.": Dividing? Who divided anything? Note that \ is the symbol for relative complement — i.e., the "subtraction" of one set from another. Ruakh 00:10, 7 March 2006 (UTC)

Re: "How can you point to certain elements in an infinite set?": That depends on the set. With the set of natural numbers (which is what I used in my examples), there are plenty of easy-to-point-to elements, such as 1, 2, or 3. Ruakh 00:10, 7 March 2006 (UTC)

I thought there were generic production rules for infinite sets which start from the empty set. It seemed logical to me that you should be able to come back to the empty set again. I know not all things can be reversed, but here I could not see a reason why not. Landheha 23:48, 6 March 2006 (UTC)

Re: "I thought there were generic production rules for infinite sets which start from the empty set.": Yes, but not by adding one element at a time. Ruakh 00:10, 7 March 2006 (UTC)

OK, thank you very much for your patient answers, I think I got it now. Have done some extra reading and thinking and I see where I went wrong. Thinking this way indeed takes some more getting used to than I thought :-)

this "Question"-part has played it's part, at least for me and I don't think it is very instructive for others. Is it OK if I remove it altogether?

1-on-1 correspondences

There might be another possible way to look at these counter-intuitive 1-on-1 correspondences between different infinite sets. To do this you can make an analogy with fractals.

Picture before you a fractal like the famous Mandelbrot set on a computer screen. You can zoom in to any smaller part of the screen and you will get to see the small part filling the entire screen with the same detailed resolution. You can keep zooming in forever without losing detail.

Suppose now mathematics is a tool with a certain precision.
It can be pointed at an object of any size.

Say you look at the set N.
Math will let you look at it with it's inherent precision.
Then you zoom in on the subset of the even numbers.
Math will let you look at it with it's inherent precision.
Yes, you can make an 1-on-1 correspondence.

Say you look at the set Q.
Math will let you look at it with it's precision.
Then you zoom in on N.
Math will let you look at it with that same precision.
Yes, you can make an 1-on-1 correspondence.

You can also simulate this recursive zooming in on the number of points on any piece of line. Math allows you to keep zooming in, so you arrive (or better: you will not arrive :-) at R points. Each step of zooming in will give you again the precision math has.

Being a non-mathematician, I think this is a fun idea.
I can't find fault with it and it might make life much easier.

Anybody???? Landheha 21:25, 6 March 2006 (UTC)

I don't think the fractal analogy is really helpful, simply because I don't think the fact that any part of a fractal is equivalent to the whole is no more intuitive than the fact that the interval (0,1) is equivalent (in some ways) to R. Also, because I think most people would have a hard time mentally zooming in from the natural numbers to the even numbers, seeing as the even numbers are not really a region of the natural numbers. (Actually, I'm more inclined to zoom out to see the even numbers — when you're zoomed in, your scale is smaller, but as you move out, your scale increases.) Ruakh 23:01, 6 March 2006 (UTC)

Zooming in or out doesn't matter for the resolution of the tool. This is just a matter of starting point. You are still able to make 1-to-1 correspondences. I thought it clearer to paint the picture starting with "zooming in on a subset, being a part of the whole".

Excuse me for making a non-correct statement where you say the even numbers are not really a region of the natural numbers. I am just refering to the many cases where just this example is used to show the counter-intuitive aspects of infinity in that the cardinality of a subset is the same as its superset. If this is not mathematically correct, please don't blame me. I am just echoing someone else's examples here Landheha 00:07, 7 March 2006 (UTC)

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)

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 D_m 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 D_m? 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 D_m 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 D_m 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)

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)

I have made significant changes to match Walter Rudin's book. Teply (talk) 00:01, 11 December 2007 (UTC)

Reverted non-standard usage. JRSpriggs (talk) 04:09, 11 December 2007 (UTC)

Both uses of countable are commonly used; I checked a couple set theory books off my shelf and found both definitions. It really isn't worth spending too long on. The article just needs to point out that that there are two possible meanings, and be clear. — Carl (CBM · talk) 04:15, 11 December 2007 (UTC)

Denumerable in lede

I came here from a link to Denumerable (I suspected it was a synonym of countable) and was rather confused to find that the lead did not define the term I was looking for. So I'm moving it there (it's common to mention synonyms in the lead anyway). --Taejo|대조 09:38, 13 June 2007 (UTC)

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)

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)

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

Opposed to editing if the balance between encyclopedic conciseness and user accessibility is skewed against making the article readable to the vast majority of readers. Of course, good referencing is always desired, and wikification/link colors/link type symbols interrupting visual flow are already debated elsewhere. Historically, Russell and Whiteheads' Principia Mathematica has been considered so obtuse that Russell ended up writing an entire book, Introduction to Mathematical Philosophy ISBN 0415096049, as a layman's introduction where he avoided set theory altogether in favor of a discussion of classes before his chapter on mathematics and logic. If editing is done, care must be taken to not dry out the text so much that it merely crumbles on the palette as a tasteless mass. Hotfeba 22:39, 9 April 2007 (UTC)

I studied pure mathematics as one of 3 options at 2nd year University level, after passing Further Maths A-level at A grade. That was several years ago and I have forgotten much of what I learnt about set theory, but I was pleased to be able to understand this article and learn something new with only reading a couple of times. I assume that one of the primary objectives of Wikipedia is to make knowledge of all kinds accessible to more people for free. By writing a high-level maths article using real world examples which laymen and laywomen could understand is an excellent practice I think. I certainly don't think the article should be moved to Wikiversity, because this would narrow down the number of people who could possibly understand this subject even further. As it is, an enthusiastic teenage genius who has the misfortune to attend an average school could in theory, by following links, understand this whole concept without their teacher or other textbooks.

I studied nothing about biology or geography since 14 years old, but I challenge anyone to find a Wikipedia article on either of these subjects which I could not understand within 20 minutes' reading*. But having followed about 5 links to get to this article (started from the Integer Summation article on Wiki homepage), I guess there are hundreds of maths articles I would find impenetrable for a long time. Mathematics is I believe the least accessible of all academic subjects and deserves lenience, there is no "improper tone" if you can give the teenager an extra chance to embrace knowledge instead of force-fed advertising. This article is competing with X-Factor and Big Brother for their attention, the teenager needs the writer who can enthuse them by keeping the subject closer to the tangible world around them! Adding more citations is fine I think but don't need to interrupt the readability of the text. Otherwise you could set up your own website for complex mathematical definitions and get a prominent mathematical genus like Steven Hawking to sponsor you. Mind you, since he likes to write very clearly for the layperson, he might defer.

*assuming my Internet connection does not cock up again....--Willcrox 21:20, 16 April 2007 (UTC)

I appreciate the fact that some of the maths articles contain sections like this - that aim to make it accessible to the layman. The slightly less formal tone is a small price to pay, I think. Without this kind of section, this would be an incomprehensible page for me. 82.35.199.228 15:20, 12 June 2007 (UTC)

Is bijection necessary?

I am interested to know if bijection is a necessary requirement for answering the question: "Are two sets of the same size?" For comparing finite sets, one-to-one correspondence appears to yield onto mapping as a natural consequence rather than require it to reach a determination. For countably infinite set comparisons, one-to-one correspondence again seems sufficient with onto mapping following as a consequence, not preceding as a prerequisite. For sets of greater orders of infinity beyond countability, there are power set inequalities. Is bijection forced by considering paradoxical results of those set theories only requiring one-to-one correspondence or power set inequalities to determine the size relation between two sets, and if so, what paradoxical results are avoided? Hotfeba 22:11, 9 April 2007 (UTC)

The definition of having the same cardinality is that there is a bijection. If two sets have the same cardinality, then necessarily there is a bijection. That does not mean it is necessary in all cases to explicitly construct such a bijection in order to prove they have the same cardinality. The Cantor-Bernstein theorem says that if there's an injection in each of the two directions, then there is a bijection. Michael Hardy 22:37, 9 April 2007 (UTC)

True, but a theory in which cardinality by bijection is taken as axiomatic or by definition tends to have less generality than a theory where bijection is proved to be merely a theorem under that theory. Your citation of the theorem leading to bijection is directly on point. Hotfeba 23:04, 9 April 2007 (UTC)

"Bijection" and "one-to-one correspondence" mean the same thing. Your question is incoherent. JRSpriggs 10:43, 10 April 2007 (UTC)

Ahh, I see. "Bijection" is merely shorter jargon for "one-to-one correspondence" and is not necessary for the derivation of theorems in the theory we all assume we are talking about, unless the equivalence you speak of in your first statement is, either by definition or by necessity for derivation, not symmetric. In fact, I now see that one-to-one corespondence may be excessive for all finite set comparisons when all that is needed is a simple one-to-one relationship between one set's elements and the elements of the other in a choose-without-replacement scheme: if there are unmatched leftovers in either set, then the sets are of different sizes; if not, then they must be the same size. Unless you have a counter-example, it appears we can agree that the concepts of cardinality and bijection are not required to determine if two finite sets are of the same size. Hotfeba 20:26, 11 April 2007 (UTC)

Re: "[…] the concepts of cardinality and bijection are not required to determine if two finite sets are of the same size.": Well, "cardinality" means "size", but overall, that's a true statement. The reason we formally define "cardinality" in terms of bijections is so we can apply the term to infinite sets; if we restrict consideration to finite sets, then there's no need for that. —Ruakh_TALK 00:01, 12 April 2007 (UTC)

Apologies, but I was considering sets that humans or their computers could compare in reasonable periods of time. For programming design/deadline/delivery purposes, it is helpful to know that implementing strict cardinality tests on finite sets is not necessary by proof or definition. Hotfeba 00:12, 12 April 2007 (UTC)

To Ruakh: Do not feed the trolls. JRSpriggs 08:20, 12 April 2007 (UTC)

Don't trolls try to engender anger? I'm not feeling angry, or even frustrated. —Ruakh_TALK 13:51, 12 April 2007 (UTC)

Well, if you think that he is being reasonable, you are free to keep talking to him. But I think that he is either intellectually dishonest (my definition of a troll) or so stupid/confused that it is a waste of time to talk to him any more. JRSpriggs 02:27, 14 April 2007 (UTC)

Simpler terms?

I was thinking of adding a sentence to the intro paragraph to put the concept into laymans terms:

In other words, each element in a countable set can be paired off with a counting number, like numbering the pages in a book. This is possible even if the "book" has an infinite number of pages.

Japanese wikipedia

Bablefish suggests that the linked Japanese article really is about countably infinite sets, rather than countable sets as we define it here. Can any reliable Japanese-speaker comment on ja:可算無限集合? — Arthur Rubin | (talk) 23:55, 17 June 2007 (UTC)

Even so, might it not be the closest equivalent article on their wiki? In which case, it should be linked anyhow. JRSpriggs 07:25, 18 June 2007 (UTC)

I don't see the difference. "Countable set" and "countably infinite set" are not synonymous, but if I had to write an article about each, they'd be almost word-for-word the same. —Ruakh_TALK 16:14, 18 June 2007 (UTC)

I hadn't really considered that. I had assumed this might have been the result of User:WAREL on one side or the other. I guess it should remain, then. — Arthur Rubin | (talk) 18:13, 18 June 2007 (UTC)

scrabble example

From the article: "Remember our example of the Scrabble words." This is the first occurance of the word "scrabble" (case insensitive) in the article. What is the reader supposed to be remembering? --Thinboy00 @901, i.e. 20:36, 4 December 2007 (UTC)