Complexity in Mathematics
Gödel's incompleteness theorem applies to logical languages with countable alphabets. So it does not rule out the possibility that one might be able to prove 'everything' in a language with an uncountable alphabet OR expand the alphabet to account for new variables.
When the proof justifies the theorem, by a growing alphabet, then is it possible to talk about the complexity of the theorem via the growing alphabet of the theorems proof?
In as short as possible, would it be possible to entertain the notion that complexity in non-congruent mathematics is determinable?
I say this because I am assuming that the theorem itself is not ascertainable in complexity due to Gödel's Incompleteness Theorem itself. However, on my other account "Shawn" I have surmised that a growing alphabet can be able to determine the complexity of the proof of the theorem if logic comes next to mathematics.
When the proof justifies the theorem, by a growing alphabet, then is it possible to talk about the complexity of the theorem via the growing alphabet of the theorems proof?
In as short as possible, would it be possible to entertain the notion that complexity in non-congruent mathematics is determinable?
I say this because I am assuming that the theorem itself is not ascertainable in complexity due to Gödel's Incompleteness Theorem itself. However, on my other account "Shawn" I have surmised that a growing alphabet can be able to determine the complexity of the proof of the theorem if logic comes next to mathematics.
Comments (37)
https://math.stackexchange.com/questions/1001948/is-it-possible-to-deduce-godels-first-incompleteness-theorem-from-chaitins-inc
https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/georgia.pdf
Quoting Shawn W
This makes me want to make a joke about my other account @Metaphysician Undercover.
Gotta watch out for those people with dual personalities, they could gang up on you. Or, the two could be completely opposed and go into an endless argument with each other, trying to make a spectacle of themselves.
I think I'm on the same page as what @tim wood quoted, meaning that in terms of complexity of computation can or whether a proof can deduce complexity of mathematical theorems. Not sure if that makes sense. I do specifically think it applies to non-congruent mathematics.
What do you think?
There's a theory of proofs over uncountable alphabets but I don't know anything about it. But as I say, by complexity I think of complexity theory, and there's an incompleteness theorem that can be proved that way. That's literally all I know about it.
What is "congruent mathematics"? Just curious.
Quoting tim wood
Good point. I think of all the theorems I have conjectured and proven, each requiring intricate maneuverings, and wonder. During the past century generalizations and abstractions have been paramount, and certainly when an individual theorem lies within those domains its previously complicated proof may be subsumed by a general result. But this is probably not what the OP means.
One jumps to a higher order logic with supremums (least upper bounds) early in an undergraduate curriculum.
Quoting Shawn W
? Maybe unscramble this. :chin:
Geometry, mainly.
Quoting jgill
I think it is better understood in number theory for example. Is every theorem able to provide for a proof that is least or more complex, and what this would itself amount to? I see that there's difficulty in understanding this because mathematicians aren't accustomed to treating logic as much as it used to to be about logicizing it.
I'm not qualified to attempt an answer to your question. But, I'm currently reading a book by Complexity theorist, James Glattfelder , Information - Consciousness - Reality : How a New Understanding of the Universe Can Help Answer Age-Old Questions of Existence. Some of his chapters get into mathematical technicalities, and uses arcane vocabulary & symbols. But he also gives plain language layman summaries of the mathematical reasoning. Here are few of the topics he covers that are also involved in your question : Simplicity within Complexity ; Goedel's Incompleteness of mathematics ; Analytical vs Algorithmic approaches to nature , and so forth.
Perhaps more pertinent to your topic though, is an article in the Dec2020-Jan2021 issue of Philosophy Now magazine. The article, by Luc deBrabandere, is entitled Homo Informaticus. He traces the history of "the dream of bringing mathematics and logic together" He refers to Leibniz, whose great dream was to "bring together mathematics and logic". He notes the contributions of various mathematicians, scientists, and philosophers (e.g. Leibniz, Kant, Boole, Russell, Chaitin & Turing) who first tried to equate Logic with Math, and then, after Goedel rained on Russell's dream of unification, they have been working on ways around Goedel's roadblock. He concludes by asserting that, even the promise of Big Data, combined with powerful computers, to make old-fashioned mathematics obsolete, with run into the same incompleteness barrier.
:smile:
The word "congruence" has at least two meanings in mathematics, but I've never come across a sub-discipline called "congruent mathematics".
Quoting Shawn
Do theorems "provide" for proofs? Especially ones that are "least complex" or "more complex"(than what?). And this is "logicizing" logic? :roll:
I seem to have run into issues with describing the part about complexity due to the fact that there's no (extra)-systematic way of formalizing mathematics apart from discerning some form of induction rather than say induction on the part of not logic but rather intuitive reasoning about how one should go about designing a proof for a theorem. What I do try and state, rather poorly is that there's inherent issues with trying to state something of the sort as to whether one can determine the complexity (if it pertains at all in any systematic manner) towards a proof of a theorem. It might be easier to think of this as if the incompleteness theorem were to assert that we just expand the alphabet of a theorems proof until it satisfies some least complexity if at all ever can be estimated.
My attempts seem to be closer to what Hilbert may have been trying to do in his program.
Hope that made sense.
Note: I make use of some of the sharpenings of certain notions and specifics that came after Godel's original paper.
(1) Godel-Rosser pertains to systems that are recursively axiomatized. A recursively axiomatized system allows an algorithm for checking whether a purported proof is indeed a proof in the system. Systems with languages having uncountably many symbols are not generally recursively axiomatized. That is why uncountable languages are not generally entertained for the purpose of the theorem.
(2) It is not desired to have a system that proves "everything", since then it would prove contradictions. And the main concern with Godel-Rosser is with theories that prove only arithmetic truths, not "everything".
(3) The rest of what the poster writes is not recognizable to me as sensical commentary on mathematical logic.
(1) By 'alphabet' in this context we mean the set of symbols of the formal language. The concern is not with the number of alphabets, but rather with the cardinality of the set of symbols. This is very relevant to mathematical logic and Godel-Rosser specifically.
(2) it appears, as in other threads, that this poster is not familiar with the actual subject matter of the discussion. It is a continual curiosity when a person insists on posting opinions on a technical subject of which he or she has not read even the first page in an introductory textbook.
Stop picking on @Metaphysician Undercover!
Might I suggest that this question is about syntax and not math?
simplicity vs. complexity
Interesting approach. What kind of general syntax applies to proof telling?
In order to meaningfully discuss incompleteness, you need to read a textbook in mathematical logic. Without such background, your notions and terminology are not comprehensible.
What is "proof telling"? Proof description? An actual proof written out? Compared with "story telling"?
A traditional proof (pencil on paper) may be complicated, but I take it "complexity" refers to computer programs that can ascertain correctness of proof for certain kinds of theorems.
Explain this difference. My high school math knowledge informs me that these are the same thing.
Quoting GrandMinnow
A thousand apologies. :smile:
As far as I know, Godel's theorems aren't a function of, ergo not liable to be disproved, assuming that is your objective, by any consideration of the cardinality of the symbol set employed in proving them.
To be fair though, if I'm not mistaken about the general idea behind your, what shall I call it, hypothesis, I'm very eager to see what it leads to.
As for my personal views on the matter, you might want to consider the matter of polysemy, something I'm sure you're familiar with. Given that one symbol maybe given two or more semantic identities, your investigation, if I may call it that, fails right from the start for the simple reason that the cardinality of the set of symbols is completely arbitrary and that implies you would draw the wrong conclusions, see patterns that may not really exist.
Of course, what I know about logic and computer languages if that's relevant at all indicates that they're constructed in ways that make it a point to avoid polysemous words. It's only after taking this into account that we can hope to find some kind of correlation between Godel's theorems and alphabets.
I hope I didn't bore you.
There are myriad ways to spout nonsense, fallacy, and misinformation such as yours, but fewer distinctive ways to state accuracies. So I am at a disadvantage relative to you, as your errant posts may have greater variety while mine eventually become repetitious. But I will respond yet again, while knowing that there is a good chance that eventually I'll give up trying to convince you that you are not prepared to discuss mathematical logic without having at least read an introductory textbook.
You are confusing the symbol sets of the systems that the incompleteness theorem are about with the symbol set of any system in which the incompleteness theorem itself is proven. The former is what is in question here. (However both are countable anyway.)
The Godel-Rosser incompleteness theorem is that there is not a formal, consistent, "arithmetically adequate" system that yields a negation-complete theory. Systems with uncountable symbol sets are not generally considered to be formal. I explained why in a previous post. Indeed, moreover, the proof of the incompleteness theorem relies on assigning a unique natural number to each symbol, thus the symbol set must be countable.
You do a disservice by posting, in many threads, widely incorrect nonsense while you are not familiar with the basics of the subject that are found in introductory textbooks. GET A TEXTBOOK IN MATHEMATICAL LOGIC.
https://www.physicsforums.com/threads/is-complexity-in-mathematics-determinate.1000094/
No. No more so than complexity in human thought is determinable.
I was expecting something like:
Mathematics is deterministic, and yet, this situation arises.
Maybe some stuff in maths can get organized better with this in thought?
Sure, but this is quite a conundrum towards the notion that everything in mathematics should or is determinate.
The question of whether mathematics is created or discovered has been around for a very long time. This, perhaps, is not precisely what you are asking, but close. An act of imagination may lead to interesting results that are determinate, but the original thought might never arise. Then all that follows will not exist. An original thought is required to set the train in motion. Is that thought determinate?
Let's suppose a math guy has that original thought, and a process unfolds in a determinate manner, then someone else has an original idea that influences the direction of that process. The second guy is part of the process, but his thought may not be determinate.
Most mathematicians pay little to no attention to issues like this. I never did. :cool:
Or maybe the act of inquiry and arising insights to sound more pragmatist?
A lot of people are baffled by this topic for some reason, where I see this in a sense very apparent in mathematics nowadays to talk about the sort of lack of categorization, that can even at all begin or take place!
Category Theory
What kind of truth about this whole issue do you think this has in common with category theory or perhaps this is sort of some kind of new logic at play? I mean, is there anything novel about this line of reasoning to the subject matter of mathematics?
Well, my knowledge doesn't seem to be a deterrent for some kind of discussion. All that I have concluded now is that there's no determined method to quantifying complexity in mathematics.
https://encyclopediaofmath.org/wiki/Complexity_theory
Be it Gödel or Heisenberg, infinite variables can not be overcome by infinite description,
there must be a corner around which the pursuit changes velocity.
Theory of Nothingness
''Rather the starting point, the un-caused Cause, is Possibility which is both Something and Nothing and the basis of Probability.'' Marvin Glover
Good question. I think there is confusion regarding complex in a technical sense and complicated in a more general sense. I know of no "scale" describing levels of complication in a mathematical proof, although when one conjectures a proof path it may be apparent that low or high levels of complication might ensue. And maybe there are practitioners who speculate "Why this looks to be about an eight on the scale of complexity!"
Again, a discussion of mathematics that mathematicians pay little attention to. But fun for amateur philosophers. :smile:
"Non-elementary" usually means the argument involves more advanced concepts and results, and may actually be fairly straightforward and uncomplicated - or not. :cool: