Comparing infinite sets

What is the basis for reason? And mathematics?

Moderators: AMod, iMod

Post Reply
Philosophy Explorer
Posts: 5621
Joined: Sun Aug 31, 2014 7:39 am

Comparing infinite sets

Post by Philosophy Explorer »

I already know that Aleph followed by a number characterizes the relative size of some infinite set. Let's start with Aleph 0.

Aleph 0 is characterized by the set of natural numbers. Aleph 0 is also characterized by set of nontranscendental irrational numbers. Why? Because the set of nontranscendental numbers may be placed in one-to-one correspondence with the set of natural numbers so these sets are the same size.

Next we have Aleph 1 which may be characterized by the set of transcendental numbers (you know, those numbers that can't be the roots of any algebraic equation such as π and e). Now I have seen proofs showing the set of Aleph 1 numbers can't be placed into one-to-one correspondence with the set of Aleph 0 numbers. What I haven't seen is a proof showing the set of Aleph 1 is greater than the set of Aleph 0 (ironically I know that the set of Aleph 1 numbers are harder to find along the real number line than the set of Aleph 0 numbers, just like dark matter).

Then we have Aleph 2 numbers which is characterized by all the curves (including, I presume, straight lines). Why is this set characterized this way I don't know. Why is this set greater than Aleph 1 I don't know either. If somebody can shed light on this I'd appreciate it along with any commentary on higher sets than Aleph 2.

Edit: I gave Aleph 2 some more thought and here is my reasoning. The Aleph 1 level can be the entire real number line which can be composed of the transcendental numbers, the nontranscendental numbers and the set of natural numbers plus those negative counterpart numbers plus the fractions plus zero to round it out.

Okay then it would seem that the number of curves would be the next logical step up. Now here's the thing. How would one number the curves for comparison purposes? For example, what number would be assigned to a parabolic curve as opposed to a hyperbolic curve? And then how would one go from there to proving that Aleph 2 is greater than Aleph 1? That's the extent of my knowledge.

PhilX
Last edited by Philosophy Explorer on Fri Sep 05, 2014 6:11 am, edited 1 time in total.
Blaggard
Posts: 2246
Joined: Fri Jan 10, 2014 9:17 pm

Re: Comparing infinite sets

Post by Blaggard »

No you have the wrong end of the cardinal stick in Cantor's hypothesis.

Not that I think he had a well made point per se, but what you said is not how the alephs work.

Essentially if you take the fractions and you may well they all eventually to infinity add up to 1 there are an infinite amount of fractions which will sum infinitely to 1 and 1 to 1 with the whole numbers. But decimals can have infinite places after 0.x so that a decimal set is larger than a fraction set, it has nothing to do with curves, just the nature of transcendental numbers like pi which has infinite places. It's a rather technical point about larger and smaller, but it does make mathematical sense per se. It's bollocks an useless but the logic is sound. :P
Independence from ZFC

Cantor believed the continuum hypothesis to be true and tried for many years to prove it, in vain (Dauben 1990). It became the first on David Hilbert's list of important open questions that was presented at the International Congress of Mathematicians in the year 1900 in Paris. Axiomatic set theory was at that point not yet formulated.

Kurt Gödel showed in 1940 that the continuum hypothesis (CH for short) cannot be disproved from the standard Zermelo–Fraenkel set theory (ZF), even if the axiom of choice is adopted (ZFC) (Gödel (1940)). Paul Cohen showed in 1963 that CH cannot be proven from those same axioms either (Cohen (1963) & Cohen (1964)). Hence, CH is independent of ZFC. Both of these results assume that the Zermelo–Fraenkel axioms are consistent; this assumption is widely believed to be true. Cohen was awarded the Fields Medal in 1966 for his proof.

The continuum hypothesis is closely related to many statements in analysis, point set topology and measure theory. As a result of its independence, many substantial conjectures in those fields have subsequently been shown to be independent as well.

So far, CH appears to be independent of all known large cardinal axioms in the context of ZFC.[citation needed]

Gödel and Cohen's negative results are not universally accepted as disposing of the hypothesis. Hilbert's problem remains an active topic of research; see Woodin (2001) and Koellner (2011a) for an overview of the current research status.

The continuum hypothesis was not the first statement shown to be independent of ZFC. An immediate consequence of Gödel's incompleteness theorem, which was published in 1931, is that there is a formal statement (one for each appropriate Gödel numbering scheme) expressing the consistency of ZFC that is independent of ZFC, assuming that ZFC is incomplete. The continuum hypothesis and the axiom of choice were among the first mathematical statements shown to be independent of ZF set theory. These proofs of independence were not completed until Paul Cohen developed forcing in the 1960s. However, they all rely on the assumption that ZF is consistent. These proofs are called proofs of relative consistency (see Forcing (mathematics)).
It's all there on google.

http://en.wikipedia.org/wiki/Continuum_hypothesis

Curves hyperbolic or otherwise have nothing to do with set theory. It is simply about number theory. 1+1=2. the degrees in trig or algebra play no part.
Philosophy Explorer
Posts: 5621
Joined: Sun Aug 31, 2014 7:39 am

Re: Comparing infinite sets

Post by Philosophy Explorer »

Thanks Blaggard,

I've already worked out a partial solution to the questions I've been posing. I couldn't follow what you were saying, but as I said I believe I'm on the path towards working out a complete solution. I know eventually it will all work out.

PhilX
wtf
Posts: 1178
Joined: Tue Sep 08, 2015 11:36 pm

Re: Comparing infinite sets

Post by wtf »

This is my second in a series of posts reviving @PhilX's old posts on infinity in order to clarify some issues of philosophical interest and importance. The first thread in this series is viewtopic.php?f=26&t=15446, and it wouldn't hurt to read that one first if you haven't already. And if you have, it wouldn't hurt to read it again. I have some references listed in that post that I won't necessarily repeat here.


Philosophy Explorer wrote:I already know that Aleph followed by a number characterizes the relative size of some infinite set. Let's start with Aleph 0.
The Alephs are indexed by the ordinal numbers. Technically the Alephs are also defined as certain ordinals (specifically, the least ordinal of any class of cardinally-equivalent ordinals) so that the Alephs are well-ordered by construction.
Philosophy Explorer wrote: Aleph 0 is characterized by the set of natural numbers.
Aleph-0 is the cardinality of the natural numbers, yes. I'm not sure what you mean by "characterized by," that's a little vague.
Philosophy Explorer wrote:Aleph 0 is also characterized by set of nontranscendental irrational numbers.
Yes, but your terminology is a little odd. The algebraic numbers have cardinality Aleph-0. The algebraic numbers are the real numbers that are the roots of polynomials having integer coefficients. It's true but confusing to talk about "nontranscendental irrationals," since the rationals are algebraic as well.
Philosophy Explorer wrote:Why? Because the set of nontranscendental numbers may be placed in one-to-one correspondence with the set of natural numbers so these sets are the same size.
Yes but why? The proof is that there are only countably many roots of polynomials of degree 1; only countably many of degree 2; dot dot dot; and the union of a countable collection of countable sets is countable. So there are only countably many algebraic numbers.
Philosophy Explorer wrote: Next we have Aleph 1 which may be characterized by the set of transcendental numbers (you know, those numbers that can't be the roots of any algebraic equation such as π and e).
Your terminology is funny again. (Funny odd, not funny haha). You are thinking of the real numbers, which include the transcendentals and the algebraic numbers.

The claim that the real numbers have cardinality Aleph-1 is the Continuum Hypothesis (CH), which you consistently mis-state in your posts. For all we know (and many set theorists believe), the cardinality of the real numbers is very large, far larger than Aleph-1. CH is independent of ZFC, so the question of whether there is a "true" answer is a matter of philosophy. Nevertheless, CH and related questions have been the object of intense study by set theorists since the time of Cantor and continuing to the present day.

But (this bears repeating, since you consistently misunderstand it) CH says that the cardinality of the reals is Aleph-1. But for all we know, it's Aleph-47. Or bigger. Nobody knows. It's a question of philosophy as to whether the question's even meaningful.

Philosophy Explorer wrote: Now I have seen proofs showing the set of Aleph 1 numbers can't be placed into one-to-one correspondence with the set of Aleph 0 numbers. What I haven't seen is a proof showing the set of Aleph 1 is greater than the set of Aleph 0 (ironically I know that the set of Aleph 1 numbers are harder to find along the real number line than the set of Aleph 0 numbers, just like dark matter).
Aleph-0 is strictly less than Aleph-1 for the reason that both are defined as particular ordinals, and ordinals are well-ordered. Aleph-0 is the least member of the class of all countable ordinals. Aleph-1 is the least member of the class of all uncountable ordinals. See the Wiki references in my earlier infinity post to learn about well-orders and ordinal numbers.




Philosophy Explorer wrote: Then we have Aleph 2 numbers which is characterized by all the curves (including, I presume, straight lines).
No, that's not true. I'll say why in a moment.
Philosophy Explorer wrote: Why is this set characterized this way I don't know.
Why you make this claim, I don't know. I believe Cantor might have thought this was the case, but it turns out to be false, as we'll see in a moment.
Philosophy Explorer wrote: Why is this set greater than Aleph 1 I don't know either.
Aleph-2 is strictly greater than Aleph-1 by the construction of the Alephs. They're particular ordinals. They line up like soldiers, one after the other: Aleph-0, Aleph-1, Aleph-2, etc. If any two of them were bijectively equivalent, they'd be the same Aleph by definition.

Philosophy Explorer wrote: If somebody can shed light on this I'd appreciate it along with any commentary on higher sets than Aleph 2.
I take you at your word that you appreciate my attempt to help you sort out these ideas.

If you want to visualize the Alephs, that's easily done. 0, 1, 2, ... are the finite ordinals. Aleph-0 is the cardinality of the set of finite ordinals. Likewise, Aleph-1 is the cardinality of the set of ordinals of cardinality Aleph-0. Aleph-2 is the cardinality of the set of ordinals of cardinality Aleph-1, and so forth. Each Aleph is the cardinality of the set of ordinals having cardinality strictly less than that Aleph. In this way one can actually visualize each of the Alephs.



Philosophy Explorer wrote: Edit: I gave Aleph 2 some more thought and here is my reasoning. The Aleph 1 level can be the entire real number line which can be composed of the transcendental numbers, the nontranscendental numbers and the set of natural numbers plus those negative counterpart numbers plus the fractions plus zero to round it out.
Again, your terminology is correct but very confusing. 0 is already algebraic, as are all the integers (positve and negative) and all the rationals (positive and negative). You can simply say that the reals consist of the transcendentals and the algebraics.

As to whether the reals have cardinality Aleph-1, again that is the content of CH. The reals may have cardinality Aleph-1, or they may have cardinalty Aleph-47. Or some other cardinality. The reals may have a cardinality of pretty much any Aleph at all, subject to some technical restrictions.



Philosophy Explorer wrote: Okay then it would seem that the number of curves would be the next logical step up.
No, the set of curves has the same cardinality as the set of real numbers, as I'll show in a moment.

Philosophy Explorer wrote: Now here's the thing. How would one number the curves for comparison purposes? For example, what number would be assigned to a parabolic curve as opposed to a hyperbolic curve? And then how would one go from there to proving that Aleph 2 is greater than Aleph 1? That's the extent of my knowledge.
This is how we calculate the number of curves.

First, what is a curve in the plane? It's a continuous curly line, intuitively speaking. How shall we formalize this? A curve in the plane is a continuous function from the unit interval [0,1] to the plane R^2. If you think about it, that makes perfect sense. In includes all the straight line segments, the curvy lines, the closed curves, the curves that loop around and intersect themselves, and so forth.

Now a continuous function whose domain is some interval of real numbers is entirely characterized by its value on the rational numbers in that interval. That's because continuous functions preserve limits of sequences, and every real number is the limit of a sequence of rationals.

In other words in calculus class they tell you that if (x_n) is a sequence converging to x, and f is a continuous function, then the sequence (f(x_n)) converges to f(x). Every real number is the limit of the sequence of rationals formed by truncating its decimal expression. For example pi is the limit of the sequence of rationals 3, 3.1, 3.14, 3.141, ... Therefore if we know the value of a continuous function on the rational numbers, we automatically know its value on the real numbers. Continuity is a powerful condition that greatly restricts how wild a function can be.

Using cardinal arithmetic, the number of such continuous functions is therefore ((Aleph-0)^2) ^ (Aleph-0) = 2^(Aleph-0), which is the cardinality of the reals (ask me for that proof if you're interested).

https://en.wikipedia.org/wiki/Cardinal_ ... arithmetic

See this thread for the same answer but with better formatting. Why is there no LaTeX on this forum? http://math.stackexchange.com/questions ... -2-aleph-0
wtf
Posts: 1178
Joined: Tue Sep 08, 2015 11:36 pm

Re: Comparing infinite sets

Post by wtf »

It occurs to me that I owe a much more clear explanation of the chain of cardinal arithmetic showing that the set of curves in the plane has the same cardinality as the real numbers. I shall do this now.

There are three things we need to know.

1) If X and Y are sets, the set of functions from Y to X is denoted X^Y. And if |X| denotes the cardinality of set X, then |X^Y| = |X|^|Y|. You can easily see this is true for finite sets, and it can be extended to transfinite cardinalities as well.

2) If k is a cardinal, then k * k = k. This is a generalization of the idea that a countable union of countable sets is countable.

3) The cardinality of the real numbers is 2^(Aleph-0). In what follows I'll write Aleph-0 as A0 in order to avoid parentheses. So the cardinality of the real numbers |R| = 2^A0.


Now:

* What is the cardinality of the plane R^2? The plane is the set of pairs of real numbers. So the cardinality of the plane is 2^A0 * 2^A0 = 2^A0. That's a quick proof that the plane has the same cardinality as the set of real numbers. That surprised even Cantor..

* A continuous function from the unit interval to the plane is defined by an arbitrary function from the rationals in the unit interval to the plane. The cardinality of the rationals in the unit interval is A0.

* So the cardinality of the set of functions from the rationals (in the unit interval) to the plane is (2^A0)^A0 = 2^(A0 * A0) = 2^A0 as claimed.

* Finally, the cardinality of the set of real numbers is 2^A0. You can see this by writing a real number (between zero and 1, for simplicity) in binary notation. For example 1/2 = .10000...

If you have a real number (between 0 and 1) expressed in binary as, say, .101011110... you can number the bit positions starting from 0 on the left. Then the above binary expression can be taken as a function that inputs a natural number, the bit position, and maps it to No/Yes or the set {0,1}. In other words the real number .101011110... codes the function that takes 0 to 1, 1 to 0, 2 to 1, 3 to 0, etc.

So real numbers (in the unit interval) are actually the same thing as the set of functions from the natural numbers to the set {0,1}. Their cardinality is 2^A0.
User avatar
Lawrence Crocker
Posts: 86
Joined: Mon Apr 13, 2015 12:44 pm
Location: Eastman, NH
Contact:

Re: Comparing infinite sets

Post by Lawrence Crocker »

As wtf says, the consistency and independence proofs raise philosophical questions about the continuum hypothesis (CH). CH can be expressed as the proposition that there is no set intermediated in size between the set of the natural numbers and the set of the reals. I have thought about this a bit, and quote below a section of my blog post about it. If this piques your curiosity, I invite you to take a look at the whole post, and respond. At issue is mathematical Platonism, which I describe sketchily and some alternatives, which I sketch really sketchily


For a long time my reaction to the continuum hypothesis was, “Damn it, either there is a set of that intermediate size or there isn’t.” I took this to be a Platonist intuition. I was convinced that there was a fact of the matter about the continuum hypothesis whether or not human beings would ever know it to be true or false.

My confidence dropped, at least below the level of swearing about it, when I realized that there might be something to a conjecture of Skolem’s that predated even Gӧdel’s consistency result. What Skolem said was that our concept of set might not yet be so well developed as to answer the continuum hypothesis question. That is, the problem might be not with the things to be counted, but with the gathering them together to be counted.

For more, please see http://www.LawrenceCrocker.blogspot.com post of July 22, 2014.
Post Reply