Chaitin has used complexity theory to prove a version of Gödel's incompleteness theorem. But I wonder if you're using complexity in a different way. Here are a couple of links.

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

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. — 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.

An unusually readable approach here:
https://johncarlosbaez.wordpress.com/2012/10/19/insanely-long-proofs/

Godel wrote a two-page paper (1936) titled, "On the Length of Proofs," which unfortunately I do not understand. However, it contains this sentence. "The transition to the logic of the next higher type not only results in certain previously unprovable propositions becoming provable, but also in it becoming possible to shorten extraordinarily infinitely many of the proofs already available."

Just a thought: are there really that many proofs already available? Not at the library, certainly.

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?

What do you think? — Shawn W

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.

I do specifically think it applies to non-congruent mathematics — Shawn W

What is "congruent mathematics"? Just curious.

Just a thought: are there really that many proofs already available? Not at the library, certainly. — 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.

In as short as possible, would it be possible to entertain the notion that complexity in non-congruent mathematics is determinable? — Shawn W

? Maybe unscramble this. :chin:

What is "congruent mathematics"? Just curious. — jgill

Geometry, mainly.

Maybe unscramble this — 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.

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. — Shawn W

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:

I don't see a/the connection between alphabets and logic. For instance, there's nothing logical about "h" or "o". How are we going to proceed from there to an argument? Plus, what's the number of alphabets got to do with logic? There are many languages around, all with different number of alphabets, but Godel's theorems don't vary between them.

What is "congruent mathematics"? Just curious. — jgill

Geometry, mainly. — Shawn

The word "congruence" has at least two meanings in mathematics, but I've never come across a sub-discipline called "congruent mathematics".

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. — Shawn

Do theorems "provide" for proofs? Especially ones that are "least complex" or "more complex"(than what?). And this is "logicizing" logic? :roll:

Do theorems "provide" for proofs? Especially ones that are "least complex" or "more complex"(than what?). And this is "logicizing" logic? — jgill

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.

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. — GrandMinnow

Stop picking on @Metaphysician Undercover!

In as short as possible, would it be possible to entertain the notion that complexity in non-congruent — Shawn W

Might I suggest that this question is about syntax and not math?
simplicity vs. complexity

Might I suggest that this question is about syntax and not math?
simplicity vs. complexity — Rxspence

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 kind of general syntax applies to proof telling? — Shawn

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.

number of alphabets, but rather with the cardinality of the set of symbols — GrandMinnow

Explain this difference. My high school math knowledge informs me that these are the same thing.

it appears, as in other threads, that this poster is not familiar with the actual subject matter of the discussion. — 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.

Sorry to have wasted your time then. I've bitten off more than I can chew. G'day.

Posted on PhysicsForum also:

https://www.physicsforums.com/threads/is-complexity-in-mathematics-determinate.1000094/

From the link above: "So, I don't think anyone has addressed the question posed in the title; but, is complexity in mathematics in your opinion determinate?"

No. No more so than complexity in human thought is determinable.

From the link above: "So, I don't think anyone has addressed the question posed in the title; but, is complexity in mathematics in your opinion determinate?"

No. No more so than complexity in human thought is determinable. — jgill

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?

Human thought and ingenuity is paramount in creative mathematics. There is no way to determine this in advance. Lots of "aha!" moments. :cool:

Sure, but this is quite a conundrum towards the notion that everything in mathematics should or is determinate.

You do a disservice by posting, in many threads, widely incorrect nonsense while you are not familiar with the basics of the subject — GrandMinnow

Probably the nicest, most civil, and also the best way to express the thought.

Sure, but this is quite a conundrum towards the notion that everything in mathematics should or is determinate. — Shawn

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!

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! — Shawn

Category Theory