The precise location of the boundary between the knowable and the unknowable is itself unknowable. But we 𝑑𝑜 know some details about 𝑤ℎ𝑦 this is true, at least within mathematics. It's being studied rigorously in a branch of theoretical computer science called 'meta-complexity theory'.
For some reason it's hard to show that math problems are hard. In meta-complexity theory, people try to understand why.
For example, most of us believe P ≠ NP: merely being able to 𝑐ℎ𝑒𝑐𝑘 the answer to a problem efficiently doesn't imply you can 𝑠𝑜𝑙𝑣𝑒 it efficiently. It seems obvious. But despite a vast amount of work, nobody has been able to prove it!
And in one of the founding results of meta-complexity theory, Razborov and Rudich showed that if a certain attractive class of strategies for proving P ≠ NP worked, then it would be possible to efficiently crack all codes! None of us think 𝑡ℎ𝑎𝑡'𝑠 possible. So their result shows there's a barrier to knowing P ≠ NP.
I'm simplifying a lot of stuff here. But this is the basic idea: they proved that it's probably hard to prove that a bunch of seemingly hard problems are really hard.
But note the 'probably' here! Nobody has 𝑝𝑟𝑜𝑣𝑒𝑑 we can't efficiently crack all codes. And this too, seems very hard to prove.
So the boundary between the knowable and unknowable is itself shrouded in unknowability. But amazingly, we can prove theorems about it!
@johncarlosbaez what can be a precise enough definition of knowability?
The article seems to take a complexity-theoretic pov. I'd like to make it a little bit broader and less formal. Do I know P(x) iff I can compute P(x)=true or false for x? Often it seems that, in math, some problem seems obscure and hard, then, once you understand the solution it feels quite easy. Then there is that old von Neumann quote: "in math you don't understand things, you get used to them". I'm a bit joking here but maybe here I'm just confusing myself by blurring what it means "to know" something VS "to understand" something.
In category theory, I get that feeling reading Lawvere or thinking about yoneda, another possible perspective on "knowability" seems to exists. You know an object by knowing its relationships (arrows) to other objects. Sometimes it is enough to know an object X just by knowing how it relates just to a small collection of basic "already known" objects. I believe that's what Lawvere refers to "subject", what is already familiar/known, interacting with the "objective", what is to be known, i.e. unknown. From this POV, take the disjoint Union of two categories, say 1+1, for one object the other is "unknowable" in some sense.
I wonder if there is some deep connection between various naive mathematical ways of understanding knowability.
@leemph - my go-to formalization of "knowability" in math (and only in math) is "provability". For example, we'd know P ≠ NP if we could prove it. What I'm hinting at in my post is that P ≠ NP is unprovable. But while Goedel and many subsequent logicians were able to prove many interesting statements are unprovable (starting from various standard axioms), so far people have only been able to show that certain approaches to proving P ≠ NP (so-called "natural proofs") lead to dizzying consequences, like our ability to tell the difference between random numbers and pseudorandom numbers.
It's completely possible that P ≠ NP is unprovable and it's also impossible to prove it's unprovable, and it's also impossible to prove this.
For example, we know that if Goldbach's conjecture is true but unprovable, it's also impossible to prove that it's unprovable. So there are cases where uknowability shrouds itself in unknowability.
So, anyway, this is where my thoughts are on this - not broader concepts of "knowing".
@johncarlosbaez I see, knowability:=provability, I like this choice. I'm not a philosopher, not a mathematician, but this seems problematic and exciting for the same reason.
Let's call a proof of T a finite succession P_n of formal expressions leading from an expression P₀ that is given (assumption) or alredy proved, to an expression P_n=T, such that each P_k is obtained by the previous P_n's using a finite set of deduction rules. A proof becomes a tangible object.
Assume knowable(T):="exists a proof of T" then the problems I see are
1- T is knowable becomes a relative concept: it depends on the assumptions (axioms) and the deduction rules. So everything becomes knowable by assuming the right set of axioms;
2- is T known if we can exhibit a proof of T, in a finite amount of time, or if we can just show that exists at least a proof, even if potentially we can not point to it? Knowable implies known?
3- if we prove T then do we have a proof that it is provable? In wich deductive system that meta-proof should be carried?
In brief, I believe that with knowable something stronger that "there exists a proof" is meant, but I dont know what. Also the fact that proofs are relative to the axioms seems interesting for this interpretation of knowability.
When you say the following, I'm completely lost
<<For example, we know that if Goldbach's conjecture is true but unprovable, it's also impossible to prove that it's unprovable. So there are cases where uknowability shrouds itself in unknowability.>>
If in this phrase "we know" means "it is provable" then my mind stops working. If it is impossible to prove it is unprovable, how can we know it is "true but unprovable"?
@leemph - regarding 1, you're exactly right: in math most of us have accepted that "mathematical knowledge" is relative to a set of axioms and deduction rules. This started with the discovery of non-Euclidean geometry, where "truths" of Euclidean geometry turned out to be consequences of axioms that no longer hold if you switch to a different sort of geometry. Later Goedel showed that any sufficiently powerful consistent finitely axiomatizable theory could never prove or disprove all statements formulated in its own language: there's always some statement P such that we can add either P or not(P) to the axioms and get a new such set of axioms that's still consistent.
In constructivist logic to prove something exists means that you can, at least in principle, exhibit an example. In classical logic there are cases where you can prove something exists but not exhibit an example. So your attitude to this question is closely allied to whether you prefer classical or constructivist logic. Most really smart mathematicians realize that this, too, is another case of the relativity in part 1. I.e., neither constructivism or classical logic is "really true": they are just alternative sets of axioms, and it's worth exploring both.
"If we prove T then do we have a proof that it is provable?" In the logics I know, exhibiting an example of something counts as a proof that it exists. So yes, in both classical and constructivist logic, we can get from a proof of P to a proof that P is provable. Part 2 was about the more problematic converse.
"In which deductive system should that meta-proof be carried out?" There are many choices. This is another instance of the relativity in 1.
@leemph wrote: "<<For example, we know that if Goldbach's conjecture is true but unprovable, it's also impossible to prove that it's unprovable. So there are cases where unknowability shrouds itself in unknowability.>>"
Sorry, this was a stupid sentence, and you were right to be confused. Here's what I was trying to say:
"For example, if Goldbach's conjecture is true but unprovable, it's also impossible to prove that it's unprovable. So there are cases where unknowability shrouds itself in unknowability."
And normally I avoid using the word "true" in this context, since it doesn't really mean much to say a mathematical statement is "true" except as a shorthand for it being provable. If I were trying to be precise, I would have said this:
"For example, if neither Goldbach's conjecture nor its negation is provable, it's also impossible to prove that either of those is unprovable. So there are cases where unknowability shrouds itself in unknowability."
@TruthSandwich - Alas, that doesn't parse because P ≠ NP is a single task, while the terms P and NP make sense only for 𝑓𝑎𝑚𝑖𝑙𝑖𝑒𝑠 of tasks, like multiplying numbers or factoring numbers into primes. There are 𝑙𝑜𝑡𝑠 of numbers, and we say multiplying numbers is in P because the time it takes grows polynomially as the numbers get bigger.
I could go on, but this is what happens when you make a joke to a mathematician.
@johncarlosbaez A side point but I think of "knowable/unknowable" as traditionally asking something a bit different: what can we know about reality. I.e., there I think it's more about the theoretical limits of science; or or science plus logic. Or if you like Bergson or some mystics we might know get past the limits of observation and analysis through "intuition" or "contemplation" - by participating in it directly as part of reality. That mysticisms moves the bar out on knowability in a cute way, but if you quiz a mystic on physics it seems probably to be an unsuccessful path.
The Kantian question is not uninteresting - if all we have is experience there are theoretical limits to what we can know about the fundamental nature of reality (if there is one).
But it is I think a different knowability question completely from what we can know about a field of questions that we have generated through the mathematical frameworks we can devise?
@aadmaa - of course, the question about what we can know about nonmathematical questions is infinitely harder than for mathematical ones. It may also be more important. But having studied it as a youth, I eventually decided it was too intractable to be worth spending more time on. I like working on things where I can make progress.
The question of unknowability for math is by comparison so clear and self-contained that I find it fascinating how even here we sink into deep quicksand of a self-referential sort. But since math is so clear and self-contained, we can prove amazing theorems about this quicksand. For example we can sometimes rigorously 𝑝𝑟𝑜𝑣𝑒 that for certain propositions, if we are unable to prove them, we are also unable to prove that we are unable to prove them. And so on.
The recent rise of meta-complexity theory is showing that such questions are relevant to cryptography, the study of efficient algorithms, etc. That's pretty amazing!
@johncarlosbaez that reminds me of something I read once: the Finch-Church paradox of knownability. "if any truth can be known then it follows that every truth is in fact known." So there will always be unknown truths. https://plato.stanford.edu/entries/fitch-paradox/
@davidsuculum - that's nice; now I want to follow the precise proof of this "paradox" and its assumptions. But beware: in English "any" means both "some" (∃) and "all" (∀). From your description I thought the paradox was claiming
"If some truth can be known then it follows that every truth is in fact known"
which is crazy, but in fact it claims
"If every truth can be known than it follows that every truth is in fact known"
This seems interesting and perhaps reasonable, since I believe not every truth can be known.
@franchesko - the article I linked to mentioned meta-meta-complexity:
.....
Given the truth table of a Boolean function, determine whether it has high or low circuit complexity. They dubbed this the minimum circuit size problem, or MCSP.
[....]
MCSP is a quintessential meta-complexity problem: a computational problem whose subject is not graph theory or another external topic, but complexity theory itself.
Kabanets knew that he and Cai weren’t the first to consider the problem they had dubbed MCSP. Soviet mathematicians had studied a very similar problem beginning in the 1950s, in an early attempt to understand the intrinsic difficulty of different computational problems. Leonid Levin had wrestled with it while developing what would become the theory of NP-completeness in the late 1960s, but he couldn’t prove it NP-complete, and he published his seminal paper without it.
After that, the problem attracted little attention for 30 years, until Kabanets and Cai noted its connection to the natural proofs barrier. Kabanets didn’t expect to settle the question himself — instead he wanted to explore why it had been so hard to prove that this seemingly hard problem about computational hardness was actually hard.
“It is, in a sense, meta-meta-complexity,” said Rahul Santhanam, a complexity theorist at the University of Oxford.
But was it hardness all the way down, or was there at least some way to understand why researchers hadn’t succeeded in proving that MCSP was NP-complete? Kabanets discovered that, yes, there was a reason.
@johncarlosbaez It's worth pointing out that we do know more about these limits if we ignore computational complexity and just focus on computability. We do know that computably semidecidable problems do not coincide with the computably decidable ones (the computability analogue of P = NP).
Add comment