From formulasearchengine
Jump to navigation Jump to search

Template:Talkheader Template:Maths rating

Database theory

To include treatment about cardinality as it relates to database theory (i.e., that cardinality refers to the relationships from one entity to another or that it represents the number of tuples in a table), would that be sensible? Or is it deserving of a separate article?

To Lazyboyz: 1. Databases are not part of set theory. Your suggested contribution should be in a different article in a different category. I suggest that you try to find something in the area of computer science for it. 2. This section of the discussion which you created should have been put at the end, not the beginning of this page. Also you should not creat section headers manually as you did. You should use the "+" tab at the top of the screen to initiate a new section of the discussion. It will prompt you for a section title and put the new section at the end as is proper. 3. You should sign your contributions to the discussion by putting four tildas, like "~~~~", at the end of your message. The software will automatically replace it with your user-id and date and time when you save the addition. As I now do here: JRSpriggs 07:26, 25 April 2006 (UTC)
JRSpriggs, i'm not lazyboyz, but I wanted to comment on something. i always creat section headers, then again I always include new comments on the bottom of the page. I didn't know you HAVE to use the "+" tab, which by the way, appears nowhere on top of the screen. Let me know where it appears so I can use it next time, and please tell me where it says I HAVE to use that tap instead of manually creating a section title. regards,Cjrs 79 14:27, 25 April 2006 (UTC)
To Cjrs 79: I said that Lazyboyz "should" use the plus tab, not that he or anyone-else "must" use it. Since he seems to not understand our system well, then I thought that using that method would help him do the right thing instead of making mistakes. The plus tab is at the top of discussion (talk) pages between the "edit this page" tab and the "history" tab. By the way, your user name includes my initials ("jrs"). So I am curious as to what it stands for. JRSpriggs 10:26, 30 April 2006 (UTC)
To JRSpriggs. I don't see a + tab either. The tab between the "edit this page" tab and the "history" tab says "new section", which evidently serves the same purpose. I don't know whether this is a browser-dependent phenomenon (which hardly seems possible), or they have changed the tab title. Hccrle (talk) 17:37, 2 July 2008 (UTC)

Why don't you do something like two articles ;- Cardinality(Mathematics) and Cardinality(Databases) with links between them where the ideas cross over. 15:16, 27 October 2007 (UTC)

Frankly, I see no connection between this article and any of the other articles listed at Cardinality (disambiguation). There would be no cross over and thus no links. JRSpriggs 01:00, 28 October 2007 (UTC)
To Hccrle: It has been more than two years since my comment about the "+" tab. The wiki interface software is constantly being changed. One of the recent changes changed the tab from "+" to "new section" which is more descriptive. The function remains basically the same. JRSpriggs (talk) 05:39, 3 July 2008 (UTC)

Cardinality of the powerset of the natural numbers

The assertion that 2^Aleph-null is the cardinality of the real numbers is troubling me. Isn't it possible to enumerate the power set of the natural numbers? It seems so to me, I started doing it. Say that the empty set is the first element (that is, we're creating a function mapping the naturals to their power set, so f(0) would be the empty set), f(1) would be {1}... f(2) = {2} f(3) = {1, 2}

f(4) = {3} f(5) = {1, 3} f(6) = {2, 3} f(7) = {1, 2, 3}

f(8) = {4} f(9) = {1, 4} f(10) = {2, 4}...

and so on (forever). Doesn't creating this mapping show that the two sets are both countable? Or is my mapping somehow not good enough?

Thanks, -David

Well David. Any function between reals and naturals is never surjective. What you assert in your comment is that the naturals are enumerable, or countable, which can be proven false by a diagonalization argument. Also note that you would need a 1-1 correspondece. Can you prove that the function you just defined is indeed a 1-p1 correspondence?

I hope this helps, if not feel free to leave a message in my user page.

Cjrs 79 18:23, Jan 17, 2005 (UTC)

To Cjrs: You got it backwards. The naturals (0,1,2,3,...) are countable. It's the reals that are uncountable.

The problem with your enumeration, David, is that you will only get finite subsets that way, not infinite subsets. -- Walt Pohl 22:39, 17 Jan 2005 (UTC)

Thanks for your answers. I don't quite understand yet how my enumeration is invalid, but I'm mulling over the idea that it doesn't generate infinite sets. The problem I am really wrestling with is this: Why does the power operation create a strictly higher cardinality, as opposed to other operations (addition, multiplication). I've read Cantor's proof, and seeing no flaws I guess I accept it, but since it works through setting up a contradiction, it doesn't really speak to my question, as far as I can see. All it tells me is that 2^Aleph-n > Aleph-n. (To say that 2^Aleph-n = Aleph-(n+1) seems like an unfounded extrapolation, unless there's a proof of this I haven't seen.) For what values of k would k^Alpeh-n > Alpeh-n, anything larger than 2? Larger than 1? How could I find out generally what functions f( k, Aleph-n ) > Aleph-n. Or what about Aleph-n * Aleph-n. To me this would intuitively be Aleph-(n+1), but we already know that I don't have too strong a grasp on all this business. :P

If you think your enumeration eventually does produce infinite subsets, perhaps you might like to hazard a guess as to which natural number n is the first one for which f(n) is infinite. To answer your questions: you are correct about 2^Aleph-n = Aleph-(n+1). This is known as the Generalized Continuum Hypothesis (GCH), and it was proved to be unprovable by Paul Cohen in 1963 (it had been proved to be relatively consistent, that is, consistent if the axioms of set theory are consistent, by Kurt Gödel in 1930; to put it another way, the negation of GCH is also unprovable). k^Aleph-n > Aleph-n for k > 1. Aleph-n * Aleph-n = Aleph-n. This is easy to prove; an example of this was given in the article, where the space-filling curves were used as bijections between the real line (c) and the interior of the unit square (c * c). As noted in the article, this was proved earlier without using space-filling curves. A simple bijection would be f(x) = (y,z), where x,y, and z are real numbers between 0 and 1, defined by taking the decimal expansion of x, and letting y be the real number whose decimal expansion consists of the digits in the odd-numbered positions thereof, and z, the even-numbered positions. Likewise you can form a bijection between the natural numbers (Aleph-0) and the ordered pairs of natural numbers (Aleph-0 * Aleph-0) by enumerating the ordered pairs, starting with (0,0), followed by the two ordered pairs whose elements add up to 1, namely (0,1) and (1,0), then the three that add up to 2, and so on. This shows that the set of rational numbers is countable. Thus it is a countable dense subset of the uncountable set of real numbers. (Dense means that between any two real numbers in the usual order, there is a rational number.) How does that mess up your intuition? Hccrle (talk) 18:09, 2 July 2008 (UTC)

intro wording

The cardinality of a set is a property that describes the size of the set by describing it using a cardinal number.

I dislike this wording. It's perfectly possible to discuss cardinality without reference at all to cardinal numbers, you simply say two sets have the same cardinality if there is a bijection between them. In fact, this was the approach taken by Frege, I think. I'm not arguing against cardinal numbers by any mean, simply suggesting that the notion of cardinal number is not necessary to discuss cardinality, so the intro should be reworded. Revolver 09:45, 14 Jun 2005 (UTC)
Wouldn't that be like saying "two groups are isomorphic if there is a.... , instead of an isomorphism is a...." I think there should be a discussion or explanation of what cardinality means outside of the property of two set having the same cardinality. Maybe we can find a definition that we can agree on...

Cjrs 79 12:58, Jun 14, 2005 (UTC)

I'm not sure what your comment means. You can talk about cardinality simply by defining bijection, just as you can define isomorphic groups simply by defining group isomorphisms. The difference is when you select a representative from each isomorphism class, in the case of cardinality these are the cardinal numbers. To do the same for groups would be to select a group representative from each group-isomorphism class, and then collect these into a class itself. (More precisely, you would be forming the skeleton of Grp. I'm not sure what "I think there should be a discussion or explanation of what cardinality means outside of the property of two set having the same cardinality." means. By definition, "two sets have the same cardinality" if there is a bijection between them. That is the definition of the term "cardinality". Then, you can define cardinal numbers and prove two sets have the same cardinality iff they have equal cardinal numbers. Revolver 19:48, 14 Jun 2005 (UTC)


This is a different question from the above, but since I don't feel like starting a new topic, I'll post it here:

I read somewhere that the reals in the interval [0,1] can be put into a bijection with the \Re \geq 0 . The bijective function in question is \frac{x}{1-x}

How can it be proven that the function is bijective?

I (naively) thought of the following:

Suppose there exist a nonnegative real number r. Then \frac{x}{1-x} = r which can be expressed in terms of r to be x = \frac{r}{1+r}

Now it must be shown that 0 \leq \frac{r}{1+r} \leq 1

Suppose \frac{r}{1+r} < 0Then r < 0 which contradicts the definition of r. Suppose \frac{r}{1+r} > 1, then r > 1+r, which means 1 < 0, which is a contradiction. The function can be shown to be injective by noting that its derivative \frac{1}{(1-x)^2} is always positive for all values of x and hence the function is strictly increasing and hence injective.

But the limitations of my informal "proof" are that it does not show that the function is surjective. How can this be shown? If there is anything with the "proof" above, please point it out; I haven't studied maths formally yet. —The preceding unsigned comment was added by (talkcontribs).

In effect you have already shown that the function is surjective. The fact that you started with the assumption that r is any nonnegative real number, and found a value of x that maps to r, proves that all nonnegative real numbers are in the range of the function, so the function is surjective. The only problem is, the bijection is not with [0,1], but with [0,1), because when x=1, the function is undefined. Hccrle (talk) 18:25, 2 July 2008 (UTC)

The cardinality of

NOTE: This section was a part of the next section. I separated it because it reached a clear conclusion, while the main discussion is still ongoing. I also corrected the parts of the main discussion in which I incorrectly assumed that . Paolo.dL 18:04, 24 August 2007 (UTC)

The cardinality of the real numbers does not have to be . All that can be safely asserted in ZFC is that it is an uncountable cardinality. — Carl (CBM · talk) 15:42, 24 August 2007 (UTC)

I think that this is a secondary point, with respect to the others discussed in this section. However, by the way, that was the only topic, among those I discussed, about which a reader could find an explanation in the article (section "Cardinal numbers"):
"The cardinality of the natural numbers is denoted aleph-null (), while the cardinality of the real numbers is denoted . It can be shown that (see Cantor's diagonal argument). The continuum hypothesis states that there is no cardinal number between the cardinality of the reals and the cardinality of the natural numbers, that is, ".
If you are right, this implies that this part of the article needs a revision. Paolo.dL 16:18, 24 August 2007 (UTC)

As the quote says, the continuum hypothesis states . The equality is predicated on the continuum hypothesis holding, which cannot be proved or disproved in ZFC. — Carl (CBM · talk) 16:35, 24 August 2007 (UTC)

Thanks a lot for the explanation. I added a short comment at the end of the phrase to clarify that the continuum hypothesis can neither be proved nor disproved Paolo.dL 16:45, 24 August 2007 (UTC)

And I've added the necessary qualification "...within standard Zermelo-Fraenkel set theory, even assuming the Axiom of Choice.". Paul August 17:06, 24 August 2007 (UTC)

Thanks a lot :-) (although now it remains unclear whether there exists another context in which it was or can be proved or disproved...) Paolo.dL 17:20, 24 August 2007 (UTC)
Of course there is. Just find a statement equivalent to the Continuum Hypothesis (CH), and add it to ZFC as an axiom. Then CH can be proved in that context. Hccrle (talk) 18:30, 2 July 2008 (UTC)

0.0 0.1 1.0 2.0 1.1 0.2 0.3 1.2 2.1 3.0 4.0 3.1 2.2 1.3 0.4 0.5 1.4 2.3 3.2 4.1 5.0 6.0 5.1 4.2 3.3 2.4 1.5 0.6 0.7 ... 7.0 8.0 ... 0.8 0.9 ... 9.0 10.0 ... 1.9 0.01 0.11 ... 11.0 12.0 ... 0.12 0.13 ... 13.0 etc, etc, etc, a countable direct algorithmic method of counting the reals. This is an isomorphism of the rationals zig-zag argument replacing / by . with the digits of the second integer reversed. Continuum hypothesis proven, cardinality of R is aleph 0. —Preceding unsigned comment added by (talk) 19:15, 10 August 2010 (UTC)

To Your sequence only gets reals of the form n×10m for integers n and m. Thus its image is a proper subset of the rationals. It does not even include one third (1/3). To get all real numbers you have to deal with numbers having an infinite number of non-zero digits to the right of the decimal place. JRSpriggs (talk) 05:50, 11 August 2010 (UTC)

Intuitively acceptable examples about "larger than infinite"

As you perfectly know, a reader who doesn't know this topic can hardly understand how it is possible to create a set with a number of elements "larger than infinite". One example is given in the article ( is "larger" than ), and it first appears intuitively acceptable, but on second thought it conflicts with the fact that the set of even numbers has the same cardinality as .

No it doesn't. and the set of even numbers are two proper subsets of , which have the same cardinality as each other but less than that of R, just as the set whose only member is the USA and the set whose only member is the UK have the same cardinality as each other (1), but less than the cardinality of the set of all nations on Earth, of which they are both proper subsets. No conflict whatsoever. Hccrle (talk) 20:52, 2 July 2008 (UTC)

I am totally ignorant on this topic (and indeed this is the reason why I believe that my comment is important for the authors of this article), but there's a geometric example that would possibly help the readers:

Example: comparing the cardinality of , and

If the above mentioned hypotheses about the cardinality of and were true, this example would be intuitively acceptable, and would even have a nice quantitative approach, showing "how much" larger an infinite set can be than another. :-)

If my hypotheses were not true, the explanation of the reason why they are not true would be also an extremely interesting example in the article.

Do you think that this example is correct? Can it be inserted in the article? What is the cardinality of and ? Please give me some feedback.

Regards, Paolo.dL 20:47, 6 August 2007 (UTC)

The hypotheses are wrong (?), but the article does not explain why

See Cardinal number#Cardinal multiplication. If the axiom of choice holds, then any infinite cardinal times itself gives itself as a product. Also see Space-filling curve. JRSpriggs 17:45, 21 August 2007 (UTC)

Thank you. So:
  1. ...
I am puzzled. Point 3 seems to be conflicting with this sentence, found in section "Comparing sets":
"Two sets A and B have the same cardinality if there exists a bijection, that is, an injective and surjective function, from A to B."
How can we find a bijection between the points on a line and the points on a plane? It seems impossible to me. For each point on a line there are infinite points on the plane! There's something that I do not understand. This concept is counterintuitive. Don't you think that the article is incomplete without some explanation about it, and some intuitive example?
  • If my hypotheses were correct, my intuitive example would be sufficient to explain why.
  • But if they were wrong, then the explanation of the reason why they are wrong would be crucial.
  • As I already wrote, in both cases it is advisable to include in the article an intuitive example.
Paolo.dL 14:30, 24 August 2007 (UTC)

Your intuitive example isn't actually an example. You are looking at a function that is not a bijection (the function that takes all the points on a vertical line to the point on that line on the x-axis, say). You conclude from that that there is no other function that is a bijection, but that conclusion is not valid.

It's easier to see how this can work if instead of looking at "real numbers" you look at infinite sequences of 0s and 1s. Call the set of such sequences S. Since S has the same cardinality as the set of real numbers, we just need to show that S^2 has the same cardinality as S. This means we need a bijection between sequences and pairs of sequences. One such bijection takes a sequence s and returns s_1 - the subsequence of s with all even coordinates - and s_2 - the subsequence of s with all odd coordinates. You can check that is a bijection from S to S^2. — Carl (CBM · talk) 14:41, 24 August 2007 (UTC)

Your example is not clear to me, but seems not relevant, because I am not trying to find a "bijection between a sequence and a pair of sequences". I am trying to find a bijection between a set X and the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y, where X and Y are infinite sets with the same cardinality. I.e., I would like to know whether a function like this is a bijection or not:
(I hope this notation is correct)
Your notation is correct, but your characterization of CBM's bijection is incorrect. It is not a bijection between a sequence and a pair of sequences, it is a bijection between the set of all sequences of reals and the set of all ordered pairs of such sequences, as you require. The sequence s is just an example of a member of the set of sequences, used to describe how the bijection works. The bijection maps s to the ordered pair (s_1, s_2), and it does the same for every other sequence of real numbers. BTW, it is also interesting to notice that this proof does not use the axiom of choice, which the article implies is needed to prove this equality of cardinality. Hccrle (talk) 19:59, 2 July 2008 (UTC)
Sorry, I mistakenly referred to the sequences in CBM's example as sequences of real numbers. Actually, they are sequences of 0's and 1's, and that's what I means to say. Hccrle (talk) 14:42, 2 November 2008 (UTC)
To be even clearer, since bijections imply that domain and codomain have the same cardinality, I would like to know if
where is a Cartesian product.
Yes, it is. Hccrle (talk) 19:59, 2 July 2008 (UTC)

More exactly, I would like readers to be able to find a clear answer to this question and a clear explanation about it in the article. I wrote that "it seems impossible to me" to find such a bijection, but that's not a conclusion. My only conclusion is that the article is incomplete and an intuitive example about this concept is needed, independently of the fact that I am wrong or right. My ultimate purpose is to show that there's a crucial concept that is very much pertinent to the subject of this article and that a generic reader (like me) cannot understand after reading the article in its present version. Paolo.dL 16:18, 24 August 2007 (UTC)

Many things in the theory of infinite sets are counter-intuitive to someone who is only used to dealing with the finite sets of everyday life. One should not reject a notion merely because it is counter-intuitive. That would be an invalid inference. Again, I urge you to read the article on space-filling curves. It gives an explicit method for making a bijection between a line and a plane. What is more, the bijection is even continuous. JRSpriggs 01:15, 25 August 2007 (UTC)

Well, I repeat that I am not rejecting any notion, and not drawing any conclusion. I am just saying that it is of crucial importance to explain the concept with an intuitive example in this article. Don't worry, I did not ignore your message. I have already quickly read the article, but have not found there an explicit answer to my questions; if I had not read it, I would not have written point 3, and the title of this subsection! In my answer to your comment, I am just making clear a doubt, asking questions, asking for an improvement of the article. I am perfectly aware of my ignorance about this topic. By the way, that's why I am asking others to improve the article, rather than doing it myself! Paolo.dL 10:40, 25 August 2007 (UTC)
I have read again the article on space-filling curves, but it does not seem to contain an explanation. It just says:
"Since the Cantor set is homeomorphic to the product , there is a continuous bijection from the Cantor set onto ."
But why is it "homeomorphic"?... I have also read the article on the Cantor set, and absolutely did not find a clear answer. Actually, I did not even understand why you need to use the Cantor set... The article on space-filling curves can only serve as a quick note for somebody who already knows everything. It did not give answers and just created more doubts. Paolo.dL 12:00, 25 August 2007 (UTC)
You're right. The fact that the space-filling curve is a homeomorphism (continuous in both directions), and the Cantor set, are as irrelevant to the discussion of cardinality as your introduction of the lengths of lines (below). It only matters that it is a bijection. Again, I think we can ignore the space-filling curves for now because CBM's bijection above is a much simpler proof that the set of real numbers and the set of ordered pairs of real numbers have the same cardinality. It is not hard to see that a similar proof would apply to the set of all n-tuples of real numbers, where n is any natural number greater than 2. Hccrle (talk) 20:09, 2 July 2008 (UTC)
Again, I have made a misstatement (and I'm not the only one). The space-filling curve is not a bijection, though it is continuous. The article shows how to get a bijection from it, but it is not continuous. There cannot be a continuous bijection between a line segment and a square area, because they are not homeomorphic. Hccrle (talk) 15:35, 2 November 2008 (UTC)

Please explain the trick

Suggested mission. I insist: the concept of "larger than infinite" is not only counter-intuitive, but absolutely unclear. And somewhere, in Wikipedia, there should be a clear explanation. And in this article, at least a summary of this explanation should be included.

I disagree. The article does not use the phrase "larger than infinite". As far as I know, that phrase is not used anywhere in mathematics. That is your phrase. The correct statement is that there are more than one infinite cardinality; some infinite cardinalities are larger than others. To say that cardinality A is larger than an infinite cardinality B is not to say that A is larger than infinite. A and B are both infinite, but one is larger than the other. And I think that concept is quite clear and it is explained in the article. Hccrle (talk) 15:35, 2 November 2008 (UTC)

Starting point. The first step for finding or describing a clear solution is a clear specification of the problem. My geometric example is a good starting point. Please clearly explain the readers how you can map bijectively a set () from a proper subset of it ()! Can you see how clearly this example highlights the problem? Since you can do that magic, then you should explain the "prestige" [I mean the "trick" (note added at 9:48 27 Aug 07)]. Wikipedia is the place where the public is supposed to find that explanation. And if possible, don't tell the readers that they first need to understand the Cantor set, because this seems to me a way to make the problem even more complex. For instance, the article on 0.999... gives a clear explanation of a very counter-intuitive concept.

3 iterations of the Peano curve, a space-filling curve

Variants of the starting point.

  1. A simplified version of my "starting point" would be the comparison between the points in a line and the points in a segment of that line. Do they have the same cardinality?
  2. Also, the infinite length of a Peano curve (see figure; thanks JRSpriggs for suggesting that article) seems to be larger than the finite length of the side of the square (I am not sure of anything anymore :-). However, the article on space-filling curves seems to suggest that they contain the same number of points. Is this true?
Yes to both questions. The Peano curve, having infinite length, is obviously longer than the side of the square it fills, but the number of points is the same. Hccrle (talk) 15:35, 2 November 2008 (UTC)

I guess the answer is yes in both cases, but I am groping in total dark at the moment. However, whatever is the answer, can you explain why in the simplest possible way?Paolo.dL 21:11, 25 August 2007 (UTC)

An additional counter-example is also needed. What set has cardinality larger than ? I guess there must be one, otherwise what's the purpose of the infinitely many aleph numbers? This is a second important knot that the article fails to untie. Paolo.dL 13:04, 25 August 2007 (UTC)

See Beth number#Beth two. Why should I explain a popular film? What has that to do with this subject? If you want your questions answered, I suggest that you ask one short relevant question at a time. No one wants to deal with your flood of irrelevant stuff. Try reading a book or taking a course in this before you bother us. JRSpriggs 00:58, 27 August 2007 (UTC)

This is a huge misunderstanding. Prestige means trick. It is what an illusionist does not want to explain, but that an encyclopedist should explain. And I am not implying that mathematics is an illusion, I am only maintaining it appears magic in this case, which is the same as saying what you already admitted: it is counter-intuitive. About "try reading a book...", this is the answer you give to someone who explicitly declared that this is not his field (please read the second sentence of this section, for instance).

Those who don't like to explain basic concepts are free not to do it. Moreover, they are free to ignore user feedback about articles which should be written for users, rather than for the mathematicians who are able to edit them. On the other hand, I am a user and I am free to provide feedback to those who are willing to receive it. I am tired of repeating that I don't want a personal answer, but a better article, where readers can find an explanation of a crucial concept rather than being forced to go to a library and browse paper books (please read the very first paragrah of this subsection, and the title of the previous subsection). Paolo.dL 11:04, 27 August 2007 (UTC)

Summary of suggestions

Let's be constructive. I gave several suggestions, that's true, but they are all about the same concept, which is indicated by the title of this section. In sum:

1) Please explain in this or in a separate article, as clearly and as simply as possible, why something which appears "larger than infinite" or "smaller than infinite" (please forgive this purposedly loose terminology; I mean greater or less than ) is actually not such. This might be done by comparing:
See also Sets with cardinality .
2) Then (and this is the other face of the same coin) explain how you can obtain a set "larger than infinite". This was my initial suggestion. Paolo.dL 10:11, 27 August 2007 (UTC)

Answer to point 2. JRSpriggs indirectly suggested this answer: "by building the power set of an infinite set such as , i.e. the set of all its possible subsets." I think this is the simplest possible answer, and it is intuitively acceptable.

About point 1. Finding a simple answer to point 1 seems to be much more difficult. Of course, explaining just one of the suggested comparisons is enough to understand them all. If possible, don't tell the readers that they first need to understand the Cantor set, because this seems to me a way to make the problem even more complex. For instance, the article on 0.999... gives a clear explanation of a very counter-intuitive concept. I know it is difficult, but it is also very useful. Paolo.dL 11:55, 27 August 2007 (UTC)

Simple examples

Consider the function f(x) = 2x. This function is clearly a bijection from R to R. Thus this shows that, for example the interval [1, 2] has the same cardinality as the interval [2, 4]. This idea can easily be adapted to show that any two intervals have the same cardinality. Given that any two intervals have the same cardinality, it is not hard to see that [0, 1] has the same cardinality as R. Paul August 17:24, 27 August 2007 (UTC)

One can look at y = tan(x) restricted to a single branch to get a bijection from an interval to the real line. There are rational functions that have the same property. It's simpler to use open intervals, rather than closed ones. — Carl (CBM · talk) 17:32, 27 August 2007 (UTC)
:-) Wonderful! This is very appetizing food for thought! Is that written somewhere in Wikipedia already? Do you think a new page should be created containing the best (simpler) possible formal prove of this "magic", together with these simple and intuitive examples? This page (e.g. Greater than infinite) may include a brief summary of and a link to Cantor's diagonal argument, and the above mentioned "Answer to point 2". Paolo.dL 18:06, 27 August 2007 (UTC)

Tentative conclusions

:-) I found almost all the needed information in Infinity#Set theory and Infinity#Cardinality of the continuum. I completed the latter section, according to what we concluded. Please see if you like it. I believe that the same stuff should be included in this article. Paolo.dL 12:37, 28 August 2007 (UTC)

:-) :-) I added and refined a section called Infinite sets. Although I refined it with care, it is just offered as a starting point. Of course, you are free to edit it as you like, or delete it. Paolo.dL 13:37, 28 August 2007 (UTC)

Thanks to JRSpriggs for his edits. Paolo.dL 09:03, 29 August 2007 (UTC)

Too difficult navigation in the articles about Set Theory

Template:Views You probably know that I have been studying for weeks the articles about infinite cardinality and infinite sets, desperately seeking information about the above mentioned point 1. However, I never suspected the existence of the pages finite set and infinite set! The navigation through the articles related to set theory is quite difficult. It was not so much difficult for me to study other topics in Wikipedia. An index added to each article would guide the reader. An alphabetically sorted index might be generated based on page category. However, an index manually compiled and sorted "by content", rather than alphabetically, would be much more useful (see the template "Views" included, for instance, in perspective projection). Again, unfortunately this is something I cannot do because this is not my field (sorry). Just a suggestion... feel free to ignore it. Paolo.dL 09:49, 29 August 2007 (UTC)

Have you tried using the category system? The articles relevant to your area of interest are mostly in Category:Cardinal numbers. See Help:Category and Wikipedia:Categorical index. Each article may be in one or more categories listed at the bottom of the page. Click on one of them and it displays a list of articles with some feature in common with the article from which you came. JRSpriggs 20:03, 29 August 2007 (UTC)

I have tried. But, as I wrote,

  • It was not so much difficult for me to study other topics in Wikipedia,
  • An article containing Foundational issues about "infinite set theory" was not included in the corresponding category! (See next section.)
  • The categories and their contents are not sorted by content. They are sorted alphabetically.

And I add now:

  • The categories overlap.
  • I was thinking to something organized like the index of a book (e.g. the template I included on the right). It would be much more useful.

Again, consider that I am a user who knew almost nothing about infinite cardinality, before reading the relevant articles on Wikipedia. Wikipedia is written by those who know for those who don't know. Since the first ones cannot easily imagine how difficult it can be for the second ones to receive what they want to transmit, I believe that user feedback is precious and this is why I provide it. Paolo.dL 10:07, 31 August 2007 (UTC)

Foundational issues

After weeks of navigation in Wikipedia (see above), I have found the section Foundational issues, in the article finite sets. This interesting section introduces infinite set theory, but the article finite sets is not even included in Category:Basic concepts in infinite set theory!

There are at least three possible places where this paragraph could be:

  1. in a new separate article, such as, for instance, Introduction to infinite set theory;
  2. right here, in Cardinality;
  3. in Axiomatic set theory
  4. in Infinite set (see suggestion by JRSpriggs below)
  5. just where it is now.

I strongly feel against option 5. I was looking for this information for weeks, and couldn't find it!!!.

I vote for option 2, because Cardinality is the only basic article (as far as I know) where you can find a summary about Finite, countable and uncountable sets. Paolo.dL 10:07, 31 August 2007 (UTC)

How about putting it into infinite set and naming the section "Introduction to infinite set theory"? That article is already the lead article of "Basic concepts in infinite set theory". And we could have a redirect from "Introduction to infinite set theory" to the section. JRSpriggs 02:17, 1 September 2007 (UTC)
I am going to argue strongly for option 5. The discussion in finite sets is about foundational issues with finite sets. A lot of it is a discussion of foundations for finitism. Definitions of Dedekind and Kuratowski finiteness are definitions in the theory of finite sets. This has more to do with finite sets than it does with general cardinality theory (which typically assumes ZFC, in my experience). And it is primarily about finiteness, rather than infinity. To discuss "finiteness" only on a page entitled "infinity" is a bit absurd.
What exactly were you looking for? This section covers various different topics.
Whatever happens, I agree that cross references should be made in the other related articles. All the best, Sam Staton 09:01, 1 September 2007 (UTC)

Yes, the section deals mainly with finiteness, but it also represents a nice introduction to a definition of infinite sets, because infinite sets are defined as those that are not finite. Thus, in my opinion, it should neither be in finite set nor in infinite set, although both articles can easily refer to it. Here's its initial sentence [I formatted in bold the central concept]:

"Georg Cantor initiated his theory of sets in order to provide a mathematical treatment of infinite sets. Thus the distinction between the finite and the infinite lies at the core of set theory."

Notice that the articles finite set and infinite set are both very difficult to find! I found them only after weeks of navigation, and just because JRSpriggs kindly linked to these pages some words contained in the new section that I have recently added to Cardinality! One expects to find the distinction between finite and infinite in a generic and introductory article (e.g. Axiomatic set theory or Cardinality). Not in a specific article on finite sets! By the way, I added a new point in the list, according to suggestion by JRSpriggs. Paolo.dL 17:46, 1 September 2007 (UTC)

I'm still confused. The material in this section does not seem out of place on the finite set page. I've not got a problem with you putting information on other pages. There could be some duplication in content, this is not a problem.
The section, as it stands, is a mixed bag of lots of different foundational aspects. (It could perhaps be a bit better organised.) I think you are only interested in the first two paragraphs of this section, in any case. Am I right?
Another thing. Just because you found it hard to find this section doesn't mean it must be moved. Instead, you should include links in other articles. All the best, Sam Staton 11:18, 2 September 2007 (UTC)

You wrote "Just because you found it hard to find this section...". This is not at all the reason I gave. The reason is this: "One expects to find the distinction between finite and infinite in a generic and introductory article...". I am not defending a personal interest.
You also wrote " should include links". The links are there, but a user interested on infinite sets never clicks on the link Finite set. That article is not even included in Category:Basic concepts in infinite set theory! Paolo.dL 08:51, 3 September 2007 (UTC)

To make our work simpler, I suggest to split it in two parts. I believe two separate decisions are required:

  • First, we should decide whether it is necessary or not to include some foundational issues in some other article.
  • Then, if the answer is yes, we need to decide whether to copy or move or write from scratch (or ...) the new section or article.

If this method is acceptable for you, please specify your preferences accordingly, using the two subsections I created below. Otherwise, just keep posting in this section (right below this comment). Thanks, Paolo.dL 17:03, 3 September 2007 (UTC)

Paolo, first, please can you clarify: which parts of the Foundational issues section are you proposing to move? The first two paragraphs are about finite set theory; the third and fourth are about different kinds of set-theory (and perhaps a little out of place). The remainder is about the intricate distinction between two notions of finiteness, due to Dedekind and Kuratowski. Thank you, Sam Staton 09:57, 4 September 2007 (UTC)
As I wrote below, I vote for moving the entire section [or leaving it where it is and inserting a summary in Cardinality]. No part of that section seems out of place if the place is a general introduction. See the explanation I added below right now. However, consider that I am just a reader who, before reading some articles on Wikipedia, knew hardly anything about the distinction between finite and infinite. I can only say that what I read in the above mentioned section appeared to be introductory, and therefore seemed to deserve a more visible place in a less specific article. Paolo.dL 14:23, 4 September 2007 (UTC)
I hope that some of the main authors of the articles on set theory (e.g. Cjrs 79, Paul August, Oleg Alexandrov, Toby Bartels, Revolver and many others) will share their opinion. In this case my opinion counts for little with respect to theirs. Paolo.dL 13:35, 6 September 2007 (UTC)

Opinions about first decision

Is there the need to include some foundational issues about the "distinction between the finite and the infinite" in one of the basic and most general articles related to set theory (other than Finite set)? (NOTE: a positive answer to this question does not imply that you accept to delete or move or copy section Finite set#Foundational issues). If the answer is yes, then

(a) What is the article where these issues should be? (e.g., see points 1-3 above)

I believe that these foundational issues should be included in Cardinality, because Cardinality is the only basic article (as far as I know) where you can find a summary about Finite, countable and uncountable sets (see above for more details about my rationale) Paolo.dL 16:49, 3 September 2007 (UTC)

Opinions about second decision

Should these issues be:

(b1) written from scratch? or
(b2) copied from Foundational issues? or
(b3) moved from Foundational issues? or
(b4) copied or moved from somewhere else? or
(b5) some combination of b1, b2, b3, b4 (e.g. partially copied and partially written from scratch)?
(b6) a short summary of Foundational issues, including the warning {{Main|Finite set}}? (in this case Foundational issues stays where it is, i.e. in Finite set)

I vote for b3, but a short summary with a link to the moved section is then needed both in finite set and infinite set. I believe that all of the parts of Foundational issues are interesting as a general introduction to the general theme "distinction between the finite and the infinite". It is nice to know that there are "other kinds of set-theory" and different notions of finiteness, which imply different notions of infiniteness (see latest comment by Sam Staton). Paolo.dL 14:23, 4 September 2007 (UTC)

I added another possible solution (b6), which seems to be a more conservative and at the same effective compromise. I propose to give the title "Distinction between finite and infinite" to the summary. Paolo.dL 14:49, 7 September 2007 (UTC)

Equivalence class under equinumerosity

There is a definition in the article that defines cardinalities as equivalence classes under equinumerosity. That would mean creating equivalence classes on the proper class of all sets. But the linked article about "equivalence classes" only talks about equivalence classes on sets. So, is it possible to define equiv.classes on proper classes just like that (assuming neuman, bertray, and the other guy) or is there some trickery at work?

You took the words right out of my mouth! But actually, the equivalence classes under equinumerosity (I'm used to the word 'equipolence') are proper classes whether you are dealing with sets or classes. (Indeed, you can only talk about classes of sets, because proper classes, by definition, are not permitted to be members of any class.) Even the number 1, the class of all singletons of sets, is a proper class, because its union is the class of all sets. Hccrle (talk) 20:30, 2 July 2008 (UTC)

I find the set of articles about set theory to be quite a jigsaw puzzle with missing pieces. —Preceding unsigned comment added by (talk) 17:51, 10 January 2008 (UTC)

Cardinality strictly greater than

"Cantor's generalized diagonal argument shows that which implies . Furthermore ."

This sentence was recently added at the end of the section "Cardinality of the continuum". Is it correct? It uses the symbol as if it were a set. The same symbol is used in this section to indicate the cardinality of the continuum. Paolo.dL (talk) 18:35, 20 March 2008 (UTC)

To Paolo.dL: Thank you for pointing out this problem. I fixed it. JRSpriggs (talk) 06:52, 21 March 2008 (UTC)

Simplifying last paragraphs in section "Cardinality of the Continuum"

This paragraph was recently added to the section "Cardinality of the continuum"

"The cardinal equality can be demonstrated using cardinal arithmetic: This argument is a condensed version of the notion of interleaving two binary sequences: let be the binary expansion of and let be the binary expansion of . Then , the interleaving of the binary expansions, is a well-defined function when and have unique binary expansions. Only countably many reals have non-unique binary expansions."

I believe that this paragraph is interesting, but too detailed for the section "Cardinality of the continuum". Moreover, it uses terminology and notation that only mathematicians can understand (believe me). This section should only summarize the contents of the "Main article" about the same subject. I propose to delete this paragraph and modify the ensuing paragraphs of this section as follows:

Cantor also showed that sets with cardinality strictly greater than exist (see generalized diagonal argument). They include, for instance:
  • the set of all subsets of R, i.e., the power set of R, written P(R) or 2R
  • the set RR of all functions from R to R

Both have cardinality (see Beth two).

The cardinal equalities and can be demonstrated using cardinal arithmetic:

The contents of the deleted paragraph can be integrated, if necessary, into the main article. Paolo.dL (talk) 11:53, 21 March 2008 (UTC)

I carefully implemented the changes described above, to make this excellent section even more easily readable. I also added a link to Cantor's theorem and reference to Beth number#Beth one. Moreover, I moved the above-mentioned paragraph to the main article, including the format changes recently suggested by Xantharius. Then, I inserted in this article a link to the section where the paragraph was moved (Cardinality of the continuum#cardinal equalities). So, no information is lost, and at the same time this section is, in my opinion, more accessible to laypersons. Paolo.dL (talk) 13:50, 30 March 2008 (UTC)

Number sign/"hash" symbol

How common is "#" as a cardinality function? I seem to remember it being used, i.e. #{1,2,c} = 3. (talk) 15:51, 3 April 2008 (UTC)

Page In General

Seems needlessly complicated. I think an introductory section on finite cardinals should be there. I understand we're all into infinite sets, but this should have some more info for people entirely unfamiliar with set theory. Erdosfan (talk) 02:42, 14 April 2008 (UTC)

I do not agree that this article is needlessly complicated. I am not a mathematician, and I believe this page is well written and contains useful and interesting information. And it is an effective introduction to more detailed pages. However, I agree that a new section on finite cardinals might be useful. Paolo.dL (talk) 12:58, 14 April 2008 (UTC)

format of aleph symbol

I believe that the symbol ℵ is too thin and too difficult to read (at least with Internet Explorer 7 in Windows XP, which, as far as I know, is the most commonly used combination of browser/operating system). It looks like a badly written R. I suggest to substitute it, throughout the article, with the math version . This is slightly too large, but at least its shape can be more easily recognized. Please let me know if you agree. Paolo.dL (talk) 20:19, 26 May 2008 (UTC)

OK. I agree with your reasoning. But I expect that someone else will eventually revert your change. So do not be surprised; this flip-flop in notation has happened before. JRSpriggs (talk) 01:12, 27 May 2008 (UTC)
Thanks. Let's wait for at least another week. May be others will let us know their opinion. Paolo.dL (talk) 10:27, 27 May 2008 (UTC)
It looks good from where I'm seeing it (I'm using Firefox on a Mac). For in-line use the alefsym is, in my opinion, more desirable because it doesn't disrupt the line spacing of surrounding lines, which using a Latex-PNG does. From my reading of the Wikipedia Mathematics Manual of Style, it recommends that in-line math should be done in HTML if possible. Xantharius (talk) 17:49, 27 May 2008 (UTC)

I have tried with Firefox on Windows XP and Vista. It is even worst than with Internet Explorer (see above). I can see α (obtained with &alpha), but ℵ (&alefsym) looks like a question mark within a rectangle. Can we assume that what I see, using the most commonly used operating systems and browsers, is what most readers will see? Xantarius uses Firefox on a Mac (therefore OSX, an excellent operating system unfortunately used by a relatively small percentage of people). Do we agree that the general rule given in the Manual of Style is less important than the interest of most readers to be able to read the symbol? Paolo.dL (talk) 19:25, 29 May 2008 (UTC)

I think the problem is that the Arial font doesn't have &alefsym (which is unicode 2135), so IE is doing something strange with it. I don't object to changing to inline maths. But a better option might be to use Template:IPA, which gives by using something like Arial Unicode MS, depending on the OS and the fonts installed. Strangely, Template:Unicode gives the nasty aleph back; I'm not sure which font is doing it. A second alternative is to use the Hebrew letter א, which Arial does have but which is also a bit too small. Sam (talk) 12:01, 30 May 2008 (UTC)

The only problem with IE is that &alefsym is by far too thin, therefore it is deformed by quantization error (aliasing) when displayed using standard page size. But if you magnify the page, you can see that it is indeed an aleph. On the contrary, I confirm that the IPA version of &alefsym () appears well readable in IE on Windows Vista. Thank you for the suggestion, Sam. If nobody will disagree, in the next week I will substitute it for the standard &alefsym (ℵ). Paolo.dL (talk) 15:28, 30 May 2008 (UTC)

My only worry about IPA is that this is abusing the IPA template, isn't it? (PS: Further research shows that the &alefsym that IE gives me comes from the "MS Gothic" font, which I think is a font for Japanese characters. It's hardly surprising that it's maths symbols aren't so carefully crafted.) Sam (talk) 16:24, 30 May 2008 (UTC)
Since our purpose is to fix a bug, I would call it "using", rather than "abusing" IPA, unless there's a better solution (PS: Gothic is not Japanese). Paolo.dL (talk) 11:13, 31 May 2008 (UTC)

I just tested the IPA version with Firefox on Windows XP. It looks good. Surprisingly, the standard &alefsym (ℵ) looks good in this version of the browser; it looks exactly like the IPA version! On the contrary, just two days ago I tested Firefox and it behaved the same as IE. Paolo.dL (talk) 11:26, 31 May 2008 (UTC)

OK. Probably the best thing would be to make a new template for this purpose, rather than using IPA. But it's probably not worth the hastle. (Re Gothic/Japanese: I understood this from East Asian gothic typeface...) Sam (talk) 11:47, 31 May 2008 (UTC)

If somebody disagrees about using IPA, please post a comment. (Re MS Gothic: thanks for explaining, Sam). Paolo.dL (talk) 12:32, 31 May 2008 (UTC)


The "ordinals" under "cardinal numbers" does not link directly to ordinal numbers. Thehchl (Thehchl) 11:56, 16 April 2009 (UTC)

Thank you for pointing that out. I have fixed it. JRSpriggs (talk) 18:52, 17 April 2009 (UTC)

|R^n| = |R^1|

The fact that the cardinality of an R3 space is the same as the cardinality of the reals is included in the discussion of the continuum hypothesis, but I don't think that it depends on the continuum hypothesis. It seems like they have equal cardinality simply because you can list each of the dimensions in an R^n space to make it fit in an R^1 space.

So if you guys don't have a problem with it, I'd like to include that as an example in the section on equal cardinalities. When I first learned about cardinality, I thought that it was a very interesting result and I'd imagine that people reading this article will feel the same way. —Preceding unsigned comment added by Zoid62 (talkcontribs) 18:13, 16 June 2009 (UTC)

The article already states "Cardinal arithmetic can be used to show not only that the number of points in a real number line is equal to the number of points in any segment of that line, but that this is equal to the number of points on a plane and, indeed, in any finite-dimensional space.". The "discussion of the continuum hypothesis" is just one short paragraph and does not include the above sentence. So I think you are misreading the article. JRSpriggs (talk) 18:34, 16 June 2009 (UTC)


“The equivalence class of a set A under this relation then consists of all those sets which have the same cardinality as A”…………I doubt if there is such an equivalence "class", because the equivalence class (by its definition in Wikipedia) is a set while here it seems to be a proper class. --虞海 (Yú Hǎi) (talk) 17:55, 30 September 2010 (UTC)

An equivalence class does not have to be a set; it may be a proper class. Wikipedia is not a reliable source. Also the article on equivalence class says "given a set X and an equivalence relation ~ on X ...". So that definition does not apply when X is a proper class. JRSpriggs (talk) 08:45, 1 October 2010 (UTC)
But such writing destroys the internal consistency of Wikipedia. --虞海 (Yú Hǎi) (talk) 17:32, 1 October 2010 (UTC)
We try to be consistent within each article, but trying to maintain consistency within Wikipedia as a whole is a fool's errand. JRSpriggs (talk) 20:23, 1 October 2010 (UTC)
Yes, but we must maintaining consistency within one and its direct internal links, because an internal links brings the reader to the definition of the term used in the article. --虞海 (Yú Hǎi) (talk) 10:53, 4 October 2010 (UTC)
In order not to confuse the reader, I temporarily created a disambiguation page and changed the link. --虞海 (Yú Hǎi) (talk) 10:59, 4 October 2010 (UTC)
I reject that approach, as well. There are a number of formalisms in which the equivalence class defined here can be used, and the difference between that and the conventional equivalence class is meaningless in almost all of those formalisms. — Arthur Rubin (talk) 14:55, 5 October 2010 (UTC)

Cardinality formulas

May I ask why the formulae to calculate the cardinality of intersections and unions ware “inappropriate”? They were completely general, but have been reduced to a simple corollary for disjoint sets only. Why is it not appropriate to be able to calculate cardinality when the article is about cardinality?

Maschen (talk) 13:56, 2 June 2011 (UTC)

It might have been more appropriate at Algebra of sets which deals with unions and intersections in more detail. There were several problems with the style. We do not usually include proofs in articles, and your proof appeared to be invalid as written. Also the general formulas are not such that they would be of general interest — how often is one going to know the cardinalities of all the sets on the right hand side and not already know the cardinality on the left side? And your formulas were stated in such a way (i.e. using subtraction) that they cannot be applied to infinite sets which are the main subject of the article. JRSpriggs (talk) 09:31, 3 June 2011 (UTC)

Perhaps they would be for theoretical interest, not all formulae are readily useful in practice, but fair enough... thank you for your feedback. Maschen (talk) 14:12, 3 June 2011 (UTC)

Cantor–Bernstein–Schroeder theorem

The Cantor–Bernstein–Schroeder theorem should probably be mentioned somewhere or other. The (in my opinion) key bit of trichotomy, |A|<=|B| and |B|<=|A| implies |A|=|B|, is that theorem, and doesn't require the axiom of choice. I suppose without the axiom of choice we may have two sets, neither of which is comparable to the other in terms of cardinality? (talk) 05:39, 17 July 2011 (UTC)

Your supposition is correct. In fact, the statement that all (pairs of) sets have comparable cardinality is equivalent to the axiom of choice. — Arthur Rubin (talk) 07:52, 17 July 2011 (UTC)

Relationship to ISO 31-11

The ISO_31-11 page list the function card to indicate cardinality. Should that form not get a mention here? Robbiemorrison (talk) 18:36, 5 February 2013 (UTC)

Seems reasonable. I have added the notation to alternatives listed in the lead. Thanks, --Mark viking (talk) 18:47, 5 February 2013 (UTC)