The Need for Formality in Mathematics

Page last updated 02 Jul 2024

Some time ago, I came across a webpage by Mark Chu-Carroll entitled Why we need formality in mathematics. This might be interesting I thought, for a number of reasons. One was that there has never been any proof, never mind a formal proof of the notion that there are more real number than natural numbers, nor that indefinable numbers “exist” (see Proof of more Real numbers than Natural numbers?). And then there was the observation that Chu-Carroll’s website was full of articles ridiculing people, such as:

where he finds easy targets that he can poke fun at, completely unaware that he has no solid foundation for his own intuitive beliefs. In short, Chu-Carroll is a typical example of someone who accepts unquestioningly the notion that there are are more real number than natural numbers and that indefinable numbers “exist”, completely unaware that there has never been any proof of these notions, that they are only based on intuition (see Proof of more Real numbers than Natural numbers?). The result is that Chu-Carroll’s discussions amounted to little more than the pointless tit-tat exchange of conflicting opinions.

So I was interested to see how Chu-Carroll, having proclaimed a need for formality in mathematics, would react to being asked to show where there is a formal proof of his notion that there are more real number than natural numbers, or that indefinable numbers “exist”. And, as I expected, as soon as he realized that there is indeed no such proof, he was left flailing in desperate attempts to rescue the situation, among which was the risible claim that Chaitin’s Omega defines an indefinable number! In the end, he refused to engage any further with me. Interestingly, since my discussion with Chu-Carroll, he hasn’t published any more articles with his “Cantor Crankery” flavour.

I include below the discussion between Mark Chu-Carroll and myself from that webpage on formality on mathematics. For convenience for the reader, I have left out comments other than those between Chu-Carroll and myself. You can click on the head of each comment to see the comment on the original page. Note: in this discussion, Chu-Carroll also engaged in disgraceful misrepresentations of what I had said, see the separate page The Duplicity of Mark Chu-Carroll.

James R Meyer Jan 15, 2018 at 8:34 am

Lovely post, Mark. I know it is a while since the last comment here, but I think that you omitted a crucial detail in your article, which I want to bring to your attention.

Let me start by stating that I completely accept that the diagonal proof does indeed prove that there can be no enumeration of the real numbers in the same language as those real numbers.

Formalized versions of the diagonal argument only establish that, given an enumeration of real numbers, and which is not an enumeration of all real numbers, then another real number can be defined in terms of that enumeration. From this we can further conclude that there cannot be an enumeration of all real numbers, since then we would have a number that was both in and not in the enumeration. That’s all the diagonal proof proves. It says nothing at all about whether there are “more” real numbers than natural numbers. That is given by an additional argument, which is usually not even stated.

Of course, in a correctly formulated fully formal proof, it must be the case that the function that is assumed to exist and which maps the natural numbers to the real numbers must necessarily be in the same language as the real numbers of the proof. Clearly, if an enumeration of real numbers is defined in the same language system as those real numbers, then it is a straightforward matter to define a diagonal number in terms of that enumeration within that same language system.

What you overlook, in common with almost everyone else, is that the argument that the reals constitute some sort of “bigger” infinity arise from an informal argument which is never given in a formal fashion, but which involves different levels of language. It is typically stated like this:

If every real number could be expressed in some language as some finite combination of symbols, then we could easily have a method of matching the natural numbers to these combinations of symbols. All that is required is an alphabetical style ordering of all the symbols used to define real numbers (in the same way as a, b, c … is the order for the English alphabet), and then you simply list them in the same way as you would order the words in a dictionary. And if you could list them, you can obviously attach natural numbers to every item in the list. But this would contradict the diagonal argument, so there must be real numbers that cannot have any finite representation.

Now, that informal argument forces any enumeration of the reals to be in a different language system (a meta-language) from the real numbers of the enumeration (which are in the object language). In short, that informal argument introduces different levels of language while at the same time, using intuition to completely ignore whether that introduction of different levels of language might affect the overall proof.

But in order to prove that a diagonal number can be defined from any infinite such enumeration, it would be necessary to prove that the meta-language in which the enumeration is defined can determine the numerical value of every symbol sequence within the object language that represents a real number – since without that capability, it is impossible for the meta-language to define a diagonal number.

If you can provide such a proof, as you say, “without any vagueness” – perhaps with (as you state in your article) a “notation [that] makes things clearer than natural language prose”, and that does not (as you say) “rely on intuition”, I would very much like to see it. Of course you are aware that in a proof, the onus is on the person who insists that his proposition is correct to prove it – the onus is not on an objector to prove that an unproven argument is incorrect (although for a number of reasons, too lengthy to state here, I believe that such a proof is not possible).
1. markcc Post author Jan 16, 2018 at 2:09 pm
  
  I think that you’re a bit confused in here, but in a way that might have a kernel of reasonability under it.
  
  When you’re talking about languages, I think what you actually mean is more than just syntactic notation – it’s the semantics of the system that you’re working in. And it’s absolutely true that Cantor’s proof is specific to the semantic system of axiomatic set theory. It’s built from the set theoretic concept of cardinality and the set theoretic notion of cardinality comparison.
  
  You can build a valid axiomatic system in which it’s not true. You can build different mathematical systems with different properties. It’s possible and even reasonable to build a mathematical system which _doesn’t_ include non-computable numbers. In a system like that, the set of “real” numbers (the computable reals) has the same cardinality as the set of integers. But it’s not the same system of mathematics that we’re talking about.
  
  Mathematics is a set of systems, and the base of all of those systems in the way that we talk about them most of the time is axiomatic set theory. When you talk about real numbers, what you’re talking about is a set of values defined as the equalence classes of the limits of Cauchy sequences over sets of rationals; and rationals are ratios defined by equivalence classes of ordered pairs over the set of natural numbers, and so on. If you want to talk about comparing the cardinality of the set of real numbers to the cardinality of some other set, then you’re stuck with the framework of set theory – because that’s the “language” in which they’re defined, the language in which their meaning is expressed.
  
  Trying to talk about how the conclusions of applying set theory to the real numbers is wrong is like trying to talk about how the hebrew word “adamah” can’t mean earth, because in english, adamant is spelled with an A, and an uppercase A is pointy, but the earth is round. You’re mixing concepts that don’t make any sense.
James R Meyer Jan 17, 2018 at 6:41 am

First, can we please agree to not accuse each other of being confused? That’s unproductive.

As I have said before, I completely accept that the diagonal proof, when stated correctly in a given language system, proves that there can be no enumeration of real numbers in that language system. And that there are formal proofs that prove that there can be no function within that formal system that enumerates the real numbers of that language system. But I do not accept that that proves that there are “more” reals than natural numbers.

You belittle people who don’t use language that you consider sufficiently formal. But I don’t see that you have provided even a semi-formal proof that there can be “more” elements of infinite set than another. It seems to me that what you do is to appropriate common English words and attach a meaning to them that is completely alien to their common usage.

The typical argument that is given (such as that of Christopher McClain above) that there can be “more” elements of one infinite set than another goes like this:
Since the proposition that:
(there is an injection but no bijection from B to A)
is equivalent to:
(cardinality of A > cardinality of B)
is also equivalent to:
(the number of elements of A > the number of elements of B)
or in common English parlance A has more elements than B.

But the last equivalence only applies if the sets A and B are finite, and where the variable “number” has the domain of natural numbers. The assertion that we can extend the equivalence of cardinality and “more” to apply for infinite sets amounts to pleading that:
Since the number of elements of an infinite set is limitless, then if A and B are infinite, this becomes:
(there is an injection but no bijection from B to A)
is equivalent to:
(cardinality of A > cardinality of B)
is equivalent to:
(the number of limitlessly many elements of A > the number of limitlessly many elements of B)

But of course, that would be absurd, since there is no natural number that defines “limitlessly many”, it is not a member of the domain of “natural number”.

In short, pleading that different cardinalities of infinite sets “proves” that there are “more” elements in one set than another is an absurdity, where rather than actually providing a proof, a word in the English language is appropriated and everyone is told that they must accept an additional meaning (greater cardinality of an infinite set) besides the conventional English meaning.

If I may quote from your comment: “You’re mixing concepts that don’t make any sense.” Exactly!

Of course, if instead you can come up an actual proof there can be “more” elements of one infinite set than another then do please provide it.

I have two “by the ways” below, which are incidental to the main point.
1) You state that: “…Cantor’s proof…[is] built from the set theoretic concept of cardinality and the set theoretic notion of cardinality comparison.” It was only in 1874 when Cantor first provided a proof – that there is no enumeration of the reals – that the subject of cardinality of infinite sets was first envisaged. So it was that finding that precipitated the notion of applying the notion of cardinality to infinite sets, not the other way around.

2) I don’t agree that set theory is “the” language in which real numbers are defined. It’s “a” language in which real numbers might be defined. It would be nonsense if anyone suggested that there aren’t alternative ways of defining real numbers. Mathematicians were defining real numbers in different ways long before set theory was invented. Besides, when does one ever see a real number defined in purely set-theoretic symbols such those for “is an element of” “is a subset of”, etc? For sure, scientists and engineers don’t use such definitions of real numbers.
1. markcc Post author Jan 17, 2018 at 7:04 am
  
  But all you’re doing is saying that you don’t like the definition of cardinality. Set theory does define a notion of cardinality. It’s quite well-defined, if you take the time to study set theory.
  
  You’re basically arguing that we shouldn’t be allowed to say that the cardinality of the set of real numbers is larger than the cardinality of the set of natural numbers, because you don’t like the definition of cardinality.
  
  You say things like: “But the last equivalence only applies if the sets A and B are finite, and where the variable “number” has the domain of natural numbers. The assertion that we can extend the equivalence of cardinality and “more” to apply for infinite sets amounts to pleading that…”
  
  That’s simply not true. The set theoretic definition of equality *doesn’t* only apply to finite sets. It’s defined for *all* sets. You may not like that – but if you’re talking about set theoretic mathematics? What you like doesn’t matter.
  
  The definition of cardinality isn’t limited to finite sets. Pick up any textbook on set theory: cardinality is defined in terms of 1:1 mappings; and using the axiom of infinity and induction, it’s applicable to any set, not just finite ones.
  
  You don’t like that, because you don’t think that talking about “cardinality” makes intuitive sense for non-finite sets. But that doesn’t matter: it’s well-defined by the axioms of set theory. Your comfort doesn’t matter. Your dislike for applying tho concept of cardinality comparison to infinite sets doesn’t matter. You’re talking about mathematics defined under axiomatic set theory, and that means that you’re stuck working in terms of the definitions of axiomatic set theory.
  1. James R Meyer Jan 17, 2018 at 8:17 pm
    
    You said “But all you’re doing is saying that you don’t like the definition of cardinality. … You’re basically arguing that we shouldn’t be allowed to say that the cardinality of the set of real numbers is larger than the cardinality of the set of natural numbers, because you don’t like the definition of cardinality.”
    
    FACT:
    I didn’t state anywhere that there one should not be able to state that one infinite set has a larger cardinality than another. I don’t have any problem with that, it merely indicates the direction of an injection. Please do not attribute arguments to me that I did not make. It’s unprofessional, bedsides the obvious straw man fallacy.
    
    You also said “That’s simply not true. The set theoretic definition of equality *doesn’t* only apply to finite sets. It’s defined for *all* sets. You may not like that – but if you’re talking about set theoretic mathematics? What you like doesn’t matter.”
    
    FACT:
    I did not argue that equality only applies to finite sets. Perhaps you should read what I wrote more carefully before you respond. Hint: see “the last equivalence only applies if …”
    
    Since it appears that my previous post was misunderstood, I will try to make it completely clear that I do not have any problem with the definitions of cardinality. So:
    
    1) I accept that for all sets A and B (finite or infinite) the proposition that:
    (there is an injection but no bijection from B to A)
    is equivalent to the proposition:
    (cardinality of A > cardinality of B)
    
    2) I also accept that for finite sets A and B the proposition that:
    (cardinality of A > cardinality of B)
    is equivalent to the proposition:
    (the number of elements of A > the number of elements of B)
    or in common English parlance A has more elements than B.
    but I do not accept it for the case where sets A and B are both infinite.
    
    So let me say it again. I have no objection to the definitions of cardinality as being equivalent to the notions of injection of sets as indicated above.
    1. markcc Post author Jan 18, 2018 at 3:17 am
      
      And let me say my response again.
      
      When you’re working in the world of set theory, you don’t get to pick and choose which definitions you “accept”. Axiomatic set theory defines a collection of rules for how you do reasoning. The set of real numbers (see that pesky word, “set”?) is defined by the rules of set theory to have certain properties. The cardinality of a set is defined in a particular way, by the rules of set theory, and that definition applies to all sets, not just the ones that you want it to apply to.
      
      You can quibble about whether or not we can take the formal notions of set theory, and translate them into informal english words. But in my opinion, that’s just silly. If your entire point is “I don’t like it that people use the word “larger” to mean “has greater cardinality”, then I’d say go talk to some linguists. They’re interested in that kind of distinction. But people doing math don’t. When we’re talking about mathematics, everyone understands that english words are shorthands for mathematical definitions. When we say “size” of a set, we mean cardinality. When we say the size of one set is larger than the size of another set, we mean that it has greater cardinality.
2. markcc Post author Jan 17, 2018 at 9:57 am
  
  Sorry for being a bit scattered; I’m traveling for work this week (in Stockholm), and I’m terribly jetlagged.
  
  So: sorry, but when you talk about real numbers, you *are* talking in terms of set theory. The whole discussion is about the size of the set of real numbers. Take away set theory, and you discard the whole basis of the proof. Yes, you can create alternative definitions of the real numbers, but if you do, they’re not the same thing – they’re not the same set of real numbers.
  
  As for scientists and engineers? They don’t actually use real numbers. Scientists and engineers work in terms of measurements. When I was a kid, my dad worked on the Galileo probe, and for trajectory computations for galileo, they used pi=3.1416 – none of the other measurements that were used were more precise than that, so using a more precise value for pi was useless. They were able to navigate a probe from earth to Jupiter using numbers no more precise than 5 significant digits!
  
  In practice, we only use rational numbers. I’ve been known to argue that we’d be better off using a system based on the set of computable numbers instead of the set of reals: the reals have all sorts of objectionable qualities. (I find the obsession of people with Cantor funny, because the cardinality of infinite sets is a simple notion; there’s so much more weirdness that’s I find much harder to accept than just cardinality. Most numbers can’t be identified – they can’t be written, they can’t be computed, they can’t be described, they can’t be identified in any way. That’s a problem: as an intuitionist would happily point out, how can something exist if you can’t ever describe it? Cardinality is easy: I can show you how to compute the exception, even if the computation is infinite; but undescribable numbers? There’s a strong case to be made that they’re a nonsensical artifact of set theory. And yet… if we get rid of them, if we reconstruct the fundamentals of set theory to eliminate that artifact, we lose many other things that we really, really want.)
  
  Continuing with the scientist and engineer theme: most scientists and engineers don’t care about number theory. The engineer who designs the engine in your car doesn’t know diddly-squat about what’s happening on a quantum level to the molecules of fuel burning inside of the cylinder of the engine they’re designing. They know how the gases act as a gas, how they burn, what products the burn produces, how energy can be extracted by it, etc. They don’t understand the deep fundamental level, because there’s just not enough time to be a master in both quantum mechanics and engineering. Similarly, as a software engineer, I have very little understanding of how electrons moving around the chips in my laptop turn into computation. That doesn’t mean that it’s not happening.
  1. James R Meyer Jan 18, 2018 at 6:50 am
    
    You say: “sorry, but when you talk about real numbers, you *are* talking in terms of set theory.”
    
    That’s opinion, not fact.
    
    It might be fact that when you talk about real numbers, you are talking in terms of set theory. But it is your opinion that when I talk about real numbers, I am are talking in terms of your set theory.
    
    You say “you can create alternative definitions of the real numbers, but if you do, they’re not the same thing – they’re not the same set of real numbers.”
    
    Clearly, it’s your opinion that in the entirety of your definitions of set theory, the resultant set of real numbers is a superior set to any set of real numbers given by any other possible definition. You cannot imagine that 300 years from now, there might actually be a better theory of numbers than what conventional ZF set theory provides. That is breathtaking arrogance.
    
    That reminds me of the following quote:
    ‘My theory stands as firm as a rock; every arrow directed against it will return quickly to its archer. How do I know this? Because I have studied it from all sides for many years; because I have examined all objections which have ever been made against the infinite numbers; and above all because I have followed its roots, so to speak, to the first infallible cause of all created things’
    
    Cantor wrote this in 1888. Thirteen years later, Russell’s paradox demonstrated that Cantor’s theory of sets as it was then was contradictory, and had to be patched up by axioms such as ZF.
    1. markcc Post author Jan 18, 2018 at 8:37 am
      
      No, that’s *not* opinion: that’s mathematics.
      
      We’re talking about the set of real numbers, and a proof concerning the cardinality of the set of real numbers.
      
      You don’t get to decide that you accept some conclusions of axiomatic set theory and the theory of real numbers built on it, but reject others on an ad-hoc basis.
      
      That’s the entire point of my original post. We’re talking about formal concepts, not informal ones. There’s a reason why we use formalisms.
      
      You can construct sets of numbers in many different ways. You can certainly create an alternative definition of numbers. For example, Knuth and Conway put together a really interesting construct called surreal numbers. In that construction, you can define sets and cardinality in different ways than the way that we talk about it.
      
      But that’s not what we’re talking about here. Here, we’re specifically talking about Cantor’s framework of sets and cardinality. We’re talking about the set of real numbers, as defined by the set theoretic foundations and the set theoretic theory of real numbers. There’s no opinion here: we’re talking about a proof that’s only meaningful in a specific semantic, logical, and mathematical framework.
      
      If you take the conclusions of that framework, and drop them into an entirely different semantic framework, then you’re wrong. When we talk about comparison of set cardinality, we’re doing it in the realm of sets and cardinal numbers.
      
      You don’t get to argue that the frequency of a beam of red light is larger than the frequency of a beam of ultraviolet light, and then say that it’s just an opinion that you’re wrong, because you think that we should be comparing wavelength instead of frequency, and the wavelength of red light is longer than the wavelength of ultraviolet. That’s not an opinion: that’s just taking a comparison that’s meaningful because of a specific definition of what you’re measuring, and rejecting that definition but still trying to discuss conclusions that are only meaningful in the context of the definition. That’s what you’re doing: taking a word that’s got a very specific, formal meaning, and then insisting that it’s just opinion that that’s it’s meaning.
      
      If you reject the way that cardinality comparison is defined, that’s very nice for you. But it’s got absolutely no bearing on the conclusion of Cantor’s proof, because Cantor’s proof is talking specifically about what the word “larger” means in the context of cardinality.
      
      To put it a slightly different way: if I go to a paint store, and I ask for paint that’s a specific shade of blue in the Pantone spectrum, I don’t get to return the paint for being the wrong color because the Pantone spectrum definition of that shade of blue is wrong. I asked for the paint *in that system*, and so the definition from that system is right in that discussion.
      1. markcc Post author Jan 18, 2018 at 8:42 am
        
        To expand one important point, that I think I glossed over a bit in the previous comment:
        
        If, a hundred years from now, people are working with a different foundation for mathematics, it’s possible that Cantor’s reasoning about cardinality will no longer make sense. It could change for technical reasons, if someone finds a better foundation; it could change for stylistic reasons. But if it changes, then *in that new framework*, you could have different results.
        
        And yet, that won’t affect anything about Cantor’s proof. It will still be the case that in the formal system in which it’s defined, Cantor’s proof is valid, and the cardinality of the set of real numbers is larger than the cardinality of the set of natural numbers.
        
        Mathematical facts aren’t absolute facts: they’re facts within a formal system of reasoning. The only thing that will change the fact that in set theory, the cardinality of the real numbers is larger than the cardinality of the naturals is someone proving that axiomatic set theory is inconsistent.
        (And we’ve got some pretty solid proofs that it is consistent up to the limits of the formal reasoning itself.)
James R Meyer Jan 18, 2018 at 4:40 pm

Mark, You try to have it both ways.

On the one hand you claim that the diagonal proof must be stated within a valid formal framework. But on the other hand your claims are based on arguments outside of that framework.

Within such a formal system as you refer to, every statement in that system and the objects of that system have to be in the language of that formal system. And that means that in your diagonal proof in that system, every number, reference to a number, every enumeration function, every reference to an enumeration function, and every definition, including the definition of the diagonal number, must be in the language of that system.

And since you have at least some knowledge of Godel and incompleteness, you must know that you can also make statements outside of such a system regarding the statements of that system. But you refuse to allow anyone to consider the diagonal proof except as within your formal system.

Now, in such a formal system, you can of course obtain the result that there can be no enumeration of all real numbers within that system. But that does not prove the case where the enumeration is in a meta-language to the system. Either you can provide a proof that a diagonal number can be defined where the enumeration is in a meta-language to your formal system, or you cannot. I did reference this before and you said I was confused, and you didn’t address the content. But I’m not confused, and I haven’t forgotten. I already asked you for such a proof, but that was not forthcoming. And I suppose you won’t attempt to provide such a proof, since you insist on insisting that you will only consider working within your formal system.

Since that is the case, what you are able to prove is that there can be no enumeration of the reals within your formal system. That’s all.

Given only your in-system diagonal proof, you have no basis for asserting that there “exist” real numbers that have no finite definition. Attempts at such a proof (as in Konig 1905 Über die Grundlagen der Mengenlehre und das Kontinuumproblem) require the introduction of a meta-language. So, given your self-imposed restrictions, you can’t even attempt to prove that your notion of “more” applies in that sense.

But, of course, it is abundantly obvious that you are nevertheless claiming that you do have a proof that there “exist” real numbers that have no finite definition (both in this post and throughout your site) – and by so doing, you are stepping outside of the formal set theoretical framework that you espouse in such depth here.

As I said, you try to have it both ways.

I’m not falling for that deception, and neither should anyone else.
1. markcc Post author Jan 22, 2018 at 9:13 am
  
  Actually, no.
  
  The point of formal mathematics is that a proof is a purely mechanical exercise. In practice, we rarely achieve that level of perfect formality, but that’s the goal.
  
  The real point of logic is to mechanize proof. Given a set of axioms, and an interesting statement written symbolically, you should be able to perform the proof without any clue of what any of the axioms mean, or what any of the symbols in the statement to be proved mean. Logical proof is deliberately mechanistic, literally. The origin of the field that we call computer science started, largely, with mathematicians trying to build fully mechanistic proof systems.
  
  If a proof “depends on understanding”, what that really means is that it depends on some unstated assumptions. The hardest part of proofs comes from that: we find it very difficult to lay out every single assumption, and every logical inference that forms a proof.
James R Meyer Jan 19, 2018 at 1:44 pm

You see, Mark, in principle you and I seek the same thing.

Everything proven logically and without intuition and without unstated assumptions.
James R Meyer Jan 24, 2018 at 11:55 am

Mark, again you are trying to have it both ways.

As I have noted already, on the one hand you assert that you will only consider the diagonal proof in terms of within ZF set theory, but on the other hand, you assert a result that is not derived from a proof within ZF theory, or for that matter, from within any given formal system.

It seems to me that you only respond to comments that you find easy to answer; the more difficult ones you ignore and hope that no-one notices. I notice.

In your post of January 24, 2018 at 9:04, after I pointed out the above, you asserted that:
“Cantor’s proof …[shows] that given any possible mapping from the natural numbers to the reals, there will be real numbers that are omitted.”

Well, no, as I have already pointed out, if you are committed to a formal proof within a formal system, then you cannot prove anything regarding an enumeration of the reals that is defined outside that system, i.e., in a meta-language to that system, such as by a dictionary style listing of the symbol sequences of that system, without any regard to their meaning.
1. markcc Post author Jan 24, 2018 at 7:50 pm
  
  You just keep playing with weasel-words to evade things. There’s nothing particularly complicated here.
  
  It doesn’t matter how you define a supposed enumeration of the reals. All that matters is that it *is* an enumeration of the reals, and set theory defines what that means.
  
  If you’ve got something defined completely outside the bounds of ZF set theory and the real number theory that’s defined using that, you’re not talking about Cantor’s proof anymore. Cantor’s proof is a proof in the axioms of set theory and real number theory.
  
  You can play games all you want with systems that aren’t part of the world of set theory. As I’ve said numerous times, it can be an interesting and valuable thing to do. But when you do, you’re no longer doing set theory. Cantor’s proof applies within the realm of set theory. It’s very precisely defined in terms of the objects and entities that exist in that mathematical realm. It doesn’t pretend to apply to anything outside of that space. And that’s fine, because we all understand what that means.
  
  You can use nonsense terms like “meta-language to the system”, which is exactly the kind of informal term that I disdain. In terms of math, saying “meta-language” doesn’t mean anything unless you define it. But in terms of Cantor’s proof? It doesn’t matter.
  
  Cantor’s proof is a very simple construction. There are two key pieces to it.
  
  The first says that we’ve got a representation of every possible real number in terms of infinite sequences of digits. No matter how you generate them, every real number can be represented in terms of an infinite sequence of digits. Give me a real number, and I can find its representation.
  
  The second says, ok, you claim to have an enumeration of all of the real numbers. I’ll show you how to produce a real number that isn’t part of that enumeration.
  
  You can talk about undefined meta-systems all you want, but those two steps are still a fundamental barrier. Every real number can be represented as an infinite sequence of digits. And for every supposed enumeration of real numbers, I can produce a real number that isn’t in that enumeration.
  
  The only way around that is by playing a nonsense game with words: you can redefine “real number”, or you can redefine “enumeration”. But neither of those refutes Cantor. You can babble about “metasystems”, but when you get to the point of Cantor’s proof, either you have an enumeration, or you don’t. Either the values in it are real numbers, or they aren’t. Cantor’s proof doesn’t care how you generate the enumeration.
Dr James R Meyer Jan 25, 2018 at 4:42 am

Mark, this is not regarding the primary content of your last post, but there are things that have to be said regarding your misconceptions re meta-language. You said: “You can use nonsense terms like ‘meta-language to the system’, which is exactly the kind of informal term that I disdain. In terms of math, saying ‘meta-language’ doesn’t mean anything unless you define it.”

Mark, the notion of metamathematics/metalanguage has been well known and used in mathematics for at least 85 years. Gödel used metamathematics in his incompleteness proof (in fact you eulogise that proof, and you have said: “I’m absolutely fascinated by Kurt Gödel, and his incompleteness theorem. Incompleteness is, without a doubt, one of the most important, most profound, most surprising, and most world-changing discoveries in the history of mathematics.”).

So I’m afraid that both the facts and other things you have said contradict your assertion “saying ‘meta-language’ doesn’t mean anything unless you define it”. It might not mean much to you but that only indicates that you have not given that aspect of mathematics sufficient study. And your statement that “You can play games all you want with systems that aren’t part of the world of set theory” throws out a huge part of mathematics. In fact, if you want to talk about mathematics, rather than actually doing it, then you are doing metamathematics. In fact, nearly all of your blog site is metamathematics. That’s a fact. If you want to scrap all the metamathematics from your site and leave only pure formal set theoretical statements that’s fine by me. But if you don’t do that, then to tell others that they can’t talk about mathematics in the same metamathematical way that you do is sheer hypocrisy.

By the way, you previously said: “the real numbers means something very specific: it’s the unique complete totally ordered field …”

Sorry, Mark, that’s not set theory, the definition of such fields is in a meta-language to set theory. It would be a classic blunder of logical inference to suppose that because certain sets of ZF theory satisfy the definition of a complete ordered field, then that must mean that everything that satisfies the definition of a complete ordered field is a ZF set. There can be many different kinds of formal systems whose entities satisfy the field definition.

You have the gall to speak disparagingly of “playing a nonsense game with words and babbling about ‘metasystems’ “, yet you hop in and out of set theory to define real numbers, while at the same time insisting that you are only prepared to consider what can be said within set theory.

If you had apportioned more study to metalanguage and metamathematics, instead of rubbishing them, perhaps you would not have made such an elementary error.
1. markcc Post author Jan 25, 2018 at 9:37 am
  
  I’m not objecting to the concept of metalanguage: I’m objecting to the way that you’re using it.
  
  Like so many other things in math, there’s a way of precisely defining metasystems. That doesn’t mean that every use of the word “metasystem” is meaningful. For one prominent example, Chris Langan likes to talk about metasystems in his CTMU, but he never bothers to define what a metasystem is.
  
  The reason that I keep saying you’re playing a nonsense game is because you keep insisting on things that you don’t define.
  
  You keep trying to play a game where, by using imprecise language, you try to weasel concepts from outside the realm of set theory and the theory of real numbers defined using set theory without defining them in the language of set theory.
  
  And that’s a big deal. A mathematical theory require mathematical definitions. To use a concept in a proof, that concept needs to be defined in the same system as the proof.
  
  The brilliance of what Gödel did is that he took the entire system of set theory and first-order predicate logic, and figured out how to express it within the framework of axiomatic set theory and Peano arithmetic. He didn’t rely on anything that didn’t work in AST&PA. His proof is completely honest and clear about the fact that what he’s doing relies on that framework. He didn’t create some undefined “metasystem” and then insist that it was allowed to do things that couldn’t be specified in ZFC&PA. Gödel’s metasystem doesn’t change anything about the basic mathematical framework it exists in. In fact, it’s entire point is that it shows that you can take any logical system that’s valid and consistent under ZFT+PA, and express it entirely in terms of primitive recursive (as defined in ZFC+PA) arithmetic computations (as defined in ZFC+PA).
  
  The problem with your metasystem talk is:
  
  (1) you never define what you mean by a “metasystem”. It could be anything from an arithmetic construction like Gödel, or a bunch of hand-wavy nonsense. Since you never bother to define it, the reasonable assumption is that it’s the latter.
  
  (2) you argue that because some unspecified metasystem that goes beyond ZFC + real numbers can produce something that violates Cantor’s proof, Cantor’s proof must be wrong. That’s not how mathematics works. Under any mathematical system, there will always be constructs from different mathematical systems that don’t make sense. I can write proofs about the surreal numbers, which are a strict superset of the reals, but those proofs may not be valid when spliced into real number theory, because they rely on concepts and constructs that don’t exist in RNT.
  
  (3) Cantor’s proof doesn’t depend on how an enumeration of the reals is generated. It can be any magical metasystem you want: at the end of the day, if it’s a refutation to Cantor’s proof, then it needs to produce an enumeration of real numbers, and that enumeration needs to be the thing that set theory means by the term “enumeration”. If it produces an enumeration as defined in axiomatic set theory, then Cantor’s proof applies, and shows how to construct a counterexample. If it’s not an enumeration as defined in axiomatic set theory, then it’s meaningless to talk about it with respect to Cantor’s proof, because Cantor’s proof is specific to the set theoretic notion of an enumeration.
  
  You want to have it both ways: you want to say that you’re refuting Cantor’s proof, but at the same time, you want to have the ability to play with concepts and constructs that have nothing to do with what Cantor’s proof talks about. And you want to say that that’s a justifiable thing to do, because you have a “metasystem” that you never bother to define.
  
  Honestly, at this point, I’ve had enough of this – we’re just going in circles. If you’re right, you’re wasting your time arguing with a petty nobody of a computer scientist; just write a paper, and go get it published, and take home your Field’s medal.
Dr James R Meyer Jan 25, 2018 at 4:44 am

Regarding the main subject matter of your last post (January 24, 2018 at 7:50 pm)

You state: “…every real number can be represented in terms of an infinite sequence of digits. Give me a real number, and I can find its representation.” And later, “Every real number can be represented as an infinite sequence of digits.”

That’s a common fallacy. But I’ll make it easy for you to try to prove me wrong. Just give me the representation of any irrational as an infinite sequence of digits. Do that and I’ll concede.

But of course you can’t. But what you can say is that given any valid definition of a real number, you can generate the digits of its expansion in any given base to as many digits as you want – but you can’t generate them all.

Note that in Cantor’s original diagonal paper of 1891, he writes the entities of an assumed enumeration as:
Suppose we have:
E1 = ( a1,1, a1,2, …, a1,ν, … ), E2 = ( a2,1, a2,2, …, a2,ν, … ), …
but of course that isn’t the way you will do it within your formal set theory.

No, in your formal proof, you refer to a real number as a particular type of set (because all entities within your set theory are sets). So any enumeration within set theory is an enumeration of sets, for example, as a set of ordered pairs of sets.

So, within your formal set theory, to refer to sets in general, you need variables whose domain is sets. Fine. No problem. So you go through your proof and you obtain a result something like this:
For all sets of ordered pairs {A, B}, where A is set that satisfies a certain definition (for natural numbers) and B is a set that satisfies a certain definition (such as real numbers), there does not exist a set of ordered pairs {A, B} such that the ordered pairs include every B. (Note that this is not prescriptive, it’s an informal description of the type of result you might get. Sorry, but that is the nature of metamathematics.)

So, within set theory, you can have a result that states there is no enumeration of sets of a certain type within that theory. In case you imagine that I have a problem with that – I don’t. It’s the additional informal nonsense that is assumed to follow from that which I object to.

I note that you say you hate that sort of informal nonsense too.

Now, given such a result of set theory, please tell me (and the rest of the world) how you obtain from that – WITHIN set theory – your assertion that there exist sets (that represent real numbers) but which have no finite representation.

You see, from a set theoretical result, the only information is that there are always some type B sets that, regardless of whatever enumeration, are missing from that enumeration. That doesn’t tell me that there exist sets that have no finite representation.

You often respond to comments by saying about something that it can’t be said/done within set theory. Well, I’m saying that now about your claim that there exist sets that have no finite representation.

You say that I am the one that is “playing with weasel-words to evade things”. But while you keep asserting that there exist sets that have no finite representation, you have yet to say how that might be proved within set theory. After all, this page is about “why we need formality in mathematics”. Exactly!

So please tell me, I’m dying to know, how you think that it can be proved within set theory that there exist sets that have no finite representation. No need for evasion or weasel words. Just a straightforward explanation will do.
1. markcc Post author Jan 25, 2018 at 9:13 am
  
  Once again, what you’re doing is rejecting things that are fundamental parts of set theory.
  
  By the argument that you’re making, Cantor’s proof fails far earlier: you’re arguing, in essence, that it’s impossible to specify the decimal expansion of an infinite real – so Cantor’ proof can’t ever produce a number, because it’s got a non-terminating, infinite representation.
  
  But mathematically, that’s not a problem. The definition of how we represent numbers, the definition that we use to talk about the representation of a number – that doesn’t rely on termination. It relies on specification, using the axioms of infinity and induction.
  
  So again: your problem isn’t with Cantor’s proof. You’re continuing to object the set-theoretic conclusion of a set theoretic proof, on the basis that you don’t like the underlying axioms of set theory.
  
  Fine. As I keep saying: if you think that set theoretic math is wrong, you’re welcome to choose a different framework. You can build a different mathematical foundation, which doesn’t include anything like the axiom of infinity, or which has an axiom of induction which doesn’t allow induction over infinite sets. There are many different ways of doing that. But when you do that, you’re not refuting Cantor’s proof. Cantor’s proof is still correct within the framework of set theory.
  
  Finally: how can I prove that there are sets without finite representation in set theory? Very easily: it’s a fundamental part of the basic axioms of set theory. In the ZFC construction, the axiom of infinity gives me an initial infinite set; the axiom of powerset gives me the ability to create a non-enumerable infinite set from the initial infinite set provided by the axiom of infinity; the axiom of specification allows me to define a wide range of infinite sets, both enumerable and non-enumerable. And from those, I can then directly move to defining the set of natural numbers; then using the set of natural numbers, I can construct the set of rational numbers; and then using the set of rational numbers, I can create the real numbers; and then using the set of real numbers, I can perform Cantor’s proof.
  
  As I keep saying: you’re trying to take an intuition about infinity, transplant it into a proof based on set theory, and then demand that there’s a problem with that proof because it doesn’t match your intuition.
  
  It’s fine to reject axiomatic set theory. There are great mathematicians who have done that. But you have to admit that that’s what you’re doing.
  1. Dr James R Meyer Jan 26, 2018 at 4:58 am
    
    Mark, if you are going to totally misrepresent what I said, that’s up to you. But any intelligent person reading these comments will see through that misrepresentation. It seems to me that instead of actually addressing what I am saying, you are attacking a collective caricature of various people who have frequented your site – a straw man of your own creation.
    
    But of course, it’s all an attempt at a diversion from the key point that you keep evading.
    
    I said that if you want to confine everything to within set theory, that’s all right by me. And all I asked for – a simple request – is a sufficiently formal proof within that set theory that there exist real numbers that have no finite representation.
    
    In response, all you did was provide one paragraph about how easy it would be “prove that there are sets without finite representation in set theory”, but what you actually did was talk about how easy it would be to prove that there is no enumeration of sets such as the real numbers in that set theory – but I’m not disputing that.
    
    So, I ask again, please provide a proof within set theory that there exist real numbers that have no finite representation.
    1. markcc Post author Jan 26, 2018 at 9:36 am
      
      Before I get to anything else, let me point out again the Gish gallop that you’re pulling here.
      
      Look at your last comment. The entire thing never mentions the supposed problem about real numbers with no finite representation. Instead, it goes off into a long nonsense discussion about how you don’t need to actually have a 1:1 mapping between two sets to show that they’ve got the same cardinality, based on a really silly mangling of the Shroder-Bernstein theorem. So when I respond to that, suddenly, you’re talking about something else entirely.
      
      See, you’re continuing to play the same game. You refuse to define terms in a precise way, which gives you an easy out. You switch topics whenever you’re caught out on a mistake. And as you demand formality from me, you continue to refuse to define anything in a formal way. What do you mean by real numbers that have no finite representation? That’s one of those informal terms that sounds nice, but could mean several different things. Does it mean a number with no finite decimal expansion? Does it mean a number with no computable representation? Does it mean a number with no finite logical specification? Does it mean something else entirely? I can answer your supposed challenge in many ways – but no matter which one I choose, you’ve left yourself room to sneer, insult me some more, and say that I’m not answering your question.
      
      For example, I can pull out one of my favorite family of infinite, transcendental, non-computable numbers: Chaitin’s Ωs. It takes quite a bit of mechanical reasoning, but an Ω is a number that for a particular recursive system (a formal mathematical abstraction of a computing device) encodes halting probabilities of programs under that computing system. Fully defining a recursive system is complicated and well beyond the scope of a comment on a blog (but if you care, there are numerous textbooks that work through the complete definition!) but it is a well-defined formal system built on the base of ZF set theory and first order predicate logic.
      
      Given an effective computing system, we can model it as a function φ. φ operates on one parameter, which is a program that will be executed by φ. The size of the program |p| is the length of the program in bits.
      
      Given this, we can define Ω_Φ as:
      
      $Omega_phi = \Sigma_{p: p \, \text{halts}} 2^{|p|}$
      
      That definition is valid under ZFC set theory, using the standard construction of recursive systems. It uniquely defines a specific number. That number cannot be computed – only approximations of it, and even those can be immensely problematical to actually compute. If we knew the value of Ω_Φ, we’d be able to construct a perfect (if ludicrously slow) halting oracle.
      
      Of course, you can easily weasel out: you can say that I just wrote the definition of the number in a finite form right up there in that equation. Or you can say that that doesn’t really define the number because I can’t tell you its digits. Or you can say that it doesn’t count, because I’m bringing in recursive function theory, which isn’t set theory.
      
      This is what I mean about this being a waste of time. You just keep flinging words, changing the subject, and playing definitional games. There’s no way that you’ll ever admit that you’re wrong.
      
      But as I said before: if you really believe you’re right about this, it’s incredibly foolish to sit around and argue it on a blog. I’m not a mathematician. I’m just a lowly software engineer with a math fetish. If you’re right, if you can actually refute Cantor’s proof, then you’re a world-class mathematician who’s in a position to overturn the entire history of 20th and 21st century mathematics. If you genuinely believe this, you should be working to get your proof published, not wasting time arguing with some twit on a blog. If you really believe you’re right, you’re in a position to take home the field medal, take a faculty position in the university of your choice, and go down in history as one of the greatest mathematicians of all time. So what are you doing here?
Dr James R Meyer Jan 26, 2018 at 11:16 am

Mark, you seem to be conflating my comments with those of a certain Carl, and ascribing things to me that should be ascribed to Carl.

Anyway, you ask me:
“What do you mean by real numbers that have no finite representation?”

You ask me now? After saying in a previous comment you said it was very easy to “prove that there are sets without finite representation in set theory”? And also you have described and explained it several times on your blog (do a Google advanced site search for the phrase “finite representation”).

And now you ask what it means? Is that intended as a joke?

For the umpteenth time, you have said you will only discuss the diagonal proof in terms of set theory. And for the umpteenth time I am asking you for a proof within that set theory that there exist real numbers which have no finite representation.

Just leave out the irrelevant stuff like Chaitin’s number, Fields medals, your pleas of, “I’m not a mathematician. I’m just a lowly software engineer” that contradict your claim that you know good math from bad math, and so on, and so on – and just provide that proof you said it was very easy to prove.
1. markcc Post author Jan 26, 2018 at 12:58 pm
  
  My apologies for confusing names. I’ll try to keep that straight.
  
  As I said, the phrase “finite representation” is an informal term, which could be assigned to many different meanings. I gave you some examples of what it could mean, and yet, still, you refuse to bother to actually provide a definition. Why?
  
  Which one?
  (1) A number has an infinite representation if its decimal (or binary if you prefer) expansion has an infinite number of digits.
  (2) A number has an infinite representation if its expansion in every integral number base has an infinite number of digits.
  (3) A number has an infinite representation if its expansion in every integral number base has a non-terminating, non-repeating sequence of digits?
  (4) A number has an infinite representation if there is no finite-length program in a recursive computing system that produces its digits.
  (5) A number has an infinite representation there is no way of uniquely identifying the number in a finite amount of space.
  
  You call Chaitin’s number nonsense. Why? It’s an example of a number which (under several possible definitions – 1, 2, 3, and 4 above!) has no finite representation, which therefore proves that there are real numbers in set theory with no finite representation. But you reject it, out of hand, sneering that it’s irrelevant, but without bothering to state *why* you’re rejecting it.
  
  That’s the problem with not having a formal definition. There’s no way for me to actually do what you claim to be asking for. Like I keep saying: the game you’re playing is based on keeping everything fuzzy enough that you can’t be refuted. I’ve given you an example of a number with no finite representation – but you’ve rejected it without explanation. You’ve refused to define your terms no matter how many times I ask, and you reject examples of the things you’re asking for, on the basis that they clearly and obviously don’t meet the requirements of the definition you refuse to share.
  
  So gosh, why would I say that you’re not arguing honestly?
  1. Dr James R Meyer Jan 26, 2018 at 3:44 pm
    
    It’s a common trick to pretend that you don’t know what someone means and to keep asking for definitions ad nauseum. We could both play that game, I could say that you referred to say, “effective computing system” without first defining it, etc, etc, but I’m not interested in infantile games like that.
    
    Two of Mark’s definitions:
    http://www.goodmath.org/blog/2009/05/15/you-cant-write-that-number-in-fact-you-cant-write-most-numbers/
    http://www.goodmath.org/blog/2014/05/26/you-cant-even-describe-most-numbers/
    
    Mine: A real number having a finite representation;
    There is a definition in a given formal system that can be written down with a finite number of symbols, and which precisely defines the entire expansion of that number (to a given base).
    A real number not having a finite representation;
    There is no definition in any formal system that can be written down with a finite number of symbols, and which precisely defines the entire expansion of that number (to a given base).
    
    Why is Chaitin’s number irrelevant? Several reasons, here’s two.
    1) because for the umpteenth +1 time, I asked for a proof there exists real numbers with no finite representation within ZF set theory. You simply assert that Chaitin’s number can be defined within ZF and expect everyone to simply take your word for it. I don’t. The only entities in ZF are sets; Chaitin’s number is defined in terms of Turing machines that stop or don’t stop. But you provide no reason why I should believe that ZF can refer totally WITHIN itself to Turing machines stopping or not stopping.
    2) According to you, Chaitin’s number “exists” without any finite representation, but the only evidence you provide for that is Chaitin’s definition, which is such that the number cannot be completely derived from that definition, since it is defined in terms of halting probability. From that you conclude there cannot be any finite representation, since that would solve the halting problem. But that does not mean that there cannot be an alternative finite definition of the number, and which makes no reference to halting probability. Since you haven’t yet proven that there is any real number that has no finite representation, then you cannot assume that there is no such finite definition. So one such finite definition can be the definition of the same decimal expansion as Chaitin’s number, but you have no way of proving that it is Chaitin’s number, since you can’t deduce the digits of
    Chaitin’s number indefinitely, but you could for the alternative definition – and so you still can’t solve the halting problem. So you still haven’t proved that there exists a real number that has no finite representation.
    1. markcc Post author Jan 26, 2018 at 5:00 pm
      
      Want to know the difference? Because you can look up effective computing systems (or recursive computing systems), and find the definition. You can read a dozen different textbooks, and completely understand exactly what I mean, and what Chaitin’s constant means. As I explained clearly and in detail: the phrase “infinite representation” can have multiple meanings, and I carefully gave you a list of options. (Which, I will note, you ignored and gave your own, less precise definition.)
      
      Chaitin’s Ω can absolutely be determined from that definition. Once again, you’re not understanding a mathematical definition. Chaitin’s Ω defines a halting probability; it isn’t defined by a halting probability. It’s defined by a simple fact: given a computing system Φ and a program p, does p halt?
      
      Of course, you’ve got a convenient way to wiggle out of that. I give you a number which meets your requirements. But you sneer and say it doesn’t count, because I’m only allowed to use pure ZF, which consists of nothing but sets. But that kind of weaseling gives you a universal out. Real numbers aren’t part of pure ZF – they’re part of a construction on top of it. The concept of a decimal expansion isn’t part of pure ZF. Anything I can produce will, necessarily, depend on constructions built on top of ZF.
      
      I can’t talk about real numbers in pure ZFC set theory, because real numbers aren’t a concept there. Real numbers are part of a mathematical theory constructed using ZFC set theory. I can talk about them using set theory, because the theory of real numbers is built using ZFC as a foundation. The real numbers are a set – and I can prove that using ZFC, but not only ZFC.
      
      To meaningfully define the real numbers, I need to start by defining the natural numbers. I can do that by defining their mathematical properties using the axioms of Peano arithmetic written in first order predicate logic, and then I can show that there is a model for that theory in sets using ZFC. Once I’ve done that, I can use all of the axioms of ZFC to construct sets of natural numbers and do proofs over those sets using the axioms of infinity, comprehension, and induction. That gives me a valid ZFC-backed theory of the natural numbers. Once I’ve done that, I can construct a theory of integers using a set of axioms, and show that there’s a model for that theory using ZFC and sets of natural numbers. Once I’ve done that, I can built sets and proofs about those sets using the axioms of ZFC like comprehension, infinity, and induction. Then I’ve got a valid ZFC-based theory of the integers. I can then define the rational numbers using a series of axioms, and show that there’s a model for those using ZFC and sets of integers. That gives me a valid ZFC-based theory of the rational numbers. Then I can define a set of axioms defining the real numbers, and show that there’s a valid model for those using ZFC and sets of rational numbers. That gives me the theory of the real numbers.
      
      I need all of that construction before I can really talk about the set of the real numbers. That doesn’t get to the necessary background that’s needed to talk about decimal representations and digit expansions.
      
      The thing is, this is what math is about. It’s about building stacks of intricate and carefully defined structures. You start from a very simple base, and build the world on top of it.
      
      ZFC isn’t a great theory because it includes everything. It’s a great theory because it provides a platform and a set of building blocks that you can use to construct almost anything.
      
      As I said in the previous post: I can define recursive function theory, but it’s not something that can be defined in a blog post. It’s something that requires a textbook. Likewise for just about any interesting thing. I can’t define a transcendental number in pure set theory. I can’t define π in pure set theory, because numbers don’t exist in pure set theory. But I can build numbers using set theory.
      
      I can define Chaitin’s numbers, because I have set theory as a foundation. I can use set theory to define natural number theory, and then natural number theory to define recursion function theory. First order predicate logic defines the rules, and set theory provides the model. That gives me the objects I need to talk about computation. Using set theory, I can define objects and sets using ZFC axioms. Look at the definition of Ω: it’s a valid set theoretic construction, built on the axioms of comprehension, infinity, and induction, operating over the objects of recursive function theory.
Dr James R Meyer Jan 28, 2018 at 4:10 am

Mark, re your comment of January 26, 2018 at 5:00 pm

I never used the term “infinite representation”. That is why I did not define it, and why I ignored your definitions of it. The term I actually used was “finite representation”, whose meaning is perfectly clear to you, as used in your blogs
http://www.goodmath.org/blog/2009/05/15/you-cant-write-that-number-in-fact-you-cant-write-most-numbers/ and
http://www.goodmath.org/blog/2014/05/26/you-cant-even-describe-most-numbers/

You say:
“Chaitin’s Ω can absolutely be determined from that definition.”

No, it can’t. But there can be an assumptive notion that the Chaitin number “exists” if one takes together both that definition and the assumption that for any Turing machine/program, there “exists” a Platonist “true” or “false” value for whether it halts, and which is completely independent of whether there exists any finite method that can determine if that Turing machine/program halts. That is very different to asserting that the Chaitin definition of itself is sufficient to determine a specific number – the definition itself without that assumption does not give a determination of any specific number.

Let’s pretend for a moment that your argument that Chaitin’s number does actually provide an example of a real number that has no finite representation. Then your “proof” that there “exists” a real number for which there is no finite definition that can determine its value relies on the assumption that there “exists” “true” and “false” values for which there are no finite definitions that can determine such values. Don’t complain if anyone rejects that argument on the grounds that it is absurdly circular.

But, anyway, I don’t need to point out the circularity of the argument. I only need to reiterate the point of my previous comment that you simply ignored. Just because you have an assumption together with Chaitin’s definition that gives you an assumed number R that you cannot determine by any finite method, that does not mean that there is no alternative finite definition B that gives that assumed number R, where the definition B makes no mention of Turing machines or computer programs. Knowing the definition B does not enable you to solve the halting problem, since there is no method of determining if any given definition (including B) is a definition that gives the assumed number R. Hence there is no proof that R does not have a finite representation.

It’s nice to see that at last you admit that, actually, it’s better to use all sorts of other stuff besides ZF set theory to do all sorts of math.
1. markcc Post author Jan 28, 2018 at 2:04 pm
  
  Your problem in this entire discussion is that you don’t understand any of the things that you’re talking about.
  
  You specifically challenged me to, using ZFC set theory, prove that there exists a real number with no finite representation.
  
  I did that.
  
  You’re now quibbling with an objection that amounts to “I don’t know what it means to define something in ZFC set theory”.
  
  I’m going to repeat this one last time.
  
  The whole argument of the post that started this reply thread is: in mathematics, we use formal notation, formal language, and formal reasoning for a reason: because that kind of precision is crucial to doing math.
  
  ZFC is a foundation on which we define other theories of math. It’s a key part of all of modern mathematics. It’s not all of math: it’s the foundation of all of math.
  
  You challenged me to produce a number with no finite representation using ZFC set theory.
  
  How does a mathematician define something like a number with no specific representation?
  
  They provide a set-theoretic definition that precisely specifies the number they’re talking about.
  
  How do they know that the thing they defined actually exists? Because they define it in ways that are valid within the foundational axioms of the system of mathematics.
  
  How did I define Chaitin’s Ω?
  
  I started by talking about a recursive (or effective) computing system. That’s a construct well-defined using the foundation of set theory.
  
  Then I defined a set of values: . Halting is a concept defined in the theory of computation. It’s a predicate. Using simple ZFC, I can define a set using a predicate, according to the axiom of specification. That set – is absolutely a valid, well-defined set under ZFC set theory. And an expression that sums over the elements of a set of integers? Absolutely valid under ZFC set theory.
  
  But you’re playing a game by trying to add new rules – new rules which you neither stated nor defined. Under ZFC set theory, Chaitin’s number exists. Mathematically, Chaitin’s number exists.
  
  Your argument against it is:
  
  But there can be an assumptive notion that the Chaitin number “exists” if one takes together both that definition and the assumption that for any Turing machine/program, there “exists” a Platonist “true” or “false” value for whether it halts, and which is completely independent of whether there exists any finite method that can determine if that Turing machine/program halts. That is very different to asserting that the Chaitin definition of itself is sufficient to determine a specific number – the definition itself without that assumption does not give a determination of any specific number.
  
  But the whole point of formal mathematics is that it defines exactly what you can and can’t do: whot, under a given set of definitions, exists; what, under a given set of definitions is provable.
  
  We’re talking in terms of the mathematics based on ZFC set theory. What defines whether or not something exists is the axioms of ZFC, and the constructs that we build using those axioms. The whole point of that formalism is to address exactly this argument: there’s no room for opinion here. The mathematical foundations and the mathematical reasoning process tell us exactly what we need to know, without a scrap of ambiguity. If we’re talking about mathematics? Chaitin’s number exists.
  
  And one last quibble:
  
  It’s nice to see that at last you admit that, actually, it’s better to use all sorts of other stuff besides ZF set theory to do all sorts of math.
  
  I don’t admit anything remotely like “It’s better to use all sorts of other stuff besides ZF set theory”. What I said in that previous comment, which you’re trying to twist here, is that ZFC is the toolbox that we use to built all of the theories of mathematics that we use every day. ZFC isn’t all of mathematics: it’s the foundation that pretty much all of modern mathematics is built on. When I’m doing number theory, I haven’t stopped doing ZFC: I’m working in a theory who’s model and underpinnings are defined with ZFC. ZFC is still a fundamental part of it.
  
  When I’m doing the theory of computation, whether I’m doing it via the mechanistic version, or via recursion function theory, I haven’t stopped doing ZFC set theory. I’m still working in a theory that’s built using ZFC as a foundation, and I’m still using ZFC every step of the way.
  
  I’m not doing something besides ZFC. I’m doing something built with ZFC.
  1. Dr James R Meyer Jan 29, 2018 at 8:29 am
    
    Mark, you say of me: “Your problem in this entire discussion is that you don’t understand any of the things that you’re talking about.””
    
    When you have to resort to hyperbole, an intelligent reader knows that it doesn’t actually make any useful contribution to the debate, and can see that the notion that I don’t understand any of what I’m talking about is ridiculous.
    
    You seem to think that formal systems cannot include any assumptions. But of course they can, in fact they must, otherwise there could be no formal axioms. And of course that means that there isn’t any way of proving that the axioms of your formal systems are indubitably “correct”.
    
    You keep banging on about your chosen formal systems as if your chosen formal systems are the only possible “correct” formal systems, saying: “there is no room for opinion”. But you can’t prove that the axioms of your chosen formal systems are the “right” ones – and so there is no reason why anyone should accept your formal axioms as the “right” ones – and hence there is no reason to accept your chosen formal systems as the “right” ones. You can say that I don’t understand anything of what I’m talking about – but the evidence of who understands what they are taking about lie within the words on this page.
    
    You started off by insisting on ZF set theory. Fine. But now you are talking about all sorts of other stuff and simply asserting that it can all be formalised. But doing that isn’t really any different to talking informally, because now no-one can be sure what assumptive axioms and rules of inference you would be using if it was all put in strict formal terms.
    
    Of course you can use your chosen formal systems and obtain the results you desire. And we can accept that you will include whatever assumptions you make as axioms of your formal systems. But that does not mean that we have to accept those axiomatic assumptions as some sort of gospel that may not be challenged. And it does not mean that we have accept those axiomatic assumptions if they lead to a circular argument. Accepting Platonist assumptions that are assumptions of the “existence” of mathematical entities independently of any finite definition is akin to a faith based belief in a deity – as is assuming that all propositions have a definite “true” or “false” value independent of any means of determining such values.
    
    But the above presumes that your claim is correct – that your formal systems can “prove” the “existence” of a number that has no finite representation. But the fact is that all that a formal system can prove is that the symbol sequences that is Chaitin’s definition – i.e., that the finite representation of Chaitin’s definition in that formal system satisfies the formal requirements in that formal system for “existence” – that is, that it satisfies the definition of a real number in that system.
    
    You are asking me to accept that you can have a formal system that can say, in effect, where Omega is Chaitin’s definition in that system:
    “Omega is a real number, and there exists no y such that y = Omega, where y is a finite symbol sequence for a real number (in this system).”
    
    But that would be absurd, since Omega is a symbol sequence of that system. The idea that a formal system can say something about the “existence” of a number that “exists” outside of that formal system is absurd. Of course, people can attach interpretations onto the statements of formal systems, but here we are dismissing such interpretations, since this page is about why formality is important in maths.
    
    Finally, you brazenly claim that you have proved that there exists a real number with no finite representation. But you haven’t, and you completely ignored the key point that I have already pointed out twice – which is that the definition of Chaitin’s number does not prove that there does not exist an alternative definition of that number that makes no reference to Turing machines/programs, and hence cannot be used to solve the halting problem, since there is no way of identifying that number as the Chaitin number.
    
    You didn’t even refer to either instance of the two times I made that argument, so the presumption must be that you do not find any flaw in that argument.
    1. markcc Post author Jan 29, 2018 at 9:07 am
      
      Gallop, gallop, gallop. As I said, I’m done with this. You’re welcome to run off and declare victory. Goodbye.

For a look at another aspect of Chu-Carroll’s pronouncements, see the page Good Math, Bad Math? which shows how Chu-Carroll fudges his explanation of Gödel’s proof of incompleteness.

The Need for Formality in Mathematics

Other Posts

The Lighter Side

Recently added

A new section on set theory

How to setup Dark mode for a web-site

Decreasing intervals, limits, infinity and Lebesgue measure

Easy Footnotes

New section added to paper on Gödel’s flawed paper

Cantor’s Grundlagen and associated papers

A brief history of meta-mathematics

Comments

Printer Friendly