Wikipedia:Reference desk/Archives/Mathematics/2020 November 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 27

Reals are countable: an informal proof, I think..

On the science desk I invented what I called an apple machine to distribute apples to the natural numbers here. We can't multiply infinities or even append them in the usual sense without duplicity. But we can iterate everything in lockstep parallelism such that the infinite sequences have bijections between them and complete them.

I will now count the positive reals as we understand them today, too. Consider a tree, each node has two children. The two edges powers of twos, one to add to the leading natural part and the other to append to its finite fraction part before arriving at the next node. Thus, the first two childrens' node values are 0.0 0.1 and 1.0 1.1 the next level nodes give us four digits: xx.xx, followed by six: xxx.xxx, etc. We complete the tree level at infinity. To make it explicit that we are counting them, add powers of 2 and tally those 0 0.0 0.1 and 1 1.0 0.1, then the tree's leaf nodes at infinity counts the naturals times 2 with the sequence {0 2 4 6 8 ...}.

Since Cantor's counting procedure with his diagonal argument did not iterate every real number with lockstep parallelism, his argument is a strawman. His other proofs regarding intervals don't even apply, I think.

Thanks in advance for either fixing my mistakes, making sure I'm published, or proving me wrong.

I was fixing some of my worst mistakes after JBL replied. Sorry, I posted prematurely.

--Modocc (talk) 18:20, 27 November 2020 (UTC)

A proof (even an "informal proof") should have a logical structure in which statements follow from others for clearly articulated reasons, terms used are clearly defined, etc. --JBL (talk) 19:23, 27 November 2020 (UTC)

I'm working on it. If anything I write is unclear or just plain wrong let me know. --Modocc (talk) 19:31, 27 November 2020 (UTC)

It is extremely poor form to edit your comments after they have been responded to: it falsifies the record of the conversation, making it appear that my response was to something else. If you are not ready to go live with your comment, you shouldn't put it here -- go work on it in your sandbox or something, instead. What you'd written initially was incoherent from top to bottom; I do not think there was even one sentence to which I can associate a precise, unambiguous meaning. Since then, you have added something that makes it appear that you've rediscovered the fact that a countably infinite binary tree contains uncountably many countably infinite paths leading away from the root. You would not be the first person to wrongly think this is somehow a disproof of Cantor (note spelling). But it's not in conflict any more than the fact that a countably infinite set has uncountably many subsets is. --JBL (talk) 20:08, 27 November 2020 (UTC)

I didn't see your reply and I made way too many mistakes and was hoping to fix them. I'd repost if it helped. Strawman arguments can be difficult to disprove and I fixed the leaf nodes count since you posted. I will leave this completely alone now and repost later with diagrams and everything I can think of to remove the ambiguities, typos, etc. I think I've discovered the opposite fact: that a binary tree faithfully representing the reals is countable. I hope to get my points across too.--Modocc (talk) 20:20, 27 November 2020 (UTC)

OK I see that I panicked while trying to verify the counts and preceded todestroyed my own work. -Modocc (talk) 23:56, 27 November 2020 (UTC)

There is no problem in creating a bijection between the nodes of an infinite binary tree and the natural numbers. What is uncountable are the infinite paths in the tree. Cantor's argument does not depend on any concept of a process producing the collection of real numbers – whether by drudgery, lockstep parallelism, or apparition. He simply shows that given a sequence S of infinite bitstreams, there is some bitstream that does not occur in the sequence. Although Cantor does not explicitly use the concept of countability (he characterizes his result as being a proof that there are cardinalities that cannot be brought into one-to-one correspondence with the set of natural numbers), the definition of a countable set is basically that its elements can be presented as a sequence.  --Lambiam 00:17, 28 November 2020 (UTC)

The tree, by definition when done correctly, contains, all points that are listed on the real number line. Also trees can be deconstructed and reassembled to be binary. So we can use the procedure of broadening the binary tree of binaries with signs and the fraction part, but also reconstruct it so its binary again and its infinite leaf nodes should be countable per my previous work. Now place the binary representation of Pi on Cantor's diagonal and list everything not Pi. So the list is, logically, incomplete and it is! If you don't allow for an exhaustive list you can't prove anything. Its a black swan fallacy too, "the diagonal" is not on the number line: until its actually found and contradicts the premise not Pi. Likewise take any diagonal and place it in the tree, its there ready to be listed as a point on the real number line because the tree and the line are exhaustive and covers all of its numbers. -Modocc (talk) 01:52, 28 November 2020 (UTC)

... and you're back to incoherent. This stuff was really surprising and groundbreaking when Cantor first came up with it, and it's still somewhat counter-intuitive, but it's not new any more. There are many wonderful treatments of the basics (the construction of the real numbers, countability and uncountability, diagonal arguments, ...) out there. You should spend your time reading about and learning and understanding these wonderful ideas that people have built up. --JBL (talk) 02:15, 28 November 2020 (UTC)

The people responding to you are right. The nodes are countable, but if you stop at any one of them, you have a terminating decimal, which is rational number. Almost all real numbers (all non-rational numbers) are an infinite distance down one of an infinite number of paths. Bubba73 ^{You talkin' to me?} 02:33, 28 November 2020 (UTC)

Yes, I know, please read the thead here regarding finite vs the infinite and then we might have something new to talk about. -Modocc (talk) 03:14, 28 November 2020 (UTC)

Your comments in that thread are also incomprehensible, in the same way your initial post here was. The weird but true reality is that there are countably many finite subsets of the integers, but uncountably many infinite subsets; dressing things up in terms of binary trees or the real numbers or both does not change that. --JBL (talk) 03:33, 28 November 2020 (UTC)

"I'll add that we can ignore the tree and just exponentially duplicate the bot an infinite number of times with instructions as to what to do with the apples". Its mindbogglingly trivial to ask these bots to give you guys a pi, the entire thing. Now place its ones' complement on Cantor's diagonal. How does his argument still hold? -Modocc (talk) 04:14, 28 November 2020 (UTC)

A proof should have a logical structure in which statements follow from others for clearly articulated reasons, terms used are clearly defined, etc. Asserting that something incoherent is "mindbogglingly trivial" shows that you don't understand what you're talking about, but not much else. Making countably many binary choices allows one to generate uncountably many possible results; more generally no set can be put in bijection with its own power set. (Maybe that uses choice? But since you're going on about how making infinitely many choices is "mindbogglingly trivial" presumably you don't object.) --JBL (talk) 13:08, 28 November 2020 (UTC)

Since you have struck out the purported construction of the tree, it is not clear what we are arguing about. You claim to have a disproof of a generally accepted mathematical result – the impossibility of constructing a one-to-one correspondence between the integers and the reals. There are people who claim to have disproofs of other generally accepted mathematical impossibility results – the impossibility of trisecting the angle, or doubling the cube, or expressing pi as the ration of two whole numbers. Some devote their whole life to this, filling treatises with their rambling "proofs", having them printed at their own cost, and sending them to leading mathematicians and institutions around the world. There is a name for such people. Do not become one of them.  --Lambiam 10:04, 28 November 2020 (UTC)

@Modocc: You claim: 'The tree, by definition when done correctly, contains, all points that are listed on the real number line.' But that's false. Apart from absurd term 'listed' (as a list is typically understood as a sequence, hence often finite and at most countably infinite), the tree does not even contain all rational numbers. It contains, by definition, only non-negative real numbers with finite decimal expansion, so it lacks e.g. 1/3, let alone irrational square root of 13 or transcendental pi. --CiaPan (talk) 16:50, 29 November 2020 (UTC)

See also here: "LST has bite because we believe that there are uncountably many real numbers (more than $\aleph _{0}$). Indeed, let's insist that we know it; Cantor proved it in 1873, and we don't want to open the question again. What is remarkable about LST is the assertion that even if the intended interpretation of S is a system of arithmetic about the real numbers, and even if the system is consistent and has a model that makes its theorems true, its theorems (under a different interpretation) will be true for a domain too small to contain all the real numbers. Systems about uncountable infinities can be given a model whose domain is only countable. Systems about the reals can be interpreted as if they were about some set of objects no more numerous than the natural numbers. It is as if a syntactical version of "One-Thousand and One Arabian Nights" could be interpreted as "One Night in Centerville".

This strange situation is not hypothetical. There are systems of set theory (or number theory or predicate logic) that contain a theorem which asserts in the intended interpretation that the cardinality of the real numbers exceeds the cardinality of the naturals. That's good, because it's true. Such systems therefore say that the cardinality of the reals is uncountable. So the cardinality of the reals must really be uncountable in all the models of the system, for a model is an interpretation in which the theorems come out true (for that interpretation). Now one would think that if theorems about uncountable cardinalities are true for a model, then the domain of the model must have uncountably many members. But LST says this is not so. Even these systems, if they have models at all, have at least one countable model." Count Iblis (talk) 12:32, 28 November 2020 (UTC)

I do not think that the Löwenheim–Skolem theorem is relevant to the OP's concerns about Cantor's theorem. For example, it seems pretty clear that the OP would reject the notion that they are discussing models of formal theories. --JBL (talk) 13:28, 28 November 2020 (UTC)

It is also of some relevance (although probably not to the OP's claim) whether one accepts the Schröder–Bernstein theorem that a pair of mutual injections between two sets implies the existence of a bijection. This cannot be proved in constructive set theory, so not all mathematicians accept it. Without S–B, the assumption of an injection $\mathbf {2^{N}} \hookrightarrow \mathbf {N}$ next to the obvious $\mathbf {N} \hookrightarrow \mathbf {2^{N}}$ is not necessarily absurd.  --Lambiam 14:30, 28 November 2020 (UTC)

The proof that there is no surjection from N onto 2^N is intuitionistically valid. It's true that you can't automatically get from there to the nonexistence of an injection from 2^N into N, using only intuitionstic logic, even though it would seem straightforward enough: Suppose there were such an injection f: 2^N→ N, then you recover a surjection in the other direction by assigning to every n in N the unique element x of 2^N such that f(x) = n, if there is one, and 0 otherwise. This doesn't even need the axiom of choice. Now you have a contradiction via the proof that there's no such surjection.

The hiccup is that the definition by cases is silently assuming that the proposition "there is an x such that f(x) = n" is either true or false, and this you cannot do in intuitionistic logic.

That said, I don't actually know whether it's consistent with intuitionistic set theory that there's an injection from 2^N into N. I would be interested to know. What is apparently consistent is that the reals are subcountable; that is, that they're a subset of a countable set, though not actually countable themselves. --Trovatore (talk) 20:57, 29 November 2020 (UTC)

One can consistently defend the position that the only "real" reals are the computable reals; all others are delusional figments of a non-constructive mind. The set of computable reals is closed under all algebraic operations, but also under limits, given a (constructive) proof that successive approximations are contained in shrinking intervals that get as small as you want. Equivalence and therefore equality is undecidable, as one would expect. Since each computable real is computed by some Turing Machine (TM) which has some unique number, there are not "more" real reals than there are naturals. But since we have no way to decide whether a given TM computes a number, we cannot use this to enumerate them. To be precise, an allegedly number-producing TM needs to carry a certificate with a proof that it is properly productive. However, since it is not possible to nail down when a purported text is a valid intuitionistic proof, this requirement does not help. Like the "real" real numbers, the "real", non-illusionary members of 2^N correspond to a computable function ƒ: N → 2, with all the same issues regarding the TMs computing them. Allowing the intuitionistic mind to get contaminated with a tinge of classical delusions, imagine we have an oracle that, given a bitstream – finitely presented as the number of a TM computing it – produces the lowest number among all TMs computing that same bitstream. The oracle, viewed as a fictitious function applied to "real" bitstreams, thus is an injection from 2^N to N. If the assumption of such an oracle be inconsistent in intuitionistic set theory, I bet we can formalize enough constructive mathematics inside classical mathematics – which has no qualms regarding the existence of such oracles – that the inconsistency carries over to the classical realm.  --Lambiam 23:37, 29 November 2020 (UTC)

Honestly I don't think you can get a coherent realist ontology out of the view that 'the only "real" reals are the computable reals', as you put it. If the computable reals really exist, as well-specified objects, then it's really hard to understand why 0' (pronounced zero-jump), the real that codes the solution to the halting problem, should not.

What you can claim coherently (if rather limitingly) is that no reals exist at all, but that we can talk about computable reals as shorthand for talking about the programs that compute them, which are finite objects. But it's undecidable in general whether program n computes the same real as program m, so it's of somewhat limited usefulness.

As to your program for finding a contradiction above, I have my doubts. As a general rule intuitionistic systems simply prove fewer things than classical ones, not different things. The existence of the oracle you're talking about is probably not inconsistent with intuitionistic set theory; just not proved by it. Still, I'm not saying it's hopeless; it could be that there's some other proposition (classically easily seen to be false) that's consistent with the intuitionistic view, and that refutes the existence of the injection. But I don't know what it would be. --Trovatore (talk) 00:20, 30 November 2020 (UTC)

As to my "program for finding a contradiction", I thought it was clear that I do not expect a contradiction to exist; as I wrote, many lines above, "Without S–B [as in IM], the assumption of an injection $\mathbf {2^{N}} \hookrightarrow \mathbf {N}$ [...] is not necessarily absurd." What I was arguing is that if the assumption of the existence of an injection (or even the stronger assumption of an oracle providing a specific one) leads to a contradiction in IM, then it leads to a contradiction in CM. Of course such an oracle is as fictitious as other things rejected by IM; the function is provably not computable. For the rest, to a constructivist, π, √2, π/2+√2, the least positive root of X¹³-X-1, and so on, are the normal reals, while Chaitin's constant is not a real number, period. As long as this is mathematically consistent, why should one care whether it is a coherent realist ontology?  --Lambiam 01:23, 30 November 2020 (UTC)

Well, you said "not necessarily". It wasn't clear to me whether you thought there was no contradiction, or just that you didn't know how to find one. My impression from a long-ago conversation with someone who seemed to know a little more about it than I did is that there is a contradiction, though I don't know how to find it.

When you start talking about what's real and what's fictitious, you're no longer really talking purely about what is "mathematically consistent"; you're now doing philosophy. To me, it is important in philosophical terms whether the ontology is coherent.

I do grok intuitionism a little bit (I studied with Giovanni Sambin), and I've thought about some of these issues a bit. As far as I can see it doesn't make sense to say that computable reals are real objects and noncomputable ones are not. The intuitionist who rejects 0' (more to the point than Chaitin's constant, though equivalent for these purposes) doesn't really believe in π as a real object, say a completed infinite collection of rationals (using the Dedekind-cut formulation), but only as a way of choosing some rationals and not others. In other words, this intuitionist really only accepts the program, not the completed computation. It's confusing and inaccurate to equate this with accepting the real number π itself. --Trovatore (talk) 02:54, 30 November 2020 (UTC)

The formulation "accepting the real number π itself" suggests mathematical Platonism. For each type of mental object, one needs a notion of what it means to "construct" it. For philosophical purposes, π is a lawlike choice sequence. Its construction can be completely described by a finite, constructible object, its birth certificate so to speak. That is good enough (for a "standard" intuitionist; ultrafinitists are another story). My personal view is that for any logic with any collection of axioms and inference rules, all models "exist" and none is more real than another – much the same way as that, when leaving out the parallel postulate, there are different models of geometry. Each model is a mathematical universe on its own; some are more interesting than others. They can be practically useful but ugly, or beautiful yet useless. In any case, by writing "real" in scare quotes, I meant an antonym of "fake" – to a constructivist, 0' and Ω are fake, impostors – their birth certificates are missing; they are from another universe.  --Lambiam 10:55, 30 November 2020 (UTC)

But this is just the thing! Constructivists typically are Platonists! Just about a restricted collection of entities. They are explicitly not formalists; their defining conflict was with a formalist, Hilbert, not with a Platonist like Goedel.

Once you start drawing the line between real and fictitious entities, you have entered into the Platonist arena; there is no escaping that. And the line between computable reals and non-computable ones is simply not a coherent place to draw the line between real and fictitious. What you can do is be a Platonist about the programs that compute computable reals, and accept the reals they compute as a fiction. But in that case you can't reify the computed real, if for no other reason than because it is undecidable whether two programs compute the same real.

As for this realism-about-models viewpoint, it's not coherent either. Once you accept models as real, it's hard to see why you shouldn't compare them. And when you start doing that, it's not too long before you wind up with the von Neumann universe as a well-specified thing, and conclude that (for example) the continuum hypothesis has a definite truth value, even if we don't know what it is. Realism-about-models (or "full-blooded Platonism" or "plenitudinous Platonism" or "many worlds") works out to be really just formalism in the end (or, possibly, the view that all sets are hereditarily countable and that the reals form a proper class; that's a different flavor that would need to be discussed separately). --Trovatore (talk) 18:11, 30 November 2020 (UTC)

I don't think this discussion should be about my personal philosophical viewpoint, but I deny that I am a closet Platonist. I have noticed that adopting a strict formalist approach can lead to much the same mathematics as constructivism – as long as you do not observe what the mathematician thinks, or says about their work, but only the proofs they give, you may not be able to see the difference. Les extrêmes se touchent. But to discuss why one rejects a proposed proof, one needs some common ground, however shaky. All I wanted to say was that certain assumptions – unprovable ones – cannot be disproved either in certain frameworks. Wittgenstein wrote, Die Welt ist alles, was der Fall ist. The theory of a logic, by which I mean the collection of propositions that are provable in that logic, is all that is the case in that logic: it is a universe. I think that most sociologists these days will agree that reality is a social construct. The arguments apply (in my opinion) equally to mathematical reality. How real is socially constructed reality really? Is it more than an agreement? In the case of mathematics, the issue is in the end which proof methods are considered acceptable. If someone considers tertium non datur acceptable and even obvious, there is no logically compelling argument to convince them otherwise – and the other way around.  --Lambiam23:00, 30 November 2020 (UTC)

I'm no mathematician but if the reals are countable then what's the first positive real? What's the second one? Sagittarian Milky Way (talk) 23:35, 28 November 2020 (UTC)

Sagittarian Milky Way The rational numbers are countable, and yet there is no first positive rational (at least if by "first" you mean "smallest") -- the question of order type is separate from the question of cardinality. --JBL (talk) 23:56, 28 November 2020 (UTC)

I see. So 1/1, 1/2 etc 2/1, 2/2 etc ... googolplexx/1, googolplex/2 etc. Sagittarian Milky Way (talk) 00:55, 29 November 2020 (UTC)

If "1/1, 1/2 etc" means 1/1, 1/2, 1/3, 1/4, ..., 1/n, ... (for all n in N), this never reaches 2/1. (What would be the last fraction before 2/1?) You can instead go by diagonals: 1/1; 2/1, 1/2; 3/1, 2/2, 1/3; 4/1, 3/2, 2/3, 1/4; ...; n/1, (n−1)/2, (n−2)/3, ..., (n+1−m)/m, ..., 2/(n−1), 1/n; ... – except that 2/2 = 1/1, so it should be skipped, as should all fractions that can be reduced, and so 5/1 is immediately followed by 1/5 because each of 4/2, 3/3 and 2/4 can be reduced and have already had their turn in a simpler form. See Cantor pairing function, whose inverse yields this enumeration of the pairs (n+1−m, m) of these fractions (except for only positive integers being used here, skipping pairs containing a 0).  --Lambiam 08:27, 29 November 2020 (UTC)

And interleave minus 1/1, -2/1, -1/2 and so on and start with zero? Sagittarian Milky Way (talk) 16:16, 29 November 2020 (UTC)

Yes, sorry, I got confused by the remark of there being no first positive rational and described a way of enumerating the positive rationals only. Any of several ways will do to get all. An easy modification of the positive enumeration is to start with 0 and to follow each positive rational p/q immediately by its negative opposite −p/q, giving: 0/1, 1/1, −1/1l; 2/1, −2/1, 1/2, −1/2; 3/1, −3/1, 1/3, −1/3; ...  --Lambiam 20:55, 29 November 2020 (UTC)

Is this related? 1/3rd is infinity levels down a tree of "bisect the integers, repeat". Sagittarian Milky Way (talk) 19:42, 29 November 2020 (UTC)

You forgot to rinse. The values of the nodes on an infinite path to the level where we see $\epsilon$ and $\omega$ appear (if you have very good eyes) do not necessarily converge to a real number, but each real number is either the value of some node, or the limit of the node-values of some infinite path to that level. I do not see how this is either relevant or irrelevant; the picture is pretty far-out, though.  --Lambiam 20:58, 29 November 2020 (UTC)