What online class should I take to learn more about this topic in particular?
How many real numbers exist? New proof moves closer to an answer
221–230 of 359 posts
Re: How many real numbers exist? New proof moves closer to an answer
#222Earlier quoted context omitted.
It's not "okay" because such a system proves that various particular Turing machines halt when, in fact, those machines do not halt. See https://news.ycombinator.com/item?id=27847719 . But to be a bit more specific, ¬Con(ZFC) says that the Turing machine that searches for a contradiction in ZFC does indeed halt. However (in all likelihood) such a machine does not actually halt, in the sense that it does not halt in 1…
> such a system proves that various particular Turing machines halt when, [ ]in fact[ ], those machines do not halt. Er, no. The fact is that there is no fact of the matter as to whether those particular Turing machines either a: do not halt at all, or b: halt after a (colloquially) infinite number of steps. (A implication of there being no fact of the matter is that, empirically, we can't tell the difference by runn…
ZFC+¬Con(ZFC) either wrongly proves that the machine that searches for an inconsistency in ZFC halts, or it wrongly proves that `while(true)` halts. Either way ZFC+¬Con(ZFC) is wrong about something.
Re: How many real numbers exist? New proof moves closer to an answer
#223A related thing that occurred to me the other day: there's some number in [0, 1] that encodes every state of every possible Turing machine (the number of Turing machines is countable, the duration of its run is countable, and the states at each step are countable, so you can diagonalize that and make a real number out of it). I'm pretty sure you can take that further and show that all possible mathematical proofs, in…
This sounds a little like Chaitin's constant Omega (Ω), which is very roughly a number in [0, 1] which is the probability that a randomly chosen program (for a universal Turing machine, U) will halt.
This has the interesting property that knowing the first n bits of Ω allows you to determine whether any program (for U) of length up to n will halt, in other words you could solve the halting problem for programs of length up to n.
As Wikipedia puts it:
> Because many outstanding problems in number theory, such as Goldbach's conjecture, are equivalent to solving the halting problem for special programs (which would basically search for counter-examples and halt if one is found), knowing enough bits of Chaitin's constant would also imply knowing the answer to these problems. But as the halting problem is not generally solvable, and therefore calculating any but the first few bits of Chaitin's constant is not possible, this just reduces hard problems to impossible ones, much like trying to build an oracle machine for the halting problem would be.
Re: How many real numbers exist? New proof moves closer to an answer
#224The mileage of others may vary, but it has been my experience that there is no cogent solid proof of uncountability that can withstand concerted critique.[0] Being charitable one might argue that the meanings of terminology had been lost in translation over time and that perhaps Cantor was trying to create non-standard analysis, but then the diagonal argument seems to represent nothing more than the truism that finit…
This presents a confused understanding of Cantor's diagonalization argument.
You are shrouding in complexity something that is straightforward. The complete proof of distinct infinite cardinalities can be stated succinctly and clearly in only a few lines, without referencing the reals at all. You don't need to vaguely refer to "four steps", you should precisely elaborate the steps of the proof you view as problematic.
First, forget the reals. Let's establish that there are sets that are infinite yet uncountable.
----
"Uncountable" means that there is no bijection with (a subset of) the natural numbers.
An "infinite sequence of A's" means a function ℕ → A. For convenience, I'll denote the set of infinite sequences of A's with `A**` -- this is not standard notation.
Theorem: There is no bijection between ℕ and {0, 1}**.
Proof: Suppose for contradiction that there is a bijection f: ℕ → {0,1}**.
Define a function z(n) = 1 - f(n)(n).
z is clearly well defined and is clearly a member of {0,1}**.
Since f is a bijection and z is in the codomain of f, there is an element k of ℕ such that f(k) = z.
However, z(k) = 1 - f(k)(k). Yet f(k) = z, so z(k) = 1 - z(k).
This is a contradiction. So, the assumption (that there exists a bijection f: ℕ ↔ {0,1}**) must be false.
Q.E.D.: There does not exist a bijection between ℕ and {0, 1}**.
----
The linked paper claims that the above proof would work on a bijection of the form ℕ ↔ [ℕ] or ℕ ↔ [ℚ] (where the [] indicate some suitable representation of the set as sequences of bits; again, not standard notation), but that is mistaken: crucially, the constructed function `z` must be a member of the codomain of `f`. The construction 1 - f(n)(n) does not necessarily lie in that set when the set only permits _certain_ bit-sequences!
For example, consider an encoding [ℕ] which is "one-hot"; the natural n is encoded as a function y(n) = 1 and otherwise y(k) = 0. Then there is an obvious bijection `f`: f(a, b) = 1 when a=b and otherwise 0. What is `z` for such an `f`? z(k) = 1 - f(k, k) = 1. So, `z` is not a member of [ℕ].
For a more involved example, consider an encoding of [ℕℕ] that is a unary-encoding of the first natural, followed by a single zero, followed by a unary encoding of the second natural, and followed by only 0s. (The rationals correspond to a subset of these). A standard bijection has the pairs appear in the order of their sum: (0, 0), (0, 1), (1, 0), (2, 0), (1, 1), (0, 2), ... It's an exercise left for the reader that z constructed on this set does not encode to a unary number, followed by a single zero, followed by a unary number, followed by only zeros.
----
If you have an issue with cardinalities, I expect it can be found in the above proof and does not actually lie with the reals. But, for completion, to tie in the real numbers, it's necessary to show that {0,1}** is bijective with ℝ, or with (0, 1). This falls out from the Cauchy-sequence definition of ℝ. For a sequence y : {0,1}** the sequence z(k) = y(0) + 1/2·y(1) + 1/4·y(2) + 1/8·y(3) + ... + 1/2^k·y(k) is clearly a Cauchy sequence with a limit in the interval [0, 1]. It's also straightforward to check that every real number in the interval [0, 1] is the limit of one such Cauchy sequence.
Re: How many real numbers exist? New proof moves closer to an answer
#225Maybe I misunderstood the article but if the set of real numbers is finite then it should be countable. But I can easily prove that the set of real numbers or any subset of real numbers is not countable. Been a really long time since I’ve thought about this but wondering what I’m missing.
No, what the article is talking about is the question whether or not the cardinality of real numbers is the smallest uncountable infinity or some other, larger uncountable infinity. The only countable infinity is aleph-0, the cardinality of natural numbers, and Cantor showed that aleph-0 is too small to hold all reals. So reals must be uncountable, but there is an infinite hierarchy of uncountable infinities, and it…
(although in practice it's suspected to be either aleph-1, which is what the Continuum Hypothesis states, or aleph-2)
There are some arguments that it's "really" much larger, as in greater than aleph-n for any finite n. See https://risingentropy.com/the-continuum-hypothesis-is-false/ (incidentally an excellent blog if you're interested in these sorts of things).
Re: How many real numbers exist? New proof moves closer to an answer
#226Man there's a lot of juicy stuff in this article (Woodin's Ultimate L program gets briefly alluded to at the end of the article). I just want to point out, because the HN crowd seems to generally not be mathematical Platonists, that this entire article is implicitly assuming a Platonist philosophical foundation. This may cause confusion for lay readers who are not mathematical Platonists. In other words the article a…
> this entire article is implicitly assuming a Platonist philosophical foundation Is mathematical platonism still significant position between mathematicians? I thought it is outdated since Lobachevsky.
I thought it was outdated since Epimenides. It requires the axiom of the excluded middle, which is about as false as axioms can possibly be, on account of having concrete counterexamples. (eg "This proposition is false.")
Re: How many real numbers exist? New proof moves closer to an answer
#227Re: How many real numbers exist? New proof moves closer to an answer
#228Earlier quoted context omitted.
> he resulting system is unsound (in the sense of Tarski) because it asserts the existence of natural numbers that have no "written form" (i.e. the existance of natural numbers that are larger than any term you can write to denote a natural number). Isn't that basically the definition of the natural numbers, ie. if you write down any natural number (say n) I can always construct a natural number that is larger than i…
If you can write down the natural number n, you can write down n+1. Of course, you can't write down the entire set of natural numbers but that is not a natural number.
On any storage system you will eventually run out of memory, so there will always be a maximum integer that you can write down with what you have, and we can only write down a vanishingly small subset of the natural numbers.
Of course, this isn’t what mean when they talk about “writing down” a number, but I’ve long thought that assuming the existence of natural numbers that you can’t write down is poetically apt.
In some sense, the set of natural numbers is “too big” to be about everyday finite numbers alone and it seems fitting to acknowledge that our usual axioms can’t exclude weirdo large finite numbers that are simply too big to ever reach.
Re: How many real numbers exist? New proof moves closer to an answer
#229Great article. Since it looks like a lot of folks are interested in this article, some extra background. First, what is forcing? The article actually has a great description of ultrapowers (a key part of the construction) but it goes by a little fast, so you might like Tim Chow's "A beginner's guide to forcing" [1] which does a good job not only laying out the mathematical details at a high level, but also really cle…
> but at the same time there is no "right answer"—all of these axioms, after all, are independent of ZFC, and it's "ok" to add any of them. Minor quible: Just because a potential axiom is independent of ZF(C) doesn't make it necessarily "okay" to add. Potential axioms can be unsound, for example if they prove new / untrue Sigma_1 statements. As an example, even in the likely circumstance that ¬Con(ZFC) is independent…
> the resulting system is unsound (in the sense of Tarski) because it asserts the existence of natural numbers that have no "written form" (i.e. the existance of natural numbers that are larger than any term you can write to denote a natural number).
Isn't this a straightforward implication of nonstandard analysis?
Re: How many real numbers exist? New proof moves closer to an answer
#230Earlier quoted context omitted.
Mostly because it implies that some Turing machines halt that actually do not halt. That is unless you are willing to accept that a Turing machine can halt in some number of steps that is beyond any number that can be written. And I don't mean can't be written in the sense that we don't have enough paper. Just cannot be written in principle at all by our notation for numbers.
But isn’t this what the busy beaver numbers are? Numbers that we cannot write for arbitrary n but they do exist?
Do they exist? I thought there was an independence theorem for the specific values of almost all busy beaver numbers.