## Status of Cantor's 'Continuum Hypothesis'

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

### Status of Cantor's 'Continuum Hypothesis'

Edit by Natural ChemE (2015 09 16 0457 EST) wrote:This thread has been generated by splitting a prior thread, Infinity is a trivially simple concept. The prior thread was about seeing infinity as a simple concept.

The first post in this thread was by someguy1 who was arguing that Cantor's Continuum Hypothesis was complex, so infinity was complex (my interpretation of his position; not necessarily correct). His point was entirely appropriate to the prior thread, however it also led into a very interesting discussion on stuff like the Continuum Hypothesis.

This thread focuses on that interesting tangent. Discussion on the complexity of infinity should go into the prior thread.

So you've trivially solved the Continuum Hypothesis (CH)? There'a probably a Fields medal in it for you. Either that, or I'd argue that you haven't shown that infinity is trivial at all.

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

What we know:

* There's an elaborate mathematical theory of infinity that's been in common use for about a century, give or take (depending on where you put your historical starting point: Cantor's paper in 1874, or Zermelo's axiomatization of set theory in 1922).

* CH is one of the most famous unsolved (and perhaps unsolvable) problems in math. It's still an active research area in set theory.

* The basic theory (countable and uncountable infinities, ordinal and cardinal numbers) is the starting point for the conversation about whether infinity is trivial. But it's difficult (for me) to see how anyone familiar with this material could regard infinity as trivial. On the contrary, the mathematical theory of infinity involves questions in logic and the philosophy of math, in addition to being deep and interesting math itself.

Here is the question that nobody knows the answer to.

We start from the intuition of the infinitude of the counting numbers 1, 2, 3, 4, 5, ... (some people like to start from 0, it makes no difference here).

How many subsets of the natural numbers are there?

That's the simple question that's bedeviled and confounded some of the greatest minds in mathematics for the last 140 years. The Continuum Hypothesis says that the number of subsets is the smallest possible infinity larger than that of the natural numbers themselves.

Eternal fame awaits the solver.

(ps) Let me get ahead of a couple of potential (or even actual!) objections to what I wrote. @Natural ChemE claimed that there is no actual infinity. If that is the case, then infinity is trivial in the exact same sense that purple unicorns are trivial. They're trivial because they don't exist.

Yet the novel Moby **** is a work of fiction, and it's far from trivial. So I'd reject this line of thought. Works of fiction may be nontrivial.

On the other hand, suppose we do admit the (conceptual, mental, abstract, fictional) existence of completed infinite sets such as the natural numbers. Then the questions raised by transfinite set theory, such as CH, become meaningful and incredibly subtle and difficult questions. Again, far from trivial.

So I don't see any sense at all in which infinity is trival.
Last edited by Natural ChemE on September 16th, 2015, 5:36 am, edited 7 times in total.
Reason: Please see the quote at the start of this post for details.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Infinity is a trivially simple concept

Faradave » September 15th, 2015, 8:48 am wrote:Thus, "innumerable" might be the best way to characterize infinity, in that we can have a measurable, finite line segment, which contains innumerable points (an infinite collection).

How many points? If all this is so simple, how many points? Which Aleph? How can anyone say this is trivial when it's baffled the finest minds from Cantor to Russell to Hilbert to Gödel straight through to contemporary, modern set theorists? Which is more likely? That all these geniuses were misguided? Or that the opinions being expressed in this thread are naive and wrong?

Can you distinguish, so that I may further understand the viewpoint being expressed in this thread, between the following two statements:

a) It's trivial because the answer is really really obvious to me, but I haven't bothered to write it down and collect my Fields medal; or

b) It's trivial because I've shut my eyes and put my hands over my ears la la la la la.

I'm getting a strong (b) vibe from this thread. As Howard Cosell once said: ""If ignorance is bliss my friend.............. YOU must be ecstatic."
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Infinity is a trivially simple concept

someguy1 » September 15th, 2015, 10:50 am wrote:So you've trivially solved the Continuum Hypothesis (CH)? There'a probably a Fields medal in it for you. Either that, or I'd argue that you haven't shown that infinity is trivial at all.

You've got the conceptual hierarchy backward. The continuum hypothesis depends on the concept of infinity, not vice versa.

Incidentally the continuum hypothesis also depends on the concept of integers, which in turn depends on the concept of counting. Would you also say that you don't understand counting?

Honestly I think that you're just being super-pretentious. I mean, seriously dude, you quoted someone as an insult about intelligence:
someguy1 » September 15th, 2015, 2:23 pm wrote:As Howard Cosell once said: ""If ignorance is bliss my friend.............. YOU must be ecstatic."
As a mod, I'm gonna warn you about that. As a poster, I'm going to tell you that it was pathetic. Don't lower yourself with such petty nonsense.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

Natural ChemE » September 15th, 2015, 3:16 pm wrote:
someguy1 » September 15th, 2015, 10:50 am wrote:So you've trivially solved the Continuum Hypothesis (CH)? There'a probably a Fields medal in it for you. Either that, or I'd argue that you haven't shown that infinity is trivial at all.

You've got the conceptual hierarchy backward. The continuum hypothesis depends on the concept of infinity, not vice versa.

Incidentally the continuum hypothesis also depends on the concept of integers, which in turn depends on the concept of counting. Would you also say that you don't understand counting?

I really don't understand your question. This conversation sounds to me like the following. Unifying general relativity and electromagnetism is trivial. After all, I have a radio. I can tune it to a top 40 pop music station. Then I drop it on the floor. Look, I've unified gravity and electromagnetism. Who needs all that fancy physics?

I confess I honestly do not understand the point you're trying to make. Radios sense electromagnetic energy and they fall under the influence of the local curvature of space. That hardly makes physics trivial, even though radios are commonplace objects of everyday experience.

Maybe you could try to put this in a way I can understand. What's trivial about the mathematics of infinity, not to mention the metaphysics of infinity?
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Infinity is a trivially simple concept

someguy1 » September 15th, 2015, 4:45 pm wrote:I confess I honestly do not understand the point you're trying to make. Radios sense electromagnetic energy and they fall under the influence of the local curvature of space. That hardly makes physics trivial, even though radios are commonplace objects of everyday experience.

Maybe you could try to put this in a way I can understand. What's trivial about the mathematics of infinity, not to mention the metaphysics of infinity?

The point is the thread's title, "Infinity is a trivially simple concept".

I think that you've read it as, "All mathematics that somehow mentions, involves, relates to, or uses the concept of infinity is trivial".
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

Natural ChemE » September 15th, 2015, 3:52 pm wrote:
someguy1 » September 15th, 2015, 4:45 pm wrote:I confess I honestly do not understand the point you're trying to make. Radios sense electromagnetic energy and they fall under the influence of the local curvature of space. That hardly makes physics trivial, even though radios are commonplace objects of everyday experience.

Maybe you could try to put this in a way I can understand. What's trivial about the mathematics of infinity, not to mention the metaphysics of infinity?

The point is the thread's title, "Infinity is a trivially simple concept".

I think that you've read it as, "The set of all mathematics that somehow mentions, involves, relates to, or uses the concept of infinity is collectively trivial".

Is electromagnetism a simple concept because I can play a radio?

So how do you define infinity to make it trivial? Unlimited? I could give a counterexample. Endless? I could give a counterexample. The definition of infinity turns out to be subtle.

someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Infinity is a trivially simple concept

someguy1,

Electromagnetism isn't a concept, simple or otherwise. It's a physical phenomena.

Does this make sense to you, or should I state this point in another way?

PS - I'd add that the definition of infinity isn't really that subtle so much as context-dependent; it's kind of a bland, lazy term that often leads to confusion because many thinkers/writers fail to really nail down what they mean. This leads to them accidentally straw manning their own arguments, leading to a huge mess in their heads. Honestly that's a big reason that I started this thread: to help promote clarity in a topic that people keep getting confused about. The topic itself is really simple; it's the unrecognized ambiguity that gets folks.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

someguy1 » Tue Sep 15, 2015 11:50 am wrote:So you've trivially solved the Continuum Hypothesis (CH)? There'a probably a Fields medal in it for you. Either that, or I'd argue that you haven't shown that infinity is trivial at all.

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

What we know:

* There's an elaborate mathematical theory of infinity that's been in common use for about a century, give or take (depending on where you put your historical starting point: Cantor's paper in 1874, or Zermelo's axiomatization of set theory in 1922).

* CH is one of the most famous unsolved (and perhaps unsolvable) problems in math. It's still an active research area in set theory.

* The basic theory (countable and uncountable infinities, ordinal and cardinal numbers) is the starting point for the conversation about whether infinity is trivial. But it's difficult (for me) to see how anyone familiar with this material could regard infinity as trivial. On the contrary, the mathematical theory of infinity involves questions in logic and the philosophy of math, in addition to being deep and interesting math itself.

Here is the question that nobody knows the answer to.

We start from the intuition of the infinitude of the counting numbers 1, 2, 3, 4, 5, ... (some people like to start from 0, it makes no difference here).

How many subsets of the natural numbers are there?

That's the simple question that's bedeviled and confounded some of the greatest minds in mathematics for the last 140 years. The Continuum Hypothesis says that the number of subsets is the smallest possible infinity larger than that of the natural numbers themselves.

Eternal fame awaits the solver.

(ps) Let me get ahead of a couple of potential (or even actual!) objections to what I wrote. @Natural ChemE claimed that there is no actual infinity. If that is the case, then infinity is trivial in the exact same sense that purple unicorns are trivial. They're trivial because they don't exist.

Yet the novel Moby **** is a work of fiction, and it's far from trivial. So I'd reject this line of thought. Works of fiction may be nontrivial.

On the other hand, suppose we do admit the (conceptual, mental, abstract, fictional) existence of completed infinite sets such as the natural numbers. Then the questions raised by transfinite set theory, such as CH, become meaningful and incredibly subtle and difficult questions. Again, far from trivial.

So I don't see any sense at all in which infinity is trival.

Dude,
Moby **** is fact-based. Ahab was fictional; the rest happened, albeit not in allegorical format. Bad example.
Resident Expert

Posts: 5931
Joined: 31 Dec 2008

### Re: Infinity is a trivially simple concept

CanadysPeak » September 15th, 2015, 4:40 pm wrote:Dude,
Moby **** is fact-based. Ahab was fictional; the rest happened, albeit not in allegorical format. Bad example.

Dude, I could have picked Star Wars just as easily. But my point was that fiction can be nontrivial. Are you supporting @NatChemE's finitism? Where he says actual infinity doesn't exist therefore it's trivial? Ok, I'll grant your point. Infinity doesn't exist therefore it's trivial. But now you're forced to deny the conceptual existence of the set of natural numbers, putting you far outside the mainstream of modern math.

However, your point is actually a good one. If you believe that math is a useful and interesting fiction that's vaguely based on reality, that's exactly what Moby **** is. But that is not an argument supporting the triviality of either the novel or of modern mathematics.

(ps) -- Let me walk through the chain of logic here, since the subplots are too nested for clarity.

@NatChemE is defending the proposition that infinity is trival. I disagree. In one of his posts, he wrote:

Natural ChemE » September 15th, 2015, 1:24 am wrote:
There's lots on the subject in discussions about actual infinity vs. potential infinity, though basically there's no meaningful "absolute infinity" - only potential constructions - because we're finite computers ourselves. Cantor is said to have disagreed for religious/romantic reasons, i.e. wanting to believe in an absolutely infinite God.

In this passage. @NatChemE is saying that he does not believe in actual (ie "completed") infinity. That makes him some variety of finitist. No problem, perfectly legitimate, but finitists do not believe in infinite sets. Therefore I asked him if he is making the argument that "Infinity doesn't exist, therefore it's trivial."

I pointed out that any complex work of fiction is nontrivial yet its subject matter is nonexistent. I used the example of Moby ****, which as you correctly point out is based on a real historical event of a whale attacking a ship.

But all fiction is like that. Star Wars is about a young man coming of age in difficult times, growing into manhood, entering a demanding training regime, becoming a leader of his people, dealing with daddy issues, etc. Every great work of fiction is based on timeless themes based in the true experience of humanity. That's no argument against it still being fiction.

But the core argument of a finitist is that infinite sets do not exist. If you take that position and then say that infinity is trivial, well ok, whatever. Star Wars is trivial too, in the sense that it's a popular entertainment. But as I noted, its underlying themes are timeless and real.

However I do not believe that finitism is the way to go here. If you want to say that infinity is trivial, you have to accept the modern concept of completed infinity (ie set theory) and then make your case that it's trivial.

Finitism is interesting but a bit beside the point.

I hope that I clarified this subthread regarding finitism, which is somewhat separate from the main topic of triviality.
Last edited by someguy1 on September 15th, 2015, 7:07 pm, edited 1 time in total.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Infinity is a trivially simple concept

someguy1 » September 15th, 2015, 5:46 pm wrote:Are you supporting @NatChemE's finitism? Where he says actual infinity doesn't exist therefore it's trivial?

Not my claim.

Don't get me wrong, I argue both:
1. Infinity is trivial.
2. Actual infinity isn't meaningful.
However, I argue neither:
1. Infinity is trivial because actual infinity doesn't exist.
2. Actual infinity doesn't exist.
You're jumping the gun pretty hard and getting confused in the process. This isn't at just one point, but all over your logic. I'd suggest more precision.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

Natural ChemE » September 15th, 2015, 5:06 pm wrote:
someguy1 » September 15th, 2015, 5:46 pm wrote:Are you supporting @NatChemE's finitism? Where he says actual infinity doesn't exist therefore it's trivial?

Not my claim.

Don't get me wrong, I argue both:
1. Infinity is trivial.
2. Actual infinity isn't meaningful.
However, I argue neither:
1. Infinity is trivial because actual infinity doesn't exist.
2. Actual infinity doesn't exist.
You're jumping the gun pretty hard and getting confused in the process. This isn't at just one point, but all over your logic. I'd suggest more precision.

Appreciate the clarification. I still don't understand your point. Perhaps I should quit while I'm behind. I don't find the subject of infinity trivial at all. Even its mathematical definition is full of subtleties. But if actual infinity doesn't exist, what is it you are saying is trival?

Also since you are finitist, are you an ultrafinist? A finitist doesn't believe in infinite sets, though they believe in 1, 2, 3, 4, ... They just don't accept a completed aggregate of all of them. An ultrafinitist denies the existence of sufficiently large finite sets. When I'm conversating with a finitist I find it helpful to know which type you are. A milder form of finitism is constructivism, where you believe in (completed) infinite sets as long as they can be computed by algorithms. This is still a non-mainstream point of view but it's gaining currency lately through the influence of computer science.

But mostly I don't understand how you can say "X is trivial and I don't think X exists at all!" Well yeah, nonexistent things have all sorts of vacuous properties. Purple unicorns have stripes, but that's a vacuously true statement.

I don't think I'm confused at all here. I picked up on your finitism and now I'm challenging you to say why you are taking the trouble to ascribe a quality (triviality) to something you don't think exists in the first place.

In other words a more logically coherent statement would be "Completed infinite sets don't exist so modern set theory is bullshit." The statement I'm having trouble with is, "Completed infinite sets don't exist so modern set theory is trivial."

Or -- ah, perhaps this is it -- are you saying: "Completed infinity doesn't exist, so there's nothing to talk about. But potential infinity is trivial."

Is that a better interpretation?

If so, then I definitely disagree. Finitism is very difficult these days as you have to work extra hard to do calculus and other infinitary branches of math. It can in fact be done, but it's hard. Far from trivial, and far harder than just accepting infinite sets and dealing with the logical consequences.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Infinity is a trivially simple concept

someguy1,

We may have to split this off as it's tangential to the thread, but I'd enjoy a chat about methods for precisely defining and working with infinities.

Short version

1. Our minds exist in the physical world.
2. So our thoughts exist in the physical world.
3. So a thought is either:
1. constructable (minds can construct the thought); or
2. inconsistent (not reproducible; minds can't think (construct) it).
4. Absolute infinities are those without an explicit construction, making them either:
1. implicitly constructable (ambiguously stated constructed infinities); or
2. inconsistent (nonsense).
5. Stuff like the generalized continuum hypothesis has already been proven if we assume constructability.
• And we literally can't think of non-constructable things consistently.

Does anything sound off here?

Long version
Generally I reject dualism, i.e. the notion that the mind and body are fundamentally separate entities (or more generally, the abject refusal to consider that the mind is some type of system with some type of physics). This means that our thought processes are physical processes. I then believe that, when we think about models, our models are themselves physical constructs, such that any well-defined thought is physically constructed, even within the murky, confusing world of neurochemistry.
Point being: The brain's great complexity does not mitigate the fact that it and all of our thoughts are physical systems that came about through (i.e. were constructed by) physical processes.
• All reproducible thought processes must be constructable through reproducible steps.
• All consistent logic/math systems are composed entirely of reproducible thought processes.

As Gödel proved, the generalized continuum hypothesis is true within this context. All other contexts (i.e. non-constructable contexts) are literally nonsense as they ultimately fail to be fully consistent for any mind that is part of our universe.
More generally, logic/math systems are always inconsistent for minds that exist in universes in which the logic/math system is not constructable. So:
• Even if human minds exist in another world, so long as our minds exist in the same other world, a system that is non-constructable/inconsistent for any of us is inconsistent for all of us.
• Even if each human mind exists in its own world, it must be able to construct a logic/math system for that logic/math system to be consistent within that mind.

As I noted in the first reply to this thread, discussions revolving around infinity are funny because they're an excellent example of folks who believe in dualism (even if implicitly, as I suspect is usually the case with mathematicians) struggling with logical conflicts resulting from that simplistic belief.
I call dualism "simplistic" not to be condescending, but because it's a simplification as opposed to a choice. Rejecting dualism means considering the more general, rigorous model for reality. This in one case where I would argue that that complexity is unavoidable since dualism leads to incorrect conclusions.

I guess that there's a lot that could be said on this topic. Like, back when you brought up the continuum hypothesis, I could've tried to talk about how's it been proven in the only context that isn't nonsense, making it a non-issue. But I guess that it's hard to maintain focus in communications like this, as threads must be relatively linear and concise. So, ya know.. still not able to say everything; but I hope it makes sense?

Basically I think that some folks are confused because they fail to consider that our thoughts and minds are physical systems, implying properties like constructability are necessarily true for all systems that we can work with - including all hypothetical math systems - such that any non-constructable concept is always inconsistent.

I guess that the important point would be:
Consistency fundamentally requires constructability.
And its corollary:
All non-constructable concepts are inconsistent.

So all "absolute infinities" are either:
1. Constructable infinities that don't explicitly specify their construction (ambiguous); or
2. nonsense.
Previously I said that "absolute infinity" isn't meaningful while also claiming that it can exist. In that post I was referring to Case (i). Exists because it can be consistent, but not meaningful because it's ambiguous.

Finally, the ultimate point in this thread was that infinity is a trivial concept. This was just 'cause infinity really is simple to understand; it's simply a value that lacks some sort of limit. Some folks just confuse the heck out of themselves 'cause they misunderstand it after learning about it for the first time, adopting an inconsistent idea of infinity that they can't consistently define (though Cantor loved to rant about how absolute infinity was God).

Does any part of this seem off?

PS - Sorry for the weird format. Hard to talk about stuff like this in linear formats.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

someguy1 » September 15th, 2015, 6:19 pm wrote:Or -- ah, perhaps this is it -- are you saying: "Completed infinity doesn't exist, so there's nothing to talk about. But potential infinity is trivial."

Is that a better interpretation?

If so, then I definitely disagree. Finitism is very difficult these days as you have to work extra hard to do calculus and other infinitary branches of math. It can in fact be done, but it's hard. Far from trivial, and far harder than just accepting infinite sets and dealing with the logical consequences.

Just to directly answer this, I was referring to "completed infinity" as "absolute infinity" in my above response. My position on it is that it is that all "completed infinities" either:
1. are potential infinities with undefined generation methods; or
2. are nonsense, because if there's no generation method - either defined or undefined - then it's fundamentally impossible for a mind to reproducibly construct it.
However I still use "completed infinities" in my work - and even in my posts on this forum - because while they're actaully just potential infinities, there's no need to specify a construction method in many cases.

So, yup, I agree with you; it's more work to always specify a construction method when many problems don't require it. However, I'd stress that all infinities must have a construction method, even if a particular writing doesn't specify one for brevity's sake. And because all infinities must be potential infinities, all valid uses of "complete infinities" are approximate representations - not fundamentally "absolute" infinities.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

someguy1,

Why do folks consider the continuum hypothesis unproven? I mean, to me, there are two cases:
1. We're talking constructable infinities, in which case Kurt Gödel has already proven it back in 1938.
2. We're talking about infinities that can't be constructed through any potential procedure operating on a potential infinity, making them fundamentally inconsistent.

It looks like it's solved to me. What am I missing?

PS - According to the postscript in the revised version of What is Cantor's Continuum Problem?, Gödel (1947), the central holdup was claimed to be that it'd be "hard" to construct a general definition for potential infinities. Hah, is it really true that mathematicians consider this an open question because a rigorous proof that doesn't refer to the whole our-brains-are-physical-entities thing would be tedious to write?
Sadly, the postscript wasn't available on the linked Jstor copy, but a scan of the revised paper with it can be read here. This copy was a revision of the original paper, published in 1964, with the postscript dated 1966.
PPS - Yeah, apparently mathematicians are allowing for non-constructable infinities (Is the Continuum Hypothesis a Definite Mathematical Problem, Solomon Feferman (2011)). Is the fact that all logical thoughts must be constructable non-trivial, or.. what am I missing?

I mean, if a thought can't be constructed, then it can't be used in any consistent thinking process.. right? I mean, literally, how can any possible, hypothetical thought process ever rely on a thought that can't be reproduced? How could a law of Physics ever have an inconstructable concept, like absolute infinity, in it if no one - not even the person who wrote it - could think it?

It seems to me that any thinkable thing must have a construction process since we literally think by constructing thoughts. Sure that construction process might be stupidly complex and difficult to describe in classical formal language, but it must exist, prohibiting "absolute" infinities.

Ugh, sorry - this is bugging me.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Infinity is a trivially simple concept

someguy1,

Alright, this has been keeping me up, but apparently the relevant concept is an effective procedure (which I've been calling a "construction method"). Though, apparently, classical mathematics has been focused on effective procedures within certain sets of rules (axioms). Personally my main concern is that, because all procedures must be executed within the physical universe, all concepts can be generated by an effective procedure composed of physical interactions or be universally - in all possible sets of axioms - inconsistent.

So it's cool with me if an "absolute infinity" can't be constructed with some particular subset of all possible procedures (set of axioms). But, under no circumstances can an "absolute infinity" be fundamentally unconstructable; it must always be constructable under the set of all possible physical interactions.

I think that all infinities must necessarily be "potential" infinities, though in a subset of those cases (i.e. the legitimate "absolute" infinities) the build-up procedure (i.e. how the potential infinity is rigorously defined) is ignored for brevity.
Example:
In another thread I'd noted that, if we integrate the square of the Quantum Mechanics wave function over all space, we must get 1. I didn't specify any construction for the infinities involved in, say, the three spatial dimensions that we'd have to integrate over as their exact means of construction (e.g. recursive iterating all of them together, or at some specified rate relative to each other) is moot.

However, while I may not specify such a procedure, e.g. recursive iteration, there must exist at least one such possible procedure that I could've specified. This is, I can be ambiguous when the ambiguity doesn't prevent solution, but I can't use ambiguity as a cover for impossible (non-definable) procedures.

If I assert that the infinities are "absolute", i.e. they lack any such build-up procedure, then they cannot be generated and are thus inconsistent concepts that poison the system with inconsistency. (Though in this trivial example, most of us would automatically solve using an assumed build-up procedure such that we can execute the integration, even if told that we shouldn't, since it's a basic, natural way that we're used to operating.)

However, I'd think that most problems stated using "absolute infinity" should be reinterpretted as using an unspecified construction method (procedure) from the set of all applicable construction methods. Exactly which we then select matters if and only if the calculated result depends upon the selection.
• If there's nothing to select, then the problem is fundamentally inconsistent.
• If all possible selections lead to the same result, then the selection is moot and can be selected at the executor's (thinker's) will.
• If there's more than one possible result based on the selection of build up method, then the problem is ambiguously stated; its result, until further specification is provided, is indeterminant amongst the set of possible results from the possible (viable) procedures.

Stuff like cardinality can be simple and calculable when we have such procedures. In cases in which there are multiple, non-equivalent procedures that vary in ways material to the problem's solution, e.g. the Continuum Hypothesis, then the solution depends on mappings (procedures, whatever) that simply haven't been defined. Then it's an ambiguous problem as opposed to a complicated one, i.e. the solution is indeterminate.
Would you agree with this?
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Status of Cantor's 'Continuum Hypothesis'

Mod note
The split from the prior thread ends here. Posts below this point were made on this thread as opposed to the original thread.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009
 vivian maxine liked this post

### Re: Status of Cantor's 'Continuum Hypothesis'

There's so much here in this thread, far too much to address line-by line. Instead I'll present a framework in which you can hold to your philosophy of mind; but also come to accept the naturalness of noncomputable sets in mathematics. That's my goal.

Please note that I'm not talking much about CH here, since the themes you raised are peripheral to CH and I need to deal with those first. We can talk about CH later if that is still of interest to you. Personally I think studying noncomputability is interesting, particularly in this age of computation that we live in. Noncomputability is telling us something important that we can't quite yet grasp. Noncomputability is randomness; and a good part of life is random. Well, unless it isn't! That's what's at stake. Algorithms are deterministic. Free will requires randomness; and randomness requires noncomputability.

1) Philosophical preliminaries

You say the mind is a computer, or a computational process in the sense of computer science. You mentioned effective procedures, that's a good definition.

It would be pointless for me to try to refute your philosophy. Given the current state of human knowlege, the answer is unknown and essentially a matter of opinion, informed or not.

Instead I shall bypass the issue entirely. I say I don't care what the mind is. For this discussion I will stipulate to your computational worldview.

Whatever the mind is, one of its outputs is math. That is undeniable. Other outputs of the mind are the works of Salvador Dali, M.C. Escher, and the latest Star Wars movie. You don't sit in the theater and say, "There REALLY aren't any Wookies, you know. Harrumph!" You don't look at an Escher staircase and remark, "You couldn't really build that in the physical world. It's nonsense! Inconsistent!" You do not do that. So why do it with math?

Must math conform to known physical law? No. Not since the discovery of non-Euclidean geometry in the 1840's. From the time of Euclid we thought non-Euclidean geometry was a logical impossibility. In the 1840's we discovered that non-Euclidean geometry was a logically consistent branch of math that nevertheless made no possible sense in the physical world. Seventy years later Minkowski used non-Euclidean geometry to model the strange new physical ideas of some guy named Einstein.

https://en.wikipedia.org/wiki/Non-Euclidean_geometry
https://en.wikipedia.org/wiki/Hermann_Minkowski

The history of math is the story of one shocking and counterintuitive idea after another eventually finding widespread acceptance and application in physical science. From negative numbers through non-Euclidean geometry to the transfinite arithmetic, nonconstructive proofs, and noncomputable sets of today; you just never know how the future will regard a piece of math that seems nonsensical or nonphysical today.

So please, let's talk philosophy of mind in another thread if at all. Here, let's talk math. And when we talk math, let's take math on its own terms. Math has not been constrained by physics since 1840. Math is often strange. Just as an Escher staircase or a Star Wars movie or a wild dream is nonlogical yet somehow meaningful, so it is with math. Abstract art, fiction, and our dreams give us a glimpse of a world beyond logic that somehow informs our experience of this world. That's what math does. That's what math often is. A glimpse of the unknown and unknowable written in symbols.

Interestingly there is one output of the mind that IS required to conform to physical law: science itself. It seems to me your real beef should be with the modern speculative physicists (string theory, multiverse), who have broken loose from the traditional constraints of physical experiment and observation.

Math is free of physical constraint; yet even the wildest math often finds application in physics a few decades later. Keep an open mind about math, and accept it on its own terms.

2) The constructable universe is not what you think it is

L is a model but it hardly ends the subject of CH, anymore than the existence of Euclidean geometry precludes the existence of non-Euclidean geometries.

Gödel's constructible universe L is indeed a model of ZFC + CH. But why should this be a surprise? Of course there must be a model of ZFC + CH. Gödel cooked up a model of ZFC in which CH was true in order to show that CH is consistent with ZFC.

Then in 1963 Cohen surprised everyone by constructing (using that word technically, so that you would approve of Cohen's notion of constructability) a model of ZFC in which CH is false. That demonstrated the independence of CH from ZFC and won Cohen the only Fields medal ever awarded in mathematical logic. https://en.wikipedia.org/wiki/Paul_Cohen

Gödel's and Cohen's models are technical gadgets cooked up for the purpose of consistency proofs. There's no reason to think that Gödel's model is the true universe of sets. Most set theorists don't think so. Both Gödel's and Cohen believed CH is false.

For what it's worth, L is not any kind of computable paradise. The Axiom of Choice is true in L (that's the 'C' in ZFC) so that L is subject to all the usual anomalies of ZFC such as a well-ordering of the reals, a non-measurable set, a paradoxical decomposition of the sphere, a vector space basis of the reals over the rationals, the famous Hat paradox, and many other fables they tell the math majors.

I'm using the word fable ironically. Yes I agree that nonconstructive proofs are discomforting. But with practice one can learn to be comfortable with them! Perhaps what's bugging you is that you believe that everything is computable; yet you are starting to sense the dangerous allure of the forbidden realm of the noncomputable :-)

https://en.wikipedia.org/wiki/Axiom_of_choice
http://www.math.cornell.edu/~kbrown/4530/ordinals.pdf
https://en.wikipedia.org/wiki/Non-measurable_set
https://drexel28.wordpress.com/2010/10/ ... -r-over-q/
https://en.wikipedia.org/wiki/Prisoners ... ut_Hearing

Regarding CH in general, there's intensive research on CH at the forefront of set theory to this very day. CH acts strangely. It's been believed for years that if we could only find the right large cardinal axiom (LCA), it would settle CH one way or the other. But CH turns out to be independent of the usual LCA's. If you're a set theorist you find this interesting. I'm not a set theorist but I find what I understand of it to be fascinating.

https://en.wikipedia.org/wiki/Large_cardinal

3) Why should we believe in nonconstructive mathematical objects?

First, let's define constructive to mean computable, in the sense of computer science. Let's say that a set of natural numbers is computable if it's recursive or recursively enumerable, take your pick. I want to get away from L and "first-order definability with parameters," which is what L is built with. L is a very technical gadget, it's not helpful here. So let's just talk about plain old computable sets of natural numbers, or computable real numbers. Effective procedures if you like.

If you banish from math all the noncomputable sets, the real number line is full of holes. The Intermediate Value Theorem is false. The real numbers fail to have the Least Upper Bound property. They fail to be topologically complete. A Cauchy sequence of rational numbers may fail to converge. These defects violate every intuition we have about the continuum and about the real numbers.

https://en.wikipedia.org/wiki/Completen ... al_numbers

The measure of the computable reals is zero. If you randomly select a real number, the probability is zero that it's computable. If we restrict ourselves to computable sets, the real line is mostly made of holes. You can barely find a point on the line. If you throw a dart at the computable real line, you have zero probability of hitting any point at all.

https://en.wikipedia.org/wiki/Measure_(mathematics)

It's true that constructivist mathematicians have gone through the academic exercise of trying to rebuild a fragment of modern math along constructivist lines. I don't regard this as a useful activity. I can't think of anything that less models the continuum than the constructive real line. It's like using Swiss cheese to catch rain.

https://en.wikipedia.org/wiki/Constructive_analysis

So you have a choice: You can have the completeness of the real numbers; which is in fact the defining and essential property of the real numbers; or you can banish noncomputable sets from mathematics. That's your choice. Since completeness is the core intuitive concept of the real line, it makes sense to simply accept noncomputable sets into mathematics. If that make you uneasy, remember what John von Neumann said: "You don't understand math. You just get used to it."

https://en.wikipedia.org/wiki/John_von_Neumann

From a computer science perspective, some sets are computable and others aren't. The computable sets are the object of study of CS; and the noncomputable sets are studied by mathematics. The noncomputable sets are essential to our philosophical worldview, as they are necessary to the mathematical model of continuity.

I'd add that I'm puzzled by the common belief that just because we have computability theory, that therefore everything must be computable.

After all, one of the first things they demonstrate in computability theory is the existence of noncomputable problems. Right? Right. Halting problem and all that. So the pioneer genius computer scientists understood that noncomputability exists, just that it isn't part of the study of CS. It's only the modern students who don't seem to understand that there's a whole world of noncomputability beyond what CS can analyze.

In any event, Turing machines have infinite tapes. The abstract conceptual models of computation studied by computer scientists are no more physically realizable than the wildest nonconstructive objects in math.

If it's difficult to get our minds around bitstrings that can't be generated by an algorithm; we must remember that people didn't used to believe in negative numbers either. Or non-Euclidean geometry. Math teaches us to be open-minded about what we think makes sense. Just do the math. Leave value judgments to the future.

4) Sir Roger agrees with me

If the universe is computable, then there is no free will. If you wish to have any degree of free will, you must have a corresponding degree of noncomputability. Roger Penrose has made the point that consciousness requires noncomputability. To be fair this is one of his more speculative ideas and nobody agrees with him. But after all he's Sir Roger and we're not. It pays to have an open mind.

http://edge.org/documents/ThirdCulture/v-Ch.14.html

Conclusion

Now that we know that math is unconstrained by physical or computational considerations, we can talk about math if you like. I hope I've been able to clear out some of the peripheral issues. I'd be happy to drill down into anything you find of interest.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013
 Braininvat, Natural ChemE liked this post

### Re: Status of Cantor's 'Continuum Hypothesis'

someguy1,

Thanks for the reply! And I agree that:
1. it's easier to avoid point-by-point replies (the irony of including this in a list notwithstanding);
2. a discussion on computability would be more interesting than just CH for now;
3. the Wookie analogy is useful - I'd like to reference it later.

Just to get on the same page, you started your list of links for noncomputable stuff with the Wikipedia article on the axiom of choice. Since I feel that the axiom of choice is highly computable, I feel like I'm missing your point. Could you help me to understand what you mean by "noncomputable"?

I definitely want to hammer out such details early on since I don't want us to be arguing points based on different terminology - too many discussions end with folks realizing that they never disagreed on more than word choice. In this case I suspect that we may see some issues differently, though I'd definitely like to focus on those actual points of difference.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Status of Cantor's 'Continuum Hypothesis'

I have a weird (actually very practical!) habit of compulsively browsing things like Wikipedia when I'm thinking to pick up information on other stuff.

Found this link to Metamath that might be useful to this discussion later.
Basically, I figure that logical constructs have to be constructable in some way - though not necessarily within any particular system.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Status of Cantor's 'Continuum Hypothesis'

Natural ChemE » October 22nd, 2015, 10:04 pm wrote:Thanks for the reply! And I agree that:
1. it's easier to avoid point-by-point replies (the irony of including this in a list notwithstanding);

Well there was just so much context and if I replied point-by-point I'd miss the forest for the trees. I gather that I'm in the ballpark of your thoughts. That's good.

Natural ChemE » October 22nd, 2015, 10:04 pm wrote:
• a discussion on computability would be more interesting than just CH for now;

• Yes I agree. Noncomputability is everything that computers can't do. What does that even mean? Perhaps it's not for our century to know. It's a deep question.

Natural ChemE » October 22nd, 2015, 10:04 pm wrote:
• the Wookie analogy is useful - I'd like to reference it later.

• I'm glad you found that useful. My idea is to take math off its pedestal of having to be "true," and instead free it to be interesting. Knowing that we can always point to non-Euclidean geometry and say, "No matter how strange it seems, you have to accept it on its own terms ..."

Natural ChemE » October 22nd, 2015, 10:04 pm wrote:I definitely want to hammer out such details early on since I don't want us to be arguing points based on different terminology - too many discussions end with folks realizing that they never disagreed on more than word choice. =P

Yes definitely, one thing at a time with some degree of clarity.

Natural ChemE » October 22nd, 2015, 10:04 pm wrote:Just to get on the same page, you started your list of links for noncomputable stuff with the Wikipedia article on the axiom of choice. Since I feel that the axiom of choice is highly computable, I feel like I'm missing your point. Could you help me to understand what you mean by "noncomputable"?

Ok, it will take me a little time to write something up. AC is highly nonconstructive.

Here's one easy example. Say I take the real numbers, which have the rationals as a proper subset. I define a relation '~' (twiddle) such that for real numbers x and y, we say that x ~ y if x - y is rational. That's an equivalence relation so it partitions the real numbers into a collection of pairwise disjoint equivalence classes. Each class consists of all the reals that twiddle each other. Every real number is in exactly one such equivalence class.

https://en.wikipedia.org/wiki/Equivalence_relation

It's easy to see that each equivalence class is countable (why? Well maybe that's not so easy to see. The rationals are one class; the set of all rationals plus pi is another class, etc. You have to think about this a little); and that there are uncountably many equivalence classes. (If there were countably many, then the reals would be a countable union of countable sets, which it's not).

The Axiom of Choice (AC) is a principle of set theory that says that if we have a collection of nonempty sets; we may form a new set that contains exactly one element from each of the given sets. AC is independent of the other axioms of ZF, so AC is adjoined to ZF as a new axiom in a system we call ZFC.

Each of the equivalence classes under twiddle is a nonempty set (in fact each class is countably infinite) so by AC there is a set, which I'll call V, which contains exactly one member of each equivalence class. V is an important example in math; its existence is guaranteed by the Axiom of Choice; but you can not possibly tell me any computation or decision procedure that would identify any of the elements of V.

The more you think about V (and I hope you do spend a little time thinking about it) the more convinced you will be that the ONLY thing you know about it is that it exists by virtue of AC. You know NOTHING about its elements. Is 2 in V? I have no idea. Is pi in V? I have no idea. All I know is that V exists and contains exactly one member of each equivalence class under the twiddle relation.

V is an important example in math. V stands for Vitali, and what I've written so far is the beginning of the proof that there is a nonmeasurable set of real numbers, a set of reals that can not possibly have any sensible probability measure assigned to it. https://en.wikipedia.org/wiki/Vitali_set The remaining proof details are not important, other than to note that V's existence is given by AC but we can say nothing at all about V's actual elements.

I want to write up a couple of more examples, but they will take a little mathematical exposition hence some time, so give me a day or two for this. Suffice to say that AC is extremely nonconstructive.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Status of Cantor's 'Continuum Hypothesis'

Natural ChemE » October 22nd, 2015, 11:21 pm wrote:Basically, I figure that logical constructs have to be constructable in some way - though not necessarily within any particular system.

I confess I don't immediately see the relevance of that diagram, but let me get back to it after I write up a couple of more AC examples.

I don't know what you mean by a logical construct being constructible. Perhaps we should nail down terminology.

I was hoping we could restrict our attention to computability in the sense of algorithms. Effective procedures as you suggested. That's very sensible. The set of prime numbers is computable, there's an algorithm to crank out its members. There are uncountably many subsets of the natural numbers but only countably many algorithms, so there are many subsets of the natural numbers that have no algorithm and are not computable. This is a definition we can agree on.

By saying AC is nonconstructive, I only mean that AC guarantees the existence of sets whose elements can never be determined. AC has some very strange logical consequences that I'll discuss soon. I should mention that the negation of AC has unpleasant consequences too, so simply denying AC won't help. In this context "nonconstructive" only means that we can't tell what the elements of the set are.

If you have something very specific in mind as a definition of "constructing a logical construct" you should probably give the definition; or perhaps consider not widening the discussion too much at this moment into topics in which are not well defined. To be direct, I think we're making progress in not talking past each other, and I'd like to build on that.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Status of Cantor's 'Continuum Hypothesis'

Did the V example make any sense at all? I've been drafting a post in which I'd go through some proofs but really it's very time consuming to write that kind of thing. If you read the AC links I gave above you'll get the flavor of all the AC weirdness. Then I can respond to any specific questions. Suffice to say that AC gives nonconstructive existence proofs of some very odd things; and that mainstream math has been this way for about a century. The Banach-Tarski paradox says that you can divide a sphere in Euclidean 3-space into five pieces; move the pieces around in space using rigid motions; and reassemble the pieces into two spheres, each the same size at the original. The proof uses AC to conjure some set out of thin air that makes the proof work. https://en.wikipedia.org/wiki/Banach%E2 ... ki_paradox This proof was published in 1924. So it's clear that math has been nonconstructive and strange for at least that long.

Let me leave it that that. Should I take another run at the diagram you posted? I know it has meaning for you but I just am not following.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Status of Cantor's 'Continuum Hypothesis'

someguy1,

I think that I'm just having trouble understanding why this stuff is considered difficult. To attack the problem, I'd like to point out a Wikipedia statement that I think is wrong. If you can show me why my counter-argument is wrong, it'd help me to get on the same wave length.
Cantor's diagonal argument, Wikipedia wrote:Interpretation
The interpretation of Cantor's result will depend upon one's view of mathematics. To constructivists, the argument shows no more than that there is no bijection between the natural numbers and T. It does not rule out the possibility that the latter are subcountable. In the context of classical mathematics, this is impossible, and the diagonal argument establishes that, although both sets are infinite, there are actually more infinite sequences of ones and zeros than there are natural numbers.
I think that there are fairly trivial bijections between the set of all integers and the set of all reals.

For example, I can construct the set of all reals by:
1. Start by adding $0$ to an empty set.
• Add $0.1$ to the set.
• Add $0.2$ to the set.
• Add $0.3$ to the set.
• [...]
• Add $1$ to the set.
Now that the next base value has been added, we'll loop back.
• Add $0.01$ to the set.
• Add $0.02$ to the set.
• Add $0.03$ to the set.
• [...]
• Add $0.09$ to the set.
We'll skip $0.1$ since it's already in the set.
• Add $0.11$ to the set.
• [...]
• Add $0.99$ to the set.
We'll skip $1$ since it's already in the set.
• Add $1.1$ to the set.
• Add $1.2$ to the set.
• Add $1.3$ to the set.
• [...]
• Add $1.9$ to the set.
• Add $2$ to the set.
We just hit the next-integer addition, so now we loop back, expanding the precision depth of each prior integer by 1, as before.
• Add $0.001$ to the set.
• Add $0.002$ to the set.
• Add $0.003$ to the set.
• [...]
• Add $0.999$ to the set.
• Add $1.01$ to the set.
• Add $1.02$ to the set.
• Add $1.03$ to the set.
• [...]
• Add $1.99$ to the set.
• Add $2.1$ to the set.
• Add $2.2$ to the set.
• Add $2.3$ to the set.
• [...]
• Add $2.9$ to the set.
• Add $3$ to the set.
• Add $0.0001$ to the set.
• Add $0.0002$ to the set.
, etc. Also, whenever we add a positive member, we also add its negative in the next step. For example, after adding $1.01$, there's an implicit step in which we add $-1.01$ before progressing to $1.02$.

We can simultaneously construct the set of all integers by:
1. Add-and-iterate an integer indexer to the set of all integers whenever a non-negative member is added to the set of all reals.
Programmers will recognize this as `SetOfAllIntegers.Add(i++);`.
2. Add the negative of the integer indexer to the set of all integers whenever a negative member is added to the set of all reals.
Then the bijection can simply be that any member of either set directly maps to the member added to the other set during the same iteration of this procedure.

This yields:
1. Complete constructions for both the set of all integers and set of reals.
• A complete, direct 1-to-1 correspondence between the set of all integers and the set of all reals.
Under this construction, both sets have the exact same cardinality, right?

However I could also construct both sets together by adding integers to the set of all integers one at a time. And then each time I do so for any positive integer, I could add the infinity of all reals that round down to that integer to the set of all reals. And then mirror for negatives again. And under this construction, which seems to be more commonly done, both sets have the gradeschool interpretation of relative size.

Anyway, what's wrong with my bijection? Why does Wikipedia say that it doesn't exist?

PS - I selected this bijection construction to be simple to be illustrative, but it doesn't respect the quality that "3" in the set of reals must map to "3" in the set of integers (which I don't understand to be material to the problem). However, if this irks anyone, we can trivially assert that the bijection map is mutated upon addition of a new integer member to the set of all reals such that that particular mapping flips with the one that previously corresponded with the same integer element in the set of all integers. It's just an extra step in the construction procedure.

PPS - If anyone finds it irksome that the two sets overlap "until after infinity", alternatively we could apply the same extra step as above, except that the integer elements in the real set could follow some regular-but-non-blocking pattern, e.g. have integers at every second element in the set of all reals. Point is, tons of different ways to accomplish the same basic goal. We can just design the bijection to be whatever we like; it's all the same thing.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Status of Cantor's 'Continuum Hypothesis'

someguy1,

Just to note where I'm at, right now I'm confused about why particular constructions are preferred over others. For example, Cantor's diagonal argument is merely (and explicitly) a particular construction. However there's no fundamental reason to use that particular construction; others are possible.

And since there exist other constructions that demonstratively yield different results, then this confusion over infinities is merely a consequence of ambiguity. This is, the set of reals is of a higher cardinality if and only if you select a construction method in which there's no one-to-one correspondence while I've demonstrated a construction method in which the cardinality is the same; I see no reason that either construction is "wrong", so when talking cardinalities it feels like we necessarily must specify construction (or else refer to the solution as "indeterminate", as we do in other ambiguous cases).

My argument hinges on my assertion that other constructions exist - i.e. that Cantor's isn't the only one that's possible. So presumably I've either demonstrated my point by providing an alternative construction that yields a bijunction, or my provided alternative is somehow flawed in a way that I don't see. I'm assuming that the issue isn't this simple, so I feel that my bijunction must be flawed. But how?

PS - We can also trivially construct procedures in which the set of integers has a higher cardinality than the set of reals. This wouldn't seem to make much intuitive sense, but it's entirely possible and pretty simple to do. I note this to reinforce my point that, as far as I can tell, cardinality is a consequence of some arbitrarily selected construction method as opposed to being any fundamentally meaningful distinction.
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Status of Cantor's 'Continuum Hypothesis'

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:
I think that I'm just having trouble understanding why this stuff is considered difficult.

I suppose everyone assigns their own personal difficulty metric to things. It's not a point of mathematics, so let's put that aside.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:To attack the problem, I'd like to point out a Wikipedia statement that I think is wrong. If you can show me why my counter-argument is wrong, it'd help me to get on the same wave length.

(omitted the rest)

Where is 1/3 = .33333333... on your list? What you've done is enumerate the terminating decimals. Nice idea, but not a problem for Cantor since the set of terminating decimals is countable. There are finitely many terminating decimals of length 1; finitely many of length 2, etc; and the union of countable sets is countable.

After all, the set of rationals is countable, and the terminating decimals are a proper subset of the rationals. So the terminating decimals (which are what you've constructed) are countable.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:We can simultaneously construct the set of all integers

Yes of course. Uno, two-o, three-o, etc. Not a problem.

By the way, you are overloading the word "construct" again. We can in fact construct the real numbers, as for example Dedekind cuts. What we can't do is enumerate the reals, meaning place them in bijective correspondence to the natural numbers.

Dedekind cuts are one of the ways we can formally construct the reals within ZF set theory. It's not the only way. https://en.wikipedia.org/wiki/Dedekind_cut

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:Anyway, what's wrong with my bijection? Why does Wikipedia say that it doesn't exist?

Cantor's diagonal argument (which you have NOT provided a disproof of) shows that there's no bijection between the naturals and the reals.

There's another beautiful demonstration known as Cantor's theorem, which says that there is no bijection between a set and its powerset. Since the reals are easily bijectable to the power set of the naturals (ask me how!), the uncountability of the reals follows.

I strongly recommend that you walk through this beautiful proof. https://en.wikipedia.org/wiki/Cantor%27s_theorem
Natural ChemE » October 23rd, 2015, 8:39 pm wrote:PS - I selected this bijection construction to be simple to be illustrative, but it doesn't respect the quality that "3" in the set of reals must map to "3" in the set of integers

Not a problem. We can biject the natural numbers 1, 2, 3, ... to the even numbers 2, 4, 6, ... and nothing gets mapped to itself.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Status of Cantor's 'Continuum Hypothesis'

Natural ChemE » October 23rd, 2015, 9:51 pm wrote:someguy1,

Just to note where I'm at, right now I'm confused about why particular constructions are preferred over others.

I don't understand the question. Cantor himself provided several proofs of the non-countability of the reals. The diagonal argument was his SECOND proof, published years after his original, more topologically-based proof. And there's Cantor's theorem, which I mentioned in my previous post. So Cantor has at least three proofs of the same fact. It's not a problem to have multiple proofs.

Of course sometimes one proof is more elegant or more interesting than some other proof. For example (changing the subject a bit) there's a combinatorial proof of Fermat's Little Theorem; and there's a proof based on the binomial theorem. Those are accessible to high school students. But there's a beautiful one-liner that totally reveals the structure of the theorem, but that requires a little group theory. So there are often many proofs of the same fact at different levels of mathematical sophistication.

https://en.wikipedia.org/wiki/Proofs_of ... le_theorem

Natural ChemE » October 23rd, 2015, 8:39 pm wrote: For example, Cantor's diagonal argument is merely (and explicitly) a particular construction. However there's no fundamental reason to use that particular construction; others are possible.

Yes of course, Cantor published at least thee distinctly different proofs of the uncountability of the reals.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:And since there exist other constructions

Proofs, not constructions. As I pointed out, the real numbers can be constructed within ZF by Dedekind cuts. That's one way. Another way is as equivalence classes of Cauchy sequences. Or we can regard the reals as infinite bitstrings with a binary point in front of them, plus the integers glued on to the left. (That's the idea you attempted above, but incorrectly). There are lots of ways to get from here to there.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote: that demonstratively yield different results,

Oh no, that would not be possible if mathematics is consistent. By the way we know that ZF can't prove its own consistency, so for all we know the whole pile of cards will come down tomorrow morning. But if you had a proof of some statement P and also the negation of P, you'd have found a genuine inconsistency in math and you'd become famous.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:then this confusion over infinities is merely a consequence of ambiguity.

Any confusion you see is (so far) the result of your misunderstanding of standard results. I'm doing my best to provide clarity. I do hope you understand the main point of these two last posts, that you demonstrated the countability of the set of terminating decimals, which is in fact countable.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote: This is, the set of reals is of a higher cardinality if and only if you select a construction method in which there's no one-to-one correspondence while I've demonstrated a construction method in which the cardinality is the same;

Where does 1/3 = .3333... appear in your construction?

Natural ChemE » October 23rd, 2015, 8:39 pm wrote: I see no reason that either construction is "wrong", so when talking cardinalities it feels like we necessarily must specify construction (or else refer to the solution as "indeterminate", as we do in other ambiguous cases).

I hope I explained to your satisfaction that your idea is ambitious but wrong.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:My argument hinges on my assertion that other constructions exist - i.e. that Cantor's isn't the only one that's possible. So presumably I've either demonstrated my point by providing an alternative construction that yields a bijunction, or my provided alternative is somehow flawed in a way that I don't see. I'm assuming that the issue isn't this simple, so I feel that my bijunction must be flawed. But how?

Have I explained the flaw to your satisfaction? Where is the (nonterminating) decimal representation of pi - 3 in your list?

Natural ChemE » October 23rd, 2015, 8:39 pm wrote:PS - We can also trivially construct procedures in which the set of integers has a higher cardinality than the set of reals.

No of course you can't do that. But if you have an idea in mind I'd be glad to take a look and find the error.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote: This wouldn't seem to make much intuitive sense, but it's entirely possible and pretty simple to do.

Simple and wrong. You're just saying the same thing over and over now, and I'm just giving the same response. Your bijection excludes all the nonterminating decimal expressions.

Natural ChemE » October 23rd, 2015, 8:39 pm wrote: I note this to reinforce my point that, as far as I can tell, cardinality is a consequence of some arbitrarily selected construction method as opposed to being any fundamentally meaningful distinction.

No, you made a mistake, which I hope I pointed out to your satisfaction. You have .3, and .33, and .333, and .3333, and .33333, etc. But you do NOT have 1/3 = .333... That's the mistake.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

### Re: Status of Cantor's 'Continuum Hypothesis'

someguy1 » October 24th, 2015, 5:55 pm wrote:Where is 1/3 = .33333333... on your list? What you've done is enumerate the terminating decimals. Nice idea, but not a problem for Cantor since the set of terminating decimals is countable. There are finitely many terminating decimals of length 1; finitely many of length 2, etc; and the union of countable sets is countable.

After all, the set of rationals is countable, and the terminating decimals are a proper subset of the rationals. So the terminating decimals (which are what you've constructed) are countable.

The non-terminating decimal .33333333 in base 10 is the same number as the terminating decimal .1 in base 3. Can rational numbers that are non-terminating decimals in base 10 be made countable simply by expressing them in some base in which they are terminating decimals?

Irrational numbers are more problematic, since they cannot be expressed as exact numbers in any rational base. Could they be collected into a countable set by being expressed exactly (i.e. in a terminating form) in various irrational bases (e.g. pi as '10' in base pi, and e as '10' in base e)? Or is this illegitimate?
Positor
Active Member

Posts: 1058
Joined: 05 Feb 2010

### Re: Status of Cantor's 'Continuum Hypothesis'

Positor » October 24th, 2015, 6:04 pm wrote:
The non-terminating decimal .33333333 in base 10 is the same number as the terminating decimal .1 in base 3. Can rational numbers that are non-terminating decimals in base 10 be made countable simply by expressing them in some base in which they are terminating decimals?

They can be made terminating, for sure. But the total number of terminating decimals in any base will always be countable. Same proof I gave above. In any base there are finitely many decimals of length 1. For example in base three there are exactly three terminating decimals of length 1: namely 0, 1, and 2. (Implied "ternary" point in front of course).

There are finitely many lenghth-2 ternaries: 00, 01, 02, 10, 11, 22, 10, 21, 22. There are finitely many length-3 ternaries; and in general there are finitely many terminating ternary strings of length n.

Every ternary string is of SOME length so it's one of the length-1, length-2, etc. The set-theoretic union of the sets of strings of length n, over all n, is a countable union of finite sets. In discrete math or set theory class they prove that a countable union of finite sets is countable. (In fact a countable union of countable sets is countable too).

So no matter what the base is, even though different rationals become terminating; the set of all terminating rationals is still countable.

And of course in any natural number base, irrationals will still have infinitely long representations.

Positor » October 24th, 2015, 6:04 pm wrote:Irrational numbers are more problematic, since they cannot be expressed as exact numbers in any rational base.

Right.

Positor » October 24th, 2015, 6:04 pm wrote:Could they be collected into a countable set by being expressed exactly (i.e. in a terminating form) in various irrational bases (e.g. pi as '10' in base pi, and e as '10' in base e)? Or is this illegitimate?

Everyone casually says "Pi is terminating in base pi," but I've never seen the details worked out. Does uniqueness work? In other words does, say, sqrt(2) have a unique representation in base pi? I have no idea. I'm sure someone's figured this out.

Regardless, the set of rational numbers is countable and the set of irrationals is uncountable, and this is a statement about numbers and not representations of numbers. So in base pi, if we could work out the details, pi would be 10 I suppose. But there would still only be countably many rational numbers and uncountably many irrational ones.

It's worth repeating that Cantor came up with three completely different proofs of the uncountability of the reals, and only one of them involves decimal representations. His other two proofs don't use the decimal representation of a real number at all.
someguy1
Member

Posts: 654
Joined: 08 Nov 2013
 Positor liked this post

### Re: Status of Cantor's 'Continuum Hypothesis'

someguy1,

I feel that I understand this subject a lot better now. Thank you for your time in explaining it to me!
Natural ChemE
Forum Moderator

Posts: 2754
Joined: 28 Dec 2009

### Re: Status of Cantor's 'Continuum Hypothesis'

Natural ChemE » October 24th, 2015, 7:13 pm wrote:someguy1,

I feel that I understand this subject a lot better now. Thank you for your time in explaining it to me!

Oh you are very welcome. Thanks for raising so many stimulating issues. I hope you're not done! We've just cleared out the underbrush, the interesting stuff is ahead.

No matter, if anything occurs to you feel free to ask. You had such a huge rush of wild interconnected ideas ... did I manage to address most of it at some level?

Once you believe that the real numbers are uncountable, there are philosophical implications. I'll talk about this a little.

A real number is computable if it can be approximated to any desired precision by an algorithm. Another way of saying this is that we can crank out as many decimal digits as we like. So .5 is computable, we just say, "1/2 in decimal." Pi is computable, we just program one of the many closed-form expressions for pi, such as the Leibniz formula pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 ...

https://en.wikipedia.org/wiki/Leibniz_f ... for_%CF%80

How many computable numbers are there? Well, how many algorithms are there? The computer scientists have formalized the idea of program or algorithm into the abstract idea of the Turing machine (TM). A Turing machine program consists of a finite sequence of instructions, written in some formal alphabet.

https://en.wikipedia.org/wiki/Turing_machine

If the alphabet is either finite or countable, then we have a very familiar-looking proof that there can be only countably many TMs. Each TM is a finite sequence of instructions so it has some length.

There is a countable set of TMs of length 1. There is a countable set of TMs of length 2 (Why? Because countable x countable = countable. Discrete math class again. You can look up that proof).

Dot dot dot ... there is a countable number of TMs of length n. Taking the union of all the TMs over all the natural numbers n, we have a countable union of countable sets. There are only countably many Turing machines hence only countably many computable numbers!!

This has DEEP philosophical implications.

If the information content of the universe is finite, the universe is the output string generated by some computer program. Deterministic down to the last bit.

If there is any degree or hope of free will or randomness in the universe; then the state of the universe must be noncomputable hence must contain infinitely much information. That is, it's a random bitstring.

Now imagine God is creating universes. She flips a fair coin infinitely many times. She's God, she can do that. She writes down the sequence and says, Ok, that's the universe.

The probability that she flipped a computable universe is zero. The probability is 1 that the universe is noncomputable; in other words, totally random. There is no algorithm. It's a random bitstring and there's no pattern. If you managed to make a cup of coffee this morning it's a completely random event. Sounds unlikely? It's even more unlikely that there's any order to it.

It's more likely we live in a completely random universe than a computable one. That's in the infinite energy case. But if the information content of the universe is finite, we're just a pinball game.

ps -- This is what I am trying to say about it. I completely agree with you that with our current understanding of physics and computer science, it certainly looks like the entire universe is a computer program.

But in that case ... the mathematical notion of noncomputability is perhaps analagous to how non-Euclidean geometry was viewed before Relativity. A mathematical curiousity that did not conform to the real world.

If the noncomputable reals, and all those un-nameable points in the continuum, are not regarded as real this century; may they not be part of the physics of the next? Could noncomputability someday be seen to be an essential part of nature? My thesis is this: The noncomputable reals are trying to tell us something!

My favorite numbers are the noncomputable ones. I can't name any of them. That's a feature, not a bug :-)

As the Tao Te Ching says: The name that can be named is not the eternal name

Or as I myself would put it: The universe that can be computed is not the eternal universe.

https://en.wikipedia.org/wiki/Tao_Te_Ching
someguy1
Member

Posts: 654
Joined: 08 Nov 2013

Next