Learnability can be undecidable
January 23, 2019 8:56 PM Subscribe
The Nature of Infinity — and Beyond - "An introduction to Georg Cantor and his transfinite paradise."
also btw...
Mathematicians Discovered a Computer Problem that No One Can Ever Solve - "It turns out that EMX can solve a problem only if the continuum hypothesis is true. But if it's not true, EMX can't. That means that the question, 'Can EMX learn to solve this problem?' has an answer as unknowable as the continuum hypothesis itself."[1,2,3]
also btw...
Mathematicians Discovered a Computer Problem that No One Can Ever Solve - "It turns out that EMX can solve a problem only if the continuum hypothesis is true. But if it's not true, EMX can't. That means that the question, 'Can EMX learn to solve this problem?' has an answer as unknowable as the continuum hypothesis itself."[1,2,3]
see also: david foster wallace’s “everything and more”
posted by bruceo at 11:20 PM on January 23, 2019 [3 favorites]
posted by bruceo at 11:20 PM on January 23, 2019 [3 favorites]
In desperation, Cantor wrote a very affecting letter to Bertrand Russell asking to be appointed Librarian at some institution where he thought Russell was influential, proposing to finally demonstrate who actually wrote Shakespeare's plays should he be chosen for the position.
I can't help wanting to know who he thought it was, and how he reached his conclusions.
posted by jamjam at 11:33 PM on January 23, 2019 [3 favorites]
I can't help wanting to know who he thought it was, and how he reached his conclusions.
posted by jamjam at 11:33 PM on January 23, 2019 [3 favorites]
Shakespeare wrote all of his own plays, but he got the material from everywhere, more than anywhere. Everyone 'knows' that, but it remains, as yet, unprovable. Right? Either Shakespeare can't write, or can. You decide.
posted by RoseyD at 11:44 PM on January 23, 2019
posted by RoseyD at 11:44 PM on January 23, 2019
Oh, I now remember writing a short paper on the diagonal argument many years ago. I'll have to read this and see if I can revive any of those decrepit neurons.
posted by pracowity at 1:46 AM on January 24, 2019
posted by pracowity at 1:46 AM on January 24, 2019
A favorite topic for cranks. There is an entire category for this at the blog "Good Math Bad Math". One case went all the way to a Court of Appeals.
posted by thelonius at 2:41 AM on January 24, 2019 [7 favorites]
posted by thelonius at 2:41 AM on January 24, 2019 [7 favorites]
A favorite topic for cranks.
See also: this subpage of the Wikipedia edit page for Cantor's diagonal argument.
posted by Panthalassa at 4:16 AM on January 24, 2019 [2 favorites]
See also: this subpage of the Wikipedia edit page for Cantor's diagonal argument.
posted by Panthalassa at 4:16 AM on January 24, 2019 [2 favorites]
I've cranked my share of that blindingly beautiful argument in the course of finally coming to grips with it, and would like to thank again all those people who had the patience to put up with all the misunderstandings I showed them along the way.
posted by flabdablet at 4:36 AM on January 24, 2019 [3 favorites]
posted by flabdablet at 4:36 AM on January 24, 2019 [3 favorites]
Jørgen Veisdal:
posted by flabdablet at 5:11 AM on January 24, 2019 [4 favorites]
It would not be until 1940 that the Austro-Hungarian logician Kurt Gödel confirmed the consistency of the continuum hypothesis by showing that it could not be disproved from the other axioms of set theory. Twenty-three years later, American mathematician Paul Cohen established its independence by showing that the continuum hypothesis could not be proved from the other axioms of set theory. They in other words showed that the statement c = ℵ₁ is independent of the Zermelo–Fraenkel axiom system generally accepted as the most common foundation of mathematics. The consistency and independence of Cantor’s conjecture meant that it was possible to build valid models of set theory that satisfied the continuum hypothesis and other models that did not.This is the same kind of thing that happened to Euclid's parallel postulate, resulting in the invention of elliptic and hyperbolic geometries.
posted by flabdablet at 5:11 AM on January 24, 2019 [4 favorites]
there are clearly more real numbers than there are integers.
In a context where he is explaining what an integer and real number are, I suspect it isn't really "clear" to the author.
posted by Obscure Reference at 5:33 AM on January 24, 2019 [1 favorite]
In a context where he is explaining what an integer and real number are, I suspect it isn't really "clear" to the author.
posted by Obscure Reference at 5:33 AM on January 24, 2019 [1 favorite]
You even sometimes still see, in the wild, theologically motivated rejection of Cantor. There is only one Infinite, which is God, the Absolute. So Cantor must be not only wrong, but heretical.
posted by thelonius at 6:37 AM on January 24, 2019 [1 favorite]
posted by thelonius at 6:37 AM on January 24, 2019 [1 favorite]
Cantor was also a theological kind of guy.
posted by Obscure Reference at 7:27 AM on January 24, 2019 [2 favorites]
posted by Obscure Reference at 7:27 AM on January 24, 2019 [2 favorites]
proposing to finally demonstrate who actually wrote Shakespeare's plays... I can't help wanting to know who he thought it was
A transfinite number of monkeys?
posted by Segundus at 8:40 AM on January 24, 2019 [11 favorites]
A transfinite number of monkeys?
posted by Segundus at 8:40 AM on January 24, 2019 [11 favorites]
Man this makes me want to be a Cantor crank. Sort of.
I totally get the insistence by the Good Math blogger that what "counts" is the formalism, and that within the formalism of set theory the diagonalization proof totally works.
At the same time, you can never actually demonstrate that the formalism really matches up with the world. (though, if it tells you that 2+2=5 but the same experiment with apples says 2+2=4, you can know it doesn't).
So, you know, let's come up with a formalism where we can do most of the math we'd like to do, but where the diagonalization arguent doesn't work. For instance, if we do restrict ourselves to "computable numbers" or the "constructive reals", then I think diagonalization stops working (I'd be happy to hear whether I'm right or wrong). But we don't seem to be required to give up "useful" things like using computer models to find out whether skyscrapers will stand and planes will fly, or even do much to impoverish the inner lives of mathematicians if we just turn our back on the set of real numbers.
posted by the antecedent of that pronoun at 3:14 PM on January 24, 2019 [2 favorites]
I totally get the insistence by the Good Math blogger that what "counts" is the formalism, and that within the formalism of set theory the diagonalization proof totally works.
At the same time, you can never actually demonstrate that the formalism really matches up with the world. (though, if it tells you that 2+2=5 but the same experiment with apples says 2+2=4, you can know it doesn't).
So, you know, let's come up with a formalism where we can do most of the math we'd like to do, but where the diagonalization arguent doesn't work. For instance, if we do restrict ourselves to "computable numbers" or the "constructive reals", then I think diagonalization stops working (I'd be happy to hear whether I'm right or wrong). But we don't seem to be required to give up "useful" things like using computer models to find out whether skyscrapers will stand and planes will fly, or even do much to impoverish the inner lives of mathematicians if we just turn our back on the set of real numbers.
posted by the antecedent of that pronoun at 3:14 PM on January 24, 2019 [2 favorites]
I've cranked my share of that blindingly beautiful argument in the course of finally coming to grips with it
I have a crank bone or two in my body. When I was shown the diagonal proof in class I also wondered about the natural numbers. Fortunately I had a prof right there to ask. He pointed out the infinite series of digits along the diagonal wouldn't converge, kinda isn't a natural number. That settled that.
The axiom of choice, though, still makes me squint and shake my head.
posted by fleacircus at 5:20 PM on January 24, 2019
I have a crank bone or two in my body. When I was shown the diagonal proof in class I also wondered about the natural numbers. Fortunately I had a prof right there to ask. He pointed out the infinite series of digits along the diagonal wouldn't converge, kinda isn't a natural number. That settled that.
The axiom of choice, though, still makes me squint and shake my head.
posted by fleacircus at 5:20 PM on January 24, 2019
john baez on "indescribable cardinals" :P
The concept is infinity is HUGELY fun.
The concept is infinity is HUGELY fun.
John von Neumann described the so-called "universe" - the collection of all sets - as the union of a list of increasingly large collections of sets V(0), V(1), V(2), etcetera. But "etcetera" must go on for a REALLY long time!posted by kliuless at 6:59 PM on January 24, 2019 [1 favorite]
[...]
We can't prove indescribable cardinals exist using the standard axioms of set theory (the ZFC axioms) - but that's already true of smaller cardinals like "inaccessible" ones.
In fact, indescribable cardinals are near the *bottom* of the ladder of large cardinals!
At the same time, you can never actually demonstrate that the formalism really matches up with the world. (though, if it tells you that 2+2=5 but the same experiment with apples says 2+2=4, you can know it doesn't).
There's a fundamental difference between counting things and measuring things that causes a lot of unnecessary confusion. It even shows up in contexts as simple as apples.
Consider the case of a person with type 1 diabetes, who needs to know how much sugar there is in anything they eat so that they can adjust the insulin delivery accordingly on their infusion pump.
For reasons of practicality, these calculations are often performed in units of carbohydrate exchanges, and a typical apple is counted as 1 exchange.
But apple sizes and their actual sugar content are a bit variable. You can generally rely on two apples being worth near enough to two exchanges, but if you have another two, it could easily happen that the number of exchanges you really should have entered into the pump was five.
So, you know, let's come up with a formalism where we can do most of the math we'd like to do, but where the diagonalization argument doesn't work.
I can get behind this as an interesting intellectual exercise in its own right, but as a reaction to disquiet about the "correctness" of the diagonalization argument as applied to a "real world" I think it misses an important point.
For instance, if we do restrict ourselves to "computable numbers" or the "constructive reals", then I think diagonalization stops working (I'd be happy to hear whether I'm right or wrong). But we don't seem to be required to give up "useful" things like using computer models to find out whether skyscrapers will stand and planes will fly, or even do much to impoverish the inner lives of mathematicians if we just turn our back on the set of real numbers.
The real numbers are, essentially, an idealization and formalization of the kinds of numbers that result from measurement as opposed to counting. My gut feel about replacing that formalism with something based solidly in computability is that by forcing our idealization of measurement to be derivable from our idealization of enumeration we'd run the risk of forcing ourselves to work in a way that feels more like programming in PHP than doing mathematics. We'd be putting restrictions on the way we work that arise more from ideology than anything else, and it seems to me that this way lies believing our own bullshit and descent into madness.
The entire point of mathematics, it seems to me, is the invention of formalisms - ways to express ideas unambiguously - followed by exploration of the consequences of the ideas so expressed. Constraining mathematics in ways that mean one is only "allowed" to consider ideas with a-priori connections to some pre-existing idea of a "real world" is to reduce mathematics to physics. It's the same instinct that leads administrations to de-fund pure science and insist that all scientific investigation must have some clear "real-world" application before being considered worthwhile, and it ignores centuries of history that demonstrate the power of retraining intuition in atypical ways.
If diagonalization offends intuition, it seems to me that the best way to respond to that is to train the intuition on more stuff, not declare certain kinds of stuff a-priori unsound.
Computer models are kind of tangential to this discussion because most of them don't use real numbers anyway; they use floating-point numbers which, since they need to be representable in a fixed number of bits, are elements of a set with finite cardinality.
posted by flabdablet at 7:10 PM on January 24, 2019
There's a fundamental difference between counting things and measuring things that causes a lot of unnecessary confusion. It even shows up in contexts as simple as apples.
Consider the case of a person with type 1 diabetes, who needs to know how much sugar there is in anything they eat so that they can adjust the insulin delivery accordingly on their infusion pump.
For reasons of practicality, these calculations are often performed in units of carbohydrate exchanges, and a typical apple is counted as 1 exchange.
But apple sizes and their actual sugar content are a bit variable. You can generally rely on two apples being worth near enough to two exchanges, but if you have another two, it could easily happen that the number of exchanges you really should have entered into the pump was five.
So, you know, let's come up with a formalism where we can do most of the math we'd like to do, but where the diagonalization argument doesn't work.
I can get behind this as an interesting intellectual exercise in its own right, but as a reaction to disquiet about the "correctness" of the diagonalization argument as applied to a "real world" I think it misses an important point.
For instance, if we do restrict ourselves to "computable numbers" or the "constructive reals", then I think diagonalization stops working (I'd be happy to hear whether I'm right or wrong). But we don't seem to be required to give up "useful" things like using computer models to find out whether skyscrapers will stand and planes will fly, or even do much to impoverish the inner lives of mathematicians if we just turn our back on the set of real numbers.
The real numbers are, essentially, an idealization and formalization of the kinds of numbers that result from measurement as opposed to counting. My gut feel about replacing that formalism with something based solidly in computability is that by forcing our idealization of measurement to be derivable from our idealization of enumeration we'd run the risk of forcing ourselves to work in a way that feels more like programming in PHP than doing mathematics. We'd be putting restrictions on the way we work that arise more from ideology than anything else, and it seems to me that this way lies believing our own bullshit and descent into madness.
The entire point of mathematics, it seems to me, is the invention of formalisms - ways to express ideas unambiguously - followed by exploration of the consequences of the ideas so expressed. Constraining mathematics in ways that mean one is only "allowed" to consider ideas with a-priori connections to some pre-existing idea of a "real world" is to reduce mathematics to physics. It's the same instinct that leads administrations to de-fund pure science and insist that all scientific investigation must have some clear "real-world" application before being considered worthwhile, and it ignores centuries of history that demonstrate the power of retraining intuition in atypical ways.
If diagonalization offends intuition, it seems to me that the best way to respond to that is to train the intuition on more stuff, not declare certain kinds of stuff a-priori unsound.
Computer models are kind of tangential to this discussion because most of them don't use real numbers anyway; they use floating-point numbers which, since they need to be representable in a fixed number of bits, are elements of a set with finite cardinality.
posted by flabdablet at 7:10 PM on January 24, 2019
Julius König via Jørgen Veisdal:
posted by flabdablet at 7:34 PM on January 24, 2019
Proof that |ℝ²| = |ℝ|I'm sure I'm missing something here. This is a gorgeous proof, but can somebody with more mathematics chops help me understand the point of the grouping-to-nonzero-digit part? Are there edge cases that would not be dealt with equally well by the simpler process of constructing z from the first digit of the expansion of x, first of y, second of x, second of y, third of x, third of y... without grouping?
It suffices to prove that the set of all pairs (x,y), 0 < x,y < 1 can be mapped bijectively onto (0,1]. Consider the pair (x,y) and write x,y in their unique non-terminating decimal expansion as in the following example:
x = 0.3 01 2 007 08 ...
y = 0.009 2 05 1 0008 ...
Note that the digits of x and y have been separated into groups by always going to the next nonzero digit, inclusive. Now we associate to (x,y) the number z ∈ (0,1] by writing down the first x-group, after that the first y-group, then the second x-group, and so on. Thus, in our example, we obtain:
z = 0.3 009 01 2 2 05 007 1 08 0008 ...
Since neither x nor y exhibits only zeroes from a certain point on, we find that the expression for z is again a non-terminating decimal expansion. Conversely, from the expansion of z we can immediately read off the preimage (x,y) and the map is bijective.
posted by flabdablet at 7:34 PM on January 24, 2019
I don't understand this method either. Doesn't ℝ include 0.5 (which does consist of "only zeroes from a certain point on") as well as values like 1/3 = 0.3333.... (which never has any zeroes)? I don't see how you apply this method to x=1/2 and y=1/3.
Meanwhile, this reddit thread discusses where the "take alternating digits" plan runs into trouble, basically with values like .24999999... (but it's reddit so I dunno if the math is good)
posted by the antecedent of that pronoun at 8:11 PM on January 24, 2019
Meanwhile, this reddit thread discusses where the "take alternating digits" plan runs into trouble, basically with values like .24999999... (but it's reddit so I dunno if the math is good)
posted by the antecedent of that pronoun at 8:11 PM on January 24, 2019
The proof specifies the "unique non-terminating decimal expansion", so you would use 1/2 = 0.4999999... In that case, thus never running out of nonzero digits.
flabdablet: I think the grouping approach (in combination with the non-terminating decimal expansion) helps ensure that the mapping is a clean bijection.
posted by NMcCoy at 8:34 PM on January 24, 2019 [1 favorite]
flabdablet: I think the grouping approach (in combination with the non-terminating decimal expansion) helps ensure that the mapping is a clean bijection.
posted by NMcCoy at 8:34 PM on January 24, 2019 [1 favorite]
(So x=1/2, y=1/3 maps uniquely onto 0.43939393...)
posted by NMcCoy at 8:36 PM on January 24, 2019 [1 favorite]
posted by NMcCoy at 8:36 PM on January 24, 2019 [1 favorite]
If you just take every other digit then:
.2220202020... goes to (0.222..., 0,2), but
.2129292929... also goes to (0.222..., 0.2)
posted by fleacircus at 10:41 PM on January 24, 2019 [2 favorites]
.2220202020... goes to (0.222..., 0,2), but
.2129292929... also goes to (0.222..., 0.2)
posted by fleacircus at 10:41 PM on January 24, 2019 [2 favorites]
Thank you.
posted by flabdablet at 2:48 AM on January 25, 2019
posted by flabdablet at 2:48 AM on January 25, 2019
The axiom of choice, though, still makes me squint and shake my head.
I have never seen why people find it suspicious. It says that, if I have a set of sets, I can make a new set by picking one thing from each, right? That seems OK to me.
posted by thelonius at 3:00 AM on January 25, 2019
I have never seen why people find it suspicious. It says that, if I have a set of sets, I can make a new set by picking one thing from each, right? That seems OK to me.
posted by thelonius at 3:00 AM on January 25, 2019
Rather than being "suspicious", I think the Axiom of Choice is something that many find intuitive (and is uncontroversially true when dealing with finite things), but which turns out to be independent of set theory.
posted by the antecedent of that pronoun at 7:19 AM on January 25, 2019
posted by the antecedent of that pronoun at 7:19 AM on January 25, 2019
I was scratching my head over the encoding issue last night but finally gave up and Googled it up. A website answer showed that Cantor's original proof used the more obvious interleaving method, which instead of proving the bijection "A <> B", first showed a mapping tgat proved "|A| <>= |B|" and finally a special theorem that given both then |A| = |B|. So that was interesting to know.
posted by polymodus at 12:17 PM on January 25, 2019
posted by polymodus at 12:17 PM on January 25, 2019
The Menger sponge, which is to our leader dear, is a 3-D generalization of Cantor's middle thirds set, which I didn't even realize until cortex described the Menger sponge as
posted by jamjam at 6:18 PM on January 26, 2019
this thing you can you do with a cube where you core out the middle third on all three axes, and then with the smaller cubes that are left over you core out the middle third on all three axes, and then...it was sort of my Trump moment, like when he realized after years, that there was actually a connection between The Apprentice, his own long-running TV show, and the whole concept of apprenticeship.
posted by jamjam at 6:18 PM on January 26, 2019
« Older Stoker-King model vs Rice model vs... | Yokokanno Watanabe a Space Cowboy? Newer »
This thread has been archived and is closed to new comments
posted by polymodus at 11:01 PM on January 23, 2019 [1 favorite]