It sounds as though you yourself hold some rather specific and rigid beliefs that likewise are not entirely objective in their genesis. — Pantagruel

Well, yeah, I rigidly believe that we should not give powers to people that only Allah should have, and if Allah does even not exist, then so much the better.

Well, yeah, I rigidly believe that we should not give powers to people that only Allah should have, and if Allah does even not exist, then so much the better. — Tarskian

Thanks for clarifying that.

That may very well be in violation of Carnap's diagonal lemma:

"For each property of logic sentences, there exists a true sentence that does not have it, or a false sentence that does."

But then again, it still needs to be a property of logic sentences. For example, a property of natural numbers can apply to all natural numbers. — Tarskian

If you refer to "an universal statement that ought to apply to everything", I would agree (assuming I understood your point).

Provability, if I have understood it correctly, means that a truth of a statement/conjecture can be derived from some axiomatic system or logical rules.

With diagonalization, we get only an indirect proof. Here the proof lies on a contradiction that if the statement/conjecture would be false, then we would have a contradiction. Yet here we lose a lot from the direct proof as there's no means to grasp similarly information about statement/conjecture as in the direct proof. That's why the "true, but unprovable" statements have been such a mystery, because we want to have more information about them as we have a direct proof. And of course, people haven't been interested to find "true, but unprovable" statements. Hopefully it's changing now.

So one hypothesis would be this:

Is diagonalization a way to find mathematical statements that cannot be proven by a direct proof, but only can shown to be true by reductio ad absurdum?

And the next, even more outrageous hypothesis:

Is then this also a limit that we can compute and give a direct proof?

Let's just think what our current definition is on what is computable: the Church-Turing thesis. It states that what is computable is what a Turing Machine can compute. What the Turing Machine cannot compute is found exactly by using diagonalization (or negative self-reference) that we are talking in the first place.

But not only is this a informal definition, it is also only a thesis. Meaning literally something that we want to prove. And here we find again an issue where we want mathematics to be something else that it is, if we want to make a direct proof about it, ie a theorem of the Church-Turing thesis. This isn't possible in my view because we are talking about the limits of what is computable or directly provable and what is not.

So what are we missing here?

Basically a proof that defines what is both computable and directly provable in mathematics and what isn't. Because this proof also states what isn't computable and not directly provable, to be consistent with itself, this part itself cannot directly provable, but only be an indirect proof.

My five cents on the issue: The diagonalization itself here holds the key. It could solve a lot of the confusion that mathematics has now.

Love to hear your comment @Tarskian and others too. And if I made a mistake somewhere, please tell, I'm not an mathematician/logician, so I an ad hominem attack on my credibility.

Your statement is a bit different from mine.

if everything were perfectly ordered, nothing would change. Existence requires both. — Wayfarer

This invigors a deep curiosity in me. Something that does not change, does not exist? How so?

The set of finite-length strings over an at most countably infinite alphabet is countable. There are countably many strings of length 1, countably many of length 2, dot dot dot, therefore countably many finite strings.

If you allow infinite strings, of course, you can have uncountably many strings. That's the difference between positive integers, which have finitely many digits; and real numbers, which have infinitely many. That's why the positive integers are countable and the real numbers uncountable. It's the infinitely long strings that make the difference. But natural language doesn't allow infinitely long strings. Every word or sentence is finite, so there can only be countably many of them.

This was my first thought. Natural languages would seem to need to be computable, which would entail countably infinite.

Well, instead of being able to predict just 0.1% of the facts in the physical universe, this would improve to something like 0.3%; not much more. — Tarskian

Again, hyperbole. I can assure you if we were able to predict how everything in the universe worked, we would solve all of quantum mechanics for starters. That's pretty huge. We would also master quarks and gluons. That's not insignificant.

Scientism is widespread as an ideology in the modern world. Any true understanding of the nature of mathematical truth deals a devastating blow to people who subscribe to it. This is exactly why I like this subject so much. — Tarskian

Right, people of all stripes can fall into the intellectual trap of, "Nothing is true!" and think that gives them an insight that others don't see. After all, if nothing is true, no more thinking right? Except its really just an illusion of intelligence. Want to really impress? Try coming up with ways to make sense of the world despite the 'chaos'.

I say this not to insult, but to kick you in the pants a bit because I see too many people fall into this trap that stunts their further growth. No, nothing you have discovered here has shaken the foundations of math or science. Knowing some limitations in how it comes about or what it can do, does not invalidate what it can do and is useful for.

In 1931, Gödel's incompleteness theorems dealt a major blow to positivism and scientism, but it was just the beginning. It is only going to keep getting worse. As Yanovsky writes in his paper:

Gödel’s famous incompleteness theorem showed us that there is a statement in basic arithmetic
that is true but can never be proven with basic arithmetic. That is just the beginning of the story. — Tarskian

You can't prove arithmetic from arithmetic because we created it. The concept of "One" is from our ability to create discrete experiences in the world. For example, look at your keyboard. Now your keys. Now a portion of the key. Those are all your ability to create the concept of "one". "Two" is the concept of one and one grouped together. And thus the logic that continues from there is math. Again, just because math can't prove math, doesn't mean that its not a viable and useful tool that results in amazing leaps in technology and understanding of the universe.

In my opinion, scientism needs to get attacked and destroyed because its narrative is not just arrogant but fundamentally evil — Tarskian

That's new! Why is it arrogant and evil?

It is a false pagan belief that misleads its followers to accept untested experimental vaccine shots from the lying and scamming representatives of the pharmaceutical mafia; and that is just one of the many examples of why it is not hyperbole. — Tarskian

Well lets say this is true. What method did you use to find out that its true? Can you be confident that your own method is sound, or at least more sound then science?

Again, hyperbole. I can assure you if we were able to predict how everything in the universe worked — Philosophim

The complete and perfect theory of everything cannot do that. It won't be able to predict everything. It would improve our ability to predict the physical universe from 0.1% to 0.3% of the true facts. So, it will possibly triple the predictive power of physics but not more than that.

We already have the theory of everything for the natural numbers, which is PA. It does not help us to predict the vast majority of mathematical truths. Most of the truth about the natural numbers is still unpredictable.

No, nothing you have discovered here has shaken the foundations of math or science. — Philosophim

I did not discover anything. Gödel certainly did. Chaitin also did. Yanofsky moderately did. I just mentioned their work.

What method did you use to find out that its true? — Philosophim

It is an opinion and not a theorem. There is nothing wrong with mathematics or with science. My problem is with positivism and scientism. I find these ideological beliefs to be very dangerous.

No, nothing you have discovered here has shaken the foundations of math or science.
— Philosophim

I did not discover anything. Gödel certainly did. Chaitin also did. Yanofsky moderately did. I just mentioned their work. — Tarskian

Right, and despite their work being concluded for quite some time now, people several times smarter than both you and I combined still hold math and science as tools of precision and meaningful discovery.

My problem is with positivism and scientism. I find these ideological beliefs to be very dangerous. — Tarskian

I find this point more interesting. Why?

Right, and despite their work being concluded for quite some time now, people several times smarter than both you and I combined still hold math and science as tools of precision and meaningful discovery. — Philosophim

If you feel threatened by its chaotic nature, it means that it disturbs your ideological beliefs. Someone who really uses them as tools of precision and meaningful discovery would never feel threatened by that.

I find this point more interesting. Why? — Philosophim

It is probably best to use an example from the Soviet Union but in fact modern western society does exactly the same:

https://www.marxists.org/subject/marxmyths/john-holloway/article.htm

In speaking of Marxism as ‘scientific’, Engels means that it is based on an understanding of social development that is just as exact as the scientific understanding of natural development. For Engels, the claim that Marxism is scientific is a claim that it has understood the laws of motion of society. This understanding is based on two key elements: ‘These two great discoveries, the materialistic conception of history and the revelation of the secret of capitalistic production through surplus-value, we owe to Marx. With these two discoveries Socialism becomes a science. The claim that Marxism is scientific is taken to mean that subjective struggle (the struggle of socialists today) finds support in the objective movement of history. The notion of Marxism as scientific socialism has two aspects. In Engels’ account there is a double objectivity. Marxism is objective, certain, ‘scientific’ knowledge of an objective, inevitable process. Marxism is understood as scientific in the sense that it has understood correctly the laws of motion of a historical process taking place independently of men’s will. All that is left for Marxists to do is to fill in the details, to apply the scientific understanding of history. The attraction of the conception of Marxism as a scientifically objective theory of revolution for those who were dedicating their lives to struggle against capitalism is obvious. At the same time, however, both aspects of the concept of scientific socialism (objective knowledge, objective process) pose enormous problems for the development of Marxism as a theory of struggle.

It is very convincing, because it sounds scientific, and because it insists that it is scientific, and especially because you will get burned at the Pfizer antivaxxer stake if you refuse to memorize this sacred fragment from the scripture of scientific truth for your scientific gender studies exam.

As you can see, everybody who craves credibility insists on sailing under the flag of scientism and redirect the worship and adulation of the masses for the omnipotent powers of science to themselves and their narrative.

Noson Yanofsky's book on this subject sounds quite interesting, it's been on my reading list. Still, from what I understand of his thesis, I don't think he is trying to motivate any sort of thoroughgoing rejection of "science" as a tool for decision-making or developing knowledge

It is very convincing, because it sounds scientific, and because it insists that it is scientific, and especially because you will get burned at the Pfizer antivaxxer stake if you refuse to memorize this sacred fragment from the scripture of scientific truth for your scientific gender studies exam

Now, this might be a bit of hyperbole, no? Didn't the NHS itself publish a study suggesting that vaccination might not be a net positive for young British males, even if it was still warranted due to its downstream effects on overall population health?

And no one got arrested for selling people all the horse dewormer they wanted to gobble down. I happened to catch it live when our former President proclaimed that he was "on the hydroxy right now" despite not even being sick, and he seems fairly likely to become POTUS again, rather than having been burnt alive.

If you feel threatened by its chaotic nature, it means that it disturbs your ideological beliefs — Tarskian

Does one have non-ideological beliefs? Is that a thing now? You wear double-layer body armor in your words because you know the environment (truth) presents an imminent danger (your baseless ideology), Ironic no? Prove me wrong mate.

It is very convincing, because it sounds scientific, and because it insists that it is scientific, and especially because you will get burned at the Pfizer antivaxxer stake if you refuse to memorize this sacred fragment from the scripture of scientific truth for your scientific gender studies exam.

As you can see, everybody who craves credibility insists on sailing under the flag of scientism and redirect the worship and adulation of the masses for the omnipotent powers of science to themselves and their narrative. — Tarskian

I’m detecting a distinct political slant here. Is it Libertarianism? Trumpism? Anarchism? Would I be right to surmise that you are not a backer of climate change science?

My problem is with positivism and scientism. I find these ideological beliefs to be very dangerous.
— Tarskian

I find this point more interesting. Why? — Philosophim

I would agree with @Tarskian, especially a mix of both can be harmful, because one can come to be so dogmatic that one starts to think that model or theory of reality is far more real than just the reality itself. And this dogmatism leads people forgetting that scientific theories are only models of reality. You don't care how real life is different from the scientific model, the model itself is right.

Scientism itself can be viewed as a derogatory remark, but positivism itself isn't so bad, if you don't use it too much and aren't open to other thoughts. For example let's think about Comte's law of three stages, where first people believe in myths and magic, then the society transform's to a transitional metaphysical state and then finally, it becomes positivist society based on scientific knowledge.

That is an interesting idea, but is it a law? Will this really evidentially happen because it's a law? It's a building block of positivism itself, sure, but is it a building block of reality?

The true nature of the universe of mathematical facts makes lots of people uncomfortable.

Imagine that we had a copy of the theory of everything?

It would allow us to mathematically prove things about the physical universe. It would be the best possible knowledge that we could have about the physical universe. We would finally have found the holy grail of science.

What would the impact be?

Well, instead of being able to predict just 0.1% of the facts in the physical universe, this would improve to something like 0.3%; and not much more. — Tarskian

The most powerful implication of chaos theory , and complex dynamical systems theory, is that phenomena that appeared within previous frameworks to be merely random are in fact intricately ordered. This is a deterministic order , but it can’t be discovered by using a linear causal form of description. It is a concept of chaos as a special sort of order, not something in opposition to it, as the title of the OP seems to suggest. It is necessary to understand how recursivity and non-linearity function to produce complex global behavior that cannot be reduced to a linear determinism. I think the lesson here is that the most vital aspect of scientific understanding is not search for certainty but patterned relationality. A much richer and more useful form of anticipatory predictiveness becomes available to us once we give up the goal of certainty. The universe isn’t certain in a mathematical sense because it is constantly changing with respect to itself, but it is changing in ways that we can come to understand more and more powerfully.

I’m much less interested in how many decimal places
one can add to a particular mathematical depiction of a scientific theory than I am in how that theory organizes the phenomena that it attempts to mathematize. The sacrifice of that precision for the sake of an alternate theory which organizes events in a more intricate way is well worth the loss of precision.

If you feel threatened by its chaotic nature, it means that it disturbs your ideological beliefs. Someone who uses them as tools of precision and meaningful discovery would never feel threatened by that. — Tarskian

I'm not threatened, I'm just having a conversation with you. Here I try to elevate the discussion more than emotion, politics, or bias. Its about trying to get to the root rationale of arguments and see if they hold up. Your answer is an emotional one, not a rational one. It can take some time to adapt coming from other forums, I get it. So lets think about it again. If these old discoveries really did shake the foundation, why are people smarter than us don't seem bothered and still use them?

It is probably best to use an example from Soviet Union but in fact modern western society does exactly the same: — Tarskian

I think your problem isn't with science, but when people use the word 'science' to describe something that isn't actually scientific. Science is a very rigorous method of testing, and in essence tries to prove its conclusions wrong, not prove them right. The idea is to see if something can be disproven, and if it can't, then it must be something that works with what we know today.

and especially because you will get burned at the Pfizer antivaxxer stake if you refuse to memorize this sacred fragment from the scripture of scientific truth for your scientific gender studies exam. — Tarskian

It sounds like you have an issue with Covid vaccines and gender studies. Or more importantly, perhaps you have an issue with the way some people have reported on it? Many people have opinions on the science involving these two fields, but that doesn't mean it accurately reflects the science of those two fields.

We can test this by first starting with Covid vaccines. What part are you against specifically? I am moderately familiar with the scientific consensus on the Covid vaccines, and we can see if your issue is with the science itself, or people's opinions on the science itself.

I would agree with Tarskian, especially a mix of both can be harmful, because one can come to be so dogmatic that one starts to think that model or theory of reality is far more real than just the reality itself. — ssu

Isn't your problem with dogmatism, or a misuse and/or misunderstanding of science/positivism, instead of with science/positivism itself?

Isn't your problem with dogmatism, or a misuse and/or misunderstanding of science/positivism, instead of with science/positivism itself? — Philosophim

Yes, absolutely! All the various philosophical schools of thought have contributed each their way. Even if I criticize reductionism and favour the idea of more-is-different, there's a place for reductionism. Yet positivist are the one's that can quite easily fall into that dogmatism.

Perhaps only scientism can be defined so negatively, that is basically something derogatory. (Note that Tarskian referred to scientism, not science.)

But a sentence is not the same as a string. — Treatid

Sorry, I did no follow the intent of the rest of your post.

The question I replied to was from @Banno, who asked: "Why should we suppose that natural languages are only countably infinite?"

I gave a proof that the set of finite-length strings over a countably infinite alphabet is countably infinite.

That is, there are at most countably many finite-length expressions, strings, words, sentences, books, in any natural language.

I was confused by your quoted point here, since a sentence is a particular kind of well-formed finite-length strings. So the sentences are a proper subset of the strings. If the strings are countable so are the sentences.

Can you clarify your post? I may have missed something.

The interpretation of a sentence depends on the context/axioms. The same string in two axiomatic systems is two distinct sentences. — Treatid

I'm talking syntax, not semantics. There are only countably many finite-length strings.

I do see your point. Even if there are countably many strings, each string could be given a different interpretation, so that there could be lots more meanings.

That's a point about models, or interpretations, or semantics, and I'm not sure it's the appropriate context for the question. On the other hand you think it is, so at least let me try to respond in that context as well.

If there are at most countably many axiom systems or interpretations, then there are still only countably many sentences.

The only way you could make your idea work would be to have uncountably many interpretations. Do you have that many interpretations?

Also I haven't hear "sentence" used in this way. I thought the idea about sentences was two expressions that say the same thing, for example in different languages.

I haven't heard a sentence as you are defining it, as a syntactic string plus an interpretation. Is this something people do?

In any event, as long as you only have countably many interpretations per string, you'll still only have countably many sentences in your definition, assuming I'm understanding your post.

However, the assertion that natural languages are countably infinite no longer holds given there are an uncountable infinite number of contexts for any given sentence. — Treatid

Ok I see you anticipated my point. Can you suggest a context in which I can conceptualize an uncountably infinite number of contexts for interpreting a language?

And again, I haven't seen "sentence" used this way. There seems to be a blurring of syntax and semantics.

Most mathematical truth is unprovable and therefore unpredictable, if only because most of its truth is ineffable ("inexpressible"). — Tarskian

Going back to your top post:

I read the paper. It's true, but there's less there than meets the eye.

They're only talking about undefinable sets. Sets of natural numbers that can't be characterized by a predicate. There are uncountably many sets, and only countably many predicates (a predicate being a finite string over an at most countable alphabet). So "almost all," all but countably many sets of natural numbers, can't be described.

So if $S$ is one such indescribable set (whose elements are essentially random: there's no way to describe them like "the prime numbers," or "the even numbers," or whatever), we have a bunch of true facts like $s \in S$ for each element $s$ that happens to be in $S$. And so forth.

So there are uncountably many facts about the powerset of the natural numbers that can not be expressed, but that are clearly true.

This is perfectly correct as far as it goes. But how far does it go?

There is nothing particularly interesting about a random set. It has no characteristic property that lets us determine whether a particular number is or isn't in the set. We have to look and see if it's in there. There's no rhyme or reason to the members of a random set.

These are all mathematical truths, but they're not very interesting mathematical truths.

What mathematicians do is find the interesting mathematical truths. The ones that form an overarching structural narrative of math. Perhaps the author of the paper, or Chaitin, are saying that this narrative is an illusion; that the mathematical truths we discover are a tiny, almost irrelevant subset of all the mathematical truth that's out there.

I think the opposite view could be taken. That the work of mathematicians in developing interesting, axiomatic mathematical truth, has value. It's what humans bring to the table.

How about this metaphor. Mathematicians are sculptors. Out of the uncountably infinite and random universe of mathematical truth, mathematicians carve away the irrelevant and uninteresting truths, leaving only the beautiful sculpture that is modern mathematics, those truths that we can express and prove. They're special just for being that.

These are all mathematical truths, but they're not very interesting mathematical truths. — fishfry

Agreed. Unpredictable truths in the physical universe are usually not particularly interesting either. The difference is that we can see them or at least observe them. That is why we know that the physical universe is mostly unpredictable. Our own eyes tell us. In order to "see" a mathematical truths, however, we need some written predicate. Otherwise, such truth is invisible to us.

If we completely ignore the unpredictable truths in the physical universe, it also gives us the impression of being beautifully and even majestically orderly. In that perception of the physical universe, there is no chaos. In that case, the physical universe also looks like a beautiful sculpture.

leaving only the beautiful sculpture that is modern mathematics — fishfry

Yes, and that is absolutely not the problem.

The problem is that people such as David Hilbert are convinced that the beautiful sculpture is all there is. Hilbert insisted on the idea that his colleagues had to work overtime in order to give him proof of his false belief:

https://en.wikipedia.org/wiki/Hilbert%27s_program

Statement of Hilbert's program

The main goal of Hilbert's program was to provide secure foundations for all mathematics.

Completeness: a proof that all true mathematical statements can be proved in the formalism.
Decidability: there should be an algorithm for deciding the truth or falsity of any mathematical statement.
...
Kurt Gödel showed that most of the goals of Hilbert's program were impossible to achieve.

The vast majority of people still see mathematical truth like Hilbert did. They still see mathematical truth as a predictable and harmonious orchestra of violins.

Out of the uncountably infinite and random universe of mathematical truth

Yes, you seem to know it perfectly fine. Most people, however, don't know it, simply because they don't want to know it.

They believe that one day we will discover the fundamental knowledge to see the entire physical universe also as a beautiful sculpture. We have already discovered the fundamental knowledge of arithmetic. Its axioms are known already and arithmetical truth is absolutely not a beautiful sculpture. Instead, it is uncountably infinite and random.

For natural language to be uncountable, you must find a sentence that cannot be added to the list. To that effect, you would need some kind of second-order diagonal argument. — Tarskian

Sure. What this argument purports to show is that a natural language has no fixed cardinality. And this is what we might expect, if natural language includes the whole of mathematics and hence transfinite arithmetic.

But the point is that "...the collection of all properties that can be expressed or described by language is only countably infinite because there is only a countably infinite collection of expressions" appears misguided, and at the least needs a better argument.

Your posts sometimes take maths just a little further than it can defensibly go.

I didn't completely follow what you're doing, but in taking the powerset of a countably infinite set, you are creating an uncountable one. There aren't uncountably many words or phrases or strings possible in a natural language, if you agree that a natural language consists of a collection of finite-length strings made from at an most countably infinite alphabet. I think this might be a flaw in your argument, where you're introducing an uncountable set. — fishfry

Not I, but Langendoen and Postal. If you wish you can take up the argument, I'm not wed to it, I'll not defend it here. I've only cited it to show that the case is not so closed as might be supposed from the Yanofsky piece. Just by way of fairness, Pullum and Scholz argue against assuming that natural languages are even infinite.

Langendoen and Postal do not agree that "a natural language consists of a collection of finite-length strings".

Does mathematics also "consists of a collection of finite-length strings made from an at most countably infinite alphabet"?

Also, doesn't English (or any other natural language) encompass mathematics? It's not that clear how, and perhaps even that, maths is distinct from natural language.

All of which might show that the issues here are complex, requiring care and clarity. There's enough here for dozens of threads.

But the point is that "...the collection of all properties that can be expressed or described by language is only countably infinite because there is only a countably infinite collection of expressions" appears misguided, and at the least needs a better argument.

Your posts sometimes take maths just a little further than it can defensibly go. — Banno

The lemma that the number of possible expressions in language is countably finite is actually a core argument in Yanofsky's paper:

http://www.sci.brooklyn.cuny.edu/~noson/True%20but%20Unprovable.pdf

Another important uncountably infinite set is the collection of subsets of the natural numbers. The collection of all such subsets is uncountably infinite. Now that we have these different notions of infinity in our toolbox, let us apply them to our concept of true but unprovable statements. All language is countably infinite. The set of statements in basic arithmetic, the subset of true statements, and the subset of provable statements are all countably infinite.

This brings to light an amazing limitation of the power of language. The collection of all subsets of natural numbers is uncountably infinite while the set of expressions describing subsets of natural numbers is countably infinite. This means that the vast, vast majority of subsets of natural numbers cannot be expressed by language. The above examples of subsets of natural numbers are expressed by language, but they are part of the few rather than the many. The majority of the subsets are inexpressible. They defy language.

There is simple proof for the lemma that language is countably finite. Yanofsky's paper does not mention it but the proof is trivial:

https://math.stackexchange.com/questions/1206460/proving-that-the-set-of-all-english-words-is-countble

This is the question : Prove that the set of all the words in the English language is countable (the set's cardinality is אo) A word is defined as a finite sequence of letters in the English language.

Answer 1: There are 26 letters in the English language. Consider each letter as one of the digits on base 27. This mapping yields that the cardinality of your set is ≤|N|, hence this set is countable.

Answer 2: The set Sn of the English words with length n is finite (this is almost obvious). So it's also countable. Why is it finite? The set An of all sequences with length n made up of latin characters is finite as it contains 26n elements. Only some of these sequences are meaningful/actual English words. So Sn⊂An. So Sn is also finite. The set T for which you have to prove that it is countable is: T=S1∪S2∪S3∪... Now you have this theorem: "A countable union of countable sets is also countable". Applying it you get that T is also countable. Thus your statement has been proved.

Not I, but Langendoen and Postal. If you wish you can take up the argument, I'm not wed to it, I'll not defend it here. I've only cited it to show that the case is not so closed as might be supposed from the Yanofsky piece. — Banno

Langendoen and Postal argue in "The vastness of natural languages", 1984, that natural-language sentences can be infinitely long.

https://aclanthology.org/J89-1006.pdf

This book is an extended argument in support of the theses that natural languages are transfinitely unbounded collections, that sentences are not limited in length (number of words) by any cardinal number, finite or transfinite, and that no constructive grammar can be an adequate grammar for any natural language.

https://fa.ewi.tudelft.nl/~hart/37/publications/the_papers/on_vastness.pdf

However, as I mentioned before, the authors do not so much argue for “not assuming a size law” but for “assuming the negation of a size law”. For example, the rules (if any) of English do not stipulate a maximum finite length of sentences; one can easily break such a stipulation by prefixing a maximum length sentence with “I know that”. The rules of English also do not explicitly state that sentences should be finite; one can add “All English sentence should be finite in length” to the rules or not. The authors argue, quite vociferously at times, against adding that condition mostly on the grounds that it is not a purely linguistic one. However, and this is where I disagree, they then conclude that, somehow, necessarily there should be sentences of infinite length.

Yanofsky, on the other hand, assumes that language sentences, especially predicate formulas that describe natural-number subset properties in ZFC, are necessarily finite.

Even though infinitary logics allows for infinitely long predicate formulas, they cannot be represented in language but only by their parse trees:

https://en.wikipedia.org/wiki/First-order_logic

Infinitary logic allows infinitely long sentences. For example, one may allow a conjunction or disjunction of infinitely many formulas, or quantification over infinitely many variables. Infinitely long sentences arise in areas of mathematics including topology and model theory.

Infinitary logic generalizes first-order logic to allow formulas of infinite length. The most common way in which formulas can become infinite is through infinite conjunctions and disjunctions. However, it is also possible to admit generalized signatures in which function and relation symbols are allowed to have infinite arities, or in which quantifiers can bind infinitely many variables. Because an infinite formula cannot be represented by a finite string, it is necessary to choose some other representation of formulas; the usual representation in this context is a tree. Thus, formulas are, essentially, identified with their parse trees, rather than with the strings being parsed.

Hence, the size of logic statements represented by language alone cannot be infinite. Therefore, the language of ZFC is still countably infinite.

Overcoming this constraint would require the use of meta-programs instead of predicates as set membership functions that have infinite while loops -- beyond primitive recursive arithmetic (PRA). These programs can then generate infinitely long predicates in the language of ZFC to describe Yanofsky's subsets. The use of such predicate-generating meta-programs instead of predicates as set membership functions is not supported in the language of ZFC.

Furthermore, this would still not help, because there are only countably infinite programs. There would still not be enough programs to describe all the uncountably infinite subsets of the natural numbers.

Not I, but Langendoen and Postal. If you wish you can take up the argument, I'm not wed to it, I'll not defend it here. I've only cited it to show that the case is not so closed as might be supposed from the Yanofsky piece. Just by way of fairness, Pullum and Scholz argue against assuming that natural languages are even infinite. — Banno

I'll check out those links. But if they deny natural languages are even infinite, then they surely aren't uncountable.

I do think natural language is infinite, in the sense that there are infinitely many legal sentences. The sun rises in the morning, I know the sun rises in the morning, I know that I know the sun rises in the morning, etc. There is a countable infinity of those.

Langendoen and Postal do not agree that "a natural language consists of a collection of finite-length strings". — Banno

I'm confused by that. If you allow infinite length strings then there are uncountably many of them, though most aren't grammatical. Are they making an argument about grammatical constraints?

Does mathematics also "consists of a collection of finite-length strings made from an at most countably infinite alphabet"? — Banno

Formally, yes. Every mathematical statement or proof has finite length. There are only countably many mathematical statements. That's the argument in the paper. There are uncountably many truths, but only countably many of them can be expressed.

Also, doesn't English (or any other natural language) encompass mathematics? It's not that clear how, and perhaps even that, maths is distinct from natural language. — Banno

As formal systems, probably not much difference. But natural language is much messier than math, I'm not even sure if a computer could determine whether a string is legal in natural language. Not once we include slang and the language of pop culture and the young.

All of which might show that the issues here are complex, requiring care and clarity. There's enough here for dozens of threads. — Banno

Well I argued in my earlier post that there's less to that paper than meets the eye. The inexpressible truths in the paper are trivial and unimportant. I wonder if there are nontrivial truths that can't be expressed, and what that would even mean.

This was my first thought. Natural languages would seem to need to be computable, which would entail countably finite. — Count Timothy von Icarus

I wonder about that. Think of the slang the kids of every generation come up with. No algorithm could predict that. Humans not just using, but constantly recreating their own language. New words and ideas and phrases are constantly coming into existence, sometimes gaining traction in the general culture, sometimes fading away. I think that the way humans evolve their own languages in so many ways, is something that humans can do that perhaps algorithms can't. I'll just put that out there.

This reminds me a little of Chomsky's generative grammars. He revolutionized linguistics by saying there are structural elements common to all human languages. Not programs, per se, but structures. Just my impressions, that's all I know about it.

That should read "countably infinite." We can think of endless permutations of language, but we could also spend and infinite amount of time saying the names of the reals between any two natural numbers.

...there's less there than meets the eye. — fishfry

Nicely phrase. Our new chum is propounding much more than is supported by the maths. Here and elsewhere.

Any readable proof of Cantor's Theorem will contain at most a finite number of characters. Yet it shows can be used to show* that there are numbers sets* with a cardinality greater than ℵ0.

And we are faced again with the difference between what is said and what is shown.

So will we count the number of grammatical strings a natural language can produce, and count that as limiting what can be - what word will we choose - rendered? That seems somehow insufficient.

And here I might venture to use rendered as including both what can be said and what must instead be shown.

Somehow, despite consisting of a finite number of characters, both mathematics and English allow us to discuss transfinite issues. We understand more than is in the literal text; we understand from the ellipses that we are to carry on in the same way... And so on.

But further, we have a way of taking the rules and turning them on their heads, as Davidson shows in "A nice derangement of epitaphs". Much of the development of maths happens by doing just that, breaking the conventions.

Sometimes we follow the rules, sometimes we break them. No conclusion here, just a few notes.

* just for @ssu

Any readable proof of Cantor's Theorem will contain at most a finite number of characters. — Banno

Any proof will contain at most a finite number of characters. At least for us finite entities.

Yet it shows that there are numbers with a cardinality greater than ℵ0. — Banno

That's actually not Cantor's theorem (the power set of any set has a strictly greater cardinality than the set itself).

What Cantor shows is that there cannot be a bijection between the natural numbers and the reals by reductio ad absurdum. That's it. Notice that it's an indirect proof. And notice that already from this we have an open question, the Continuum Hypothesis.

Yet this doesn't stop Cantor treating uncountable infinities as normal ones and he continues adding things up in cascading system of larger and larger infinities while trying to evade paradoxes. Many mathematicians even today are doubtful of this, even if they might be not mainstream.

It is a false meme that the Cantor proofs mentioned here are by contradiction or indirect. Moreover, the proofs are constructive.

(1) The theorem known as 'Cantor's theorem' has the key part ('P' for 'the power set of'):

For all x, there is no function from x onto Px.

Proof:

Let g be a function from x to Px.
Let D be {y | y e x & ~ y e g(y)}.
So D is not in the range of g.
So g is not onto Px.

That's a direct proof. And it's constructive: Given any function g from x to Px, we construct a member of Px that is not in the range of g.

(2) Cantor's other famous proof in this regard ('w' for 'the set of natural numbers'):

There is no function from w onto the set of denumerable binary sequences

Proof:

Let g be a function from w to the set of denumerable binary sequences
Let d be the function from w to the set of denumerable binary sequences such that:
for all n in w, d(n) = 0 if g(n)(n) = 1 and d(n) = 1 if g(n)(n) = 0.
So d(n) is not in the range of g.
So g is not onto the set of denumerable binary sequences.

That's a direct proof. And it's constructive: Given any function g from w to the set of denumerable binary sequences, we construct a denumerable binary sequence that is not in the range of g.

/

Cantor did propose answers to the paradoxes (though his answers are not in the axiomatic method) but I don't know that Cantor's showing that there are always sets of larger infinite size was meant to evade the paradoxes. Indeed, it is the fact that there are always sets of larger infinite size that allows a paradox in Cantorian set theory. Cantor's answer to that paradox is another matter.