Last time I talked briefly about pretend mathematicians. Y’know, people who’ve actually never studied the stuff they’re claiming to refute. Because “common sense” tells them it’s wrong. And “common sense” is, as we all know, the guiding principle of mathematics.

So this time I’ll actually get into cardinality and infinite sets a bit.

First, a preface. Infinity, as it is defined mathematically, is not an object of any kind. It’s not a number. It’s not a set. So what is it?

As it relates to calculus, infinity is a limiting principle. To avoid a rigorous discussion, it’s best to look at it through an example. Take an everyday function like . We write:

This notation reads: The limit of as x goes to infinity equals the limit of as x goes to infinity equals infinity. In other words, we’re asking the question: If x were to never stop getting larger, what would happen to the function ? In this case, the function itself would never stop getting larger either. So we write that its limit is infinity.

Now let’s stop here for a second to clear something up. Infinity still is not a number. This is a notation that mathematicians use for convenience. It’s understood that when a limit of a function equals infinity that that function does not have a limit, not that its limit is actually a number called “infinity”. In more technical terms, the function is said to **diverge**.

The second way in which infinity is used in mathematics is in regards to sets, specifically the number of elements of a set. If you’re not familiar with the term, a **set** is just a collection of things.

The notation goes as follows. Say you have a set of the numbers 3,4,5, and 6. We would write the set as , or for convenience, . An object is an element of a set if is itself a set and if it is “inside” of . may also be referred to as a **subset** of . Subsets of are considered elements of , not . So at the very least, , and it has one element. could have more elements; at the very least, it must have in there.

The example in the previous paragraph is of a finite set. A set is **finite** if it has finitely many elements. Basically, it just means that if you started counting the number of elements, you would eventually finish. Now we’ll introduce the concept of cardinality. A **cardinality** describes the number of elements of a set. The set has a cardinality of 4, because it has 4 elements. Quickly we can see that if a set has cardinality that is a natural number, then it is finite. (Refer to the math symbols page if you don’t know what natural numbers are).

So what does an infinite set look like? Well, a set is infinite if it’s not finite. Pretty simple. But it gets a bit more complicated. This is where intuition and common sense may fail you if you aren’t careful.

Take the set of natural numbers. Clearly this set is infinite, because for any number that you give me, I can just add another natural number to it and get a bigger number. It has another property which is quite obvious, but turns out to be significant. No matter what element you choose from , I can tell you at what position your element lies in the set. So if you choose 2,044, I know the number is the 2,044th element of the set. In general, the natural number is the element of the set .

For this reason, is called **countably infinite**. It may have an infinite number of members, but no matter what member you may pick, I can tell you at what position it lies in the set. So let’s call the cardinality of this set . This is simply a notation, not a number.

So let’s talk a little bit about a different set. Let’s call it . is the set of all even natural numbers. You can clearly see that this set is also countably infinite. If you give me any element in the set, I know its position is . So, for example, 2 is the first element, 4 is the second, 6 is the third, etcetera.

But how does compare to ? It may seem at first glance that is “bigger” than , because is a subset of . First, remember that these sets are both infinite, which should tip you off that common sense might fail you this time. Second, remember that we’re not necessarily concerned with the values of each element, but with the *number* of elements in total. How can we prove that and actually have the same cardinality?

Let’s take each element of and pair it with a unique element of . If we can do this for every single element of and , they must have the same number of elements. So define a function , where is any natural number. This does exactly what we wanted to do, because no matter if a natural number is even or odd, multiplying it by 2 makes it even. And we can see that each element of one set has a unique partner from the other. We can see that if one element of either set had to pair with two partners to make things fit that the other set would be the bigger set.

It’s easy to see, then, (or prove) that every countably infinite set has the exact same cardinality. The set of odd natural numbers. The set of integers. The set of primes. All of them.

It gets trickier though. Let’s consider the set of real numbers . is the set of all rational and irrational numbers. So it includes everything from the integers to fractions to numbers like that have infinitely many digits.

How does compare to ? Well is clearly a subset of . But, as we know, that doesn’t mean they don’t have the same cardinality.

Remember that our special property from countably infinite sets was that we knew at what position every element lay in the set. Let’s simplify things a bit and only take the set of nonnegative real numbers. Well, we know what the first element of the set is. It’s zero. What’s the next greatest element? Is it .01? No, because .001 is greater than zero but is less than .01. But .0001 is greater than zero and less than .001. And so on and so on. We can quickly see that no matter what “second element” you pick, I can find a smaller one that’s still greater than zero. Aside from the first element, then, asking about the “position” of an element in is meaningless. is what’s called **uncountably infinite**.

So let’s look at a smaller set, the set of real numbers between and including 0 and 1. We’ll denote that as [0,1]. Clearly [0,1] has a first element and a last element. But [0,1] is still uncountable. It’s still meaningless to talk about the “second element” or the “third element” of [0,1]. Okay, so it’s uncountable, but is it infinite? Well yeah, it is. Let’s take a subset of [0,1], and call it (0.5,0.7). So this is the set of all numbers between 0.5 and 0.7, not including 0.5 and 0.7. This set doesn’t even have a first or a last element. 0.5 isn’t in the set. So what’s the first element? 0.50000001? Well 0.500000001 is less than that, but still greater than 0.5. We arrive at the same conundrum. So we see that we can create infinitely many numbers in this interval (0.5,0.7). No matter what two different numbers in the interval you pick, I can find a new number between those numbers.

Clearly if (0.5,0.7) has infinitely many elements, then so does [0,1]. So [0,1] is uncountably infinite as well. Thus, is uncountably infinite. You can extend this reasoning and show that the set of real numbers [0,1] and [0,2] have, seemingly paradoxically, the same cardinality. You can then show that and any interval subset of have the same cardinality.

This seems unbelievable, but it’s true. I’ll do the first example. We need to pair every element of [0,1] with an element of [0,2]. Well, we can just use the same function we used before, . For a quick check that this works, note that the midpoint of [0,1] corresponds to the midpoint of [0,2]. .

Now, you should keep in mind that we’re still talking about the number of elements of the set, not the values. It’s easy to forget that. Yes, the interval [0,1] has a finite length. It’s just 1-0=1. We’re concerned about the number of elements in the interval, not the difference between the first and last elements.

So how can we compare and ? Well, every interval subset of has infinitely many elements. Every interval subset of , on the other hand, has finitely many elements. Clearly, then, is much bigger than . In other words, the cardinality of is less than the cardinality of . We denote the cardinality of as and say that . (Note that this is a cardinal, not an arithmetic, ordering; isn’t a number, remember).

So I hope that was understandable. I tried not to use so much jargon. If you have any questions, comments, responses, you know what to do. Next time we’ll talk about the continuum hypothesis and sets with even bigger cardinalities!

Posted by mindloop on July 31, 2007 at 8:04 pm

Some technical annoyances I have…

(A)

You seem to be confusing an element and a subset. An element is a singular part of the set. For example, 3 is an element of {3,4,5} (a set of numbers). Four and five are the other two elements. An element is not necessarily a set. 3,4, and 5 are not sets but numbers. None of these are subsets. But {3}, {4}, and {5} are subsets. So are {3,4}, {4,5}, {3,5}, and {3,4,5} (the last is not a ‘proper’ subset).

Now suppose we take {{3},{4},{5}} (a set of sets of single numbers). {3} is an element, and so are {4} and {5}. None of these are subsets; they are elements. But {{3}}, {{4}}, and {{5}} are subsets. The others are {{3},{4}}, {{3},{5}}, {{4},{5}}, and {{3},{4},{5}} (the last not being a proper subset).

(B)

You explained countable infinite well, but not uncountable infinite. You referenced that between any two real numbers there is another, but this does not mean that the real numbers are uncountably infinite. What you noted is that the reals are what is called a “dense” set. The rational numbers are also a dense set (in fact your examples of 0.1, 0.01, 0.001, … are all rational numbers). Yet these are countably infinite. You are confusing countability with countable orderability.

To truly prove R’s uncountability, you need something like Cantor’s diagonal argument.

(C)

[ack… I have to leave now! will finish small bit later!]

Posted by Jon on July 31, 2007 at 9:45 pm

(A)

You’re right. I was a bit careless with the notation. I’ll fix that. As for the difference between {3,4,5} and {{3},{4},{5}}, it seems like a difference between our educations. I was taught that the former notation was convenient for expressing the latter, as numbers can be thought of as discrete sets with single elements. You can then set up arithmetic via unions, complements, and intersections. It’s really a pedantic difference for the purposes of this blog.

(B)

My main argument for the uncountability of was that you cannot associate position with its elements, not that it is dense. This is effectively what Cantor’s diagonalization argument shows. With , as you mentioned, you can. And I did use as an example; they weren’t all rational numbers!

(C)

Looking forward to it. 🙂

Posted by khuram on August 1, 2007 at 6:24 am

John

So I am successful at least in that I never studied the stuff but still caused this hi fi discussion to take place:-)

Anyways, sometime before, another person had raised similar objection on me. My reply was that, “yes! I read less and think more.”

Right now I am in Office and my home computer is also out of order. So my detailed reply is due at any convenient time. What I can say for the moment is that none of your points is against any of my points. Like you, I also don’t treat “infinity” as any “number” or so. My article on this topic discusses two types of infinity which are (i) Never Ending and; (ii) Never Happening.

For details, see main article on following link:

http://khuram.wordpress.com/2007/05/06/some-points-about-nature-of-infinity/

Secondly,I also don’t disagree with your following proof:

“It’s easy to see, then, (or prove) that every countably infinite set has the exact same cardinality. The set of odd natural numbers.”

My article was NOT talking about the issue of cardinality comparison of super and sub-sets.

My article is talking about the issue of cardinality of smaller and larger PHYSICAL lines.

What I say is that REAL numbers exist only in abstract mathematical relations. My further point is that REAL numbers don’t exist in the dimensions and sizes of PHYSICAL OBJECTS.

And my main point is that a finite

physicalline must be having finite numbers of individual points in it.Thirdly, you have not addressed to my criticism on the concepts of geometry; like concept of “point” and concept of “line”. My outstanding question is that how linier combination of “spaceless” points can result in a non-zero length but “widthless” line …???

With reference to your point on “minloop” blog … that my article contains “no math” …

Yes … I am not mathematician. I want to employ common sense methodology and terminology. I don’t believe in absolute accuracy of mathematics and I believe that sometimes common sense can be right and mathematics wrong!

Regards!

Posted by mindloop on August 1, 2007 at 12:56 pm

Okay, I’m back. (And ready to finish reading your post!) Also, I see you avoided the epsilon-delta notation to keep it simple 😉

(A)

I am following what I learned in my education in this case, but I learn most of my math online before the classroom and of what I learned of set theory online, there is a difference between the number 3 and the set {3}. So it actually makes sense to refer to {2,{2}} in such a formulation, for example. I suspect that the way you learned it isn’t the generally accepted standard. (But don’t think of me as a standards-nazi, I realize we’re basically cutting hairs by arguing this :D)

(B)

Perhaps you understand it correctly, but I do not think you expressed it correctly in the post.

“How does R compare to N? Well N is clearly a subset of R. But, as we know, that doesn’t mean they don’t have the same cardinality.

Remember that our special property from countably infinite sets was that we knew at what position every element lay in the set. Let’s simplify things a bit and only take the set R+ of nonnegative real numbers. Well, we know what the first element of the set is. It’s zero. What’s the next greatest element? Is it .01? No, because .001 is greater than zero but is less than .01. But .0001 is greater than zero and less than .001. And so on and so on. We can quickly see that no matter what “second element” you pick, I can find a smaller one that’s still greater than zero. Aside from the first element, then, asking about the “position” of an element in R+ is meaningless. R+ is what’s called uncountably infinite.”

In every sentence but the last, you go on explaining what is actually called a dense set. Meaning, between any two elements you can find another element. As we both know, Q and R both share this property. 0.1 is rational, 0.01 is rational, 0.001 is rational, and so your entire paragraph might as well be explaining Q instead of R. By your own reasoning, it is still meaningless to talk about the “position” of rational numbers (they cannot be countably ordered by size, in other words).

“Any set which can be put in a one-to-one correspondence with the natural numbers (or integers) so that a prescription can be given for identifying its members one at a time is called a countably infinite (or denumerably infinite) set.” –Mathworld

Q can be put into 1-1 correspondence with N, even though it is dense. R is dense but cannot be. Why this is the case you did not explain or even hint at.

“So how can we compare R and N? Well, every interval subset of R has infinitely many elements. Every interval subset of N, on the other hand, has finitely many elements. Clearly, then, R is much bigger than N. In other words, the cardinality of N is less than the cardinality of R.”

Every interval in Q has infinitely many elements! Yet Q and N still have the same cardinality. You are not correctly identifying the reason that R and N are of different sizes. In my opinion, the best way to show this is to explain that any sequence (read: countable subset) of real numbers is missing at least one, and therefore the real numbers in their entirety must not be countable. (Basically, use the diagonal argument because it is easy to understand.)

“We denote the cardinality of R as \aleph_1 and say that \aleph_0 < \aleph_1. (Note that this is a cardinal, not an arithmetic, ordering; \aleph isn’t a number, remember).

So I hope that was understandable. I tried not to use so much jargon. If you have any questions, comments, responses, you know what to do. Next time we’ll talk about the continuum hypothesis and sets with even bigger cardinalities!”

Noooooooooooooooooooooooooooooooooooooooo!!

Are you sure that the size of R is aleph1? If that were correct, then there would be no continuum hypothesis in the first place! The cardinality of R is termed 2^aleph1, or beth1.

The continuum hypothesis states that the size of R is in fact aleph1, which would mean there are no sets bigger than N but smaller than R, but this assertion is actually independent of the Zermelo-Fraenkel axioms of which set theory is based off of!

Okay, I’m done ranting. 🙂

Posted by khuram on August 7, 2007 at 3:17 am

Sorry Mr. Jon,,, I have checked your other post on similar topic now… you are actually talking about discussion on digg.com

You had only single point for me which you had presented on your comments on mindloop blog. You said about me that there is no math in my writings. I accept. Because really there is no “calculation” in my article.

Secondly I don’t write from Purtugese. I write from an intellectually backward country “Pakistan”… So you should give me grace marks atleast …

Regards!