Wikipedia:Reference desk/Archives/Mathematics/2022 January 14

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 14

How to prove that Chaitin constant is a normal number?

Chaitin constant is known to be a normal number, but I do not think it is easy to prove, since some “easier” numbers, such as Pi, e, and the square root of 2, are not known to be normal number or not, so how to prove that Chaitin constant is normal number? ——118.170.50.5 (talk) 09:37, 14 January 2022 (UTC)

Every Martin-Löf random number is normal, so the problem can be reduced to proving the (stronger) property that any halting probability is Martin-Löf random. According to the references provided in the article, this is Theorem 6.1.3 in: R. Downey and D. Hirschfeldt (2010), Algorithmic Randomness and Complexity, Springer-Verlag.  --Lambiam 13:38, 14 January 2022 (UTC)

Okay, another question, is every uncomputable number normal? ——2402:7500:917:30C4:54AA:108F:3ECB:103F (talk) 13:41, 14 January 2022 (UTC)

No. Take any uncomputable number, x, and make a new number whose digits alternate between the digits of x and 1's. The new number is still uncomputable, and definitely not normal. Danstronger (talk) 14:08, 14 January 2022 (UTC) (For another proof, there are countably infinite computable numbers but uncountable non-normal numbers. Danstronger (talk) 14:11, 14 January 2022 (UTC))

@Danstronger: Is the set of normal numbers also uncountable? ——2402:7500:917:30C4:54AA:108F:3ECB:103F (talk) 14:17, 14 January 2022 (UTC)

Yes. One way to see this would be to construct a normal "version" of any real number, for example by putting increasingly many copies of 1234567890 into the digits. E.g. for pi, 3.1415... becomes 3.123456789011234567890123456789041234567890123456789012345678901... Danstronger (talk) 14:33, 14 January 2022 (UTC)

Continuum hypothesis is true.

Since this conjecture (the continuum hypothesis) is "a conjecture which can be disproved using a counterexample", if this conjecture is in fact false, we can use this counterexample to disprove it, thus the conjecture is decidable, and if the conjecture is undecidable, then it must be true, thus, if we can prove that this conjecture is undecidable, then we can prove that this conjecture is true, which is a contradiction, like Goldbach conjecture (a counterexample is an even number ≥4 which cannot be written as sum of two primes), Fermat last theorem (a counterexample is an integer n≥3 and positive integers x, y, z such that xⁿ + yⁿ = zⁿ), Riemann hypothesis (a counterexample is a complex number z such that Re(z) ≠ 0, Im(z) ≠ 1/2, but ζ(z) = 0), and four color theorem (a counterexample is a graph which cannot be drawn using ≤4 colors), a counterexample of continuum hypothesis is a subset S of R such that Card(S) > Card(N) and Card(S) < Card(R). ——118.170.50.5 (talk) 10:01, 14 January 2022 (UTC)

• Your reasoning is faulty. Here are the steps:

1. The CH, a conjecture of the form "all sets have some property", is proven to be undecidable (in ZFC).
2. Therefore, no counterexample (a set with a cardinality contradicting the CH) can be proven to exist (in ZFC).
3. Therefore, no counterexample exists (in ZFC).
4. Therefore, the CH is true.

The jump from 2 to 3 is incorrect. You could posit the existence of a counterexample (and then study its properties), or posit that no counterexample exists (and then study the consequences of that axiom on other properties of other objects). That is precisely what "undecidable" means. Tigraan^{Click here for my talk page ("private" contact)} 14:43, 14 January 2022 (UTC)

This is just like the Fermat last theorem, no counterexample (xⁿ + yⁿ = zⁿ, n≥3 is integer and x, y, z are positive integers) can be proven to exist ——> no counterexample (xⁿ + yⁿ = zⁿ, n≥3 is integer and x, y, z are positive integers) exists. ——49.217.65.248 (talk) 14:53, 14 January 2022 (UTC)

No. The Fermat last theorem has been proven, that is, it has been proven that no counterexample exists. For the CH, it has been proven that no counterexample can be proven to exist (again: in ZFC), which is a different thing. The Riemann hypothesis, the Goldbach conjecture, the Collatz conjecture etc. are all problems that have not been proven undecidable (so far at least). Tigraan^{Click here for my talk page ("private" contact)} 16:48, 14 January 2022 (UTC)

If the Goldbach conjecture has a counterexample, it is provably false. This is also plausibly the case for the Riemann hypothesis. For the Collatz conjecture it is conceivable that some trajectory appears to grow without bound as far as we can test using the most powerful supercomputers and thus remains a candidate counterexample, yet defies all attempts to prove it will not eventually collapse.  --Lambiam 19:07, 14 January 2022 (UTC)

To expand on Lambiam's and Tigraan's remarks, it is possible (in the sense that we haven't refuted the possibility) that Goldbach is independent of (say) ZFC please please please, not "undecidable"; that's a sharply inferior usage here. It is possible that it is independent of ZFC but provable in some stronger theory (say, ZFC+"there exists a measurable cardinal), and it could even be provable in the stronger theory that Goldbach is independent of ZFC. However, if Goldbach is independent of ZFC, then Goldbach is true. --Trovatore (talk) 19:35, 14 January 2022 (UTC)

• Tigraan's argument is correct. It's maybe easier to see if we move from the CH to a simpler example, the existence of inadmissibleinaccessible cardinals. ZFC can't prove they exist, but the cumulative hierarchy, the standard model which ZFC is intended to elaborate does entail their existence: you're not supposed to 'stop' at $V_{2\omega }$. No serious set theorist identifies the theorems of ZFC with the truths of set theory. — Charles Stewart (talk) 17:09, 15 January 2022 (UTC)

  I'm not familiar with "inadmissible cardinals". Did you mean inaccessible cardinals?

  By the way, according to standard conventions for ordinal arithmetic, I think you meant $\omega \cdot 2$ rather than $2\omega$. To be honest I'm not sure why the convention is that way, but it is. I seem to recall that Cantor originally used the convention that would refer to it as $2\omega$, and it got changed somewhere along the lines, for reasons that are not clear to me. The previous convention seems more intuitive. --Trovatore (talk) 22:40, 15 January 2022 (UTC)

• Yes, I did mean inaccessibles. My impression is that set theorists since von Neumann tend to prefer the asymmetric description of ordinals because it is has a simpler definition; proof theorists since Gerhard Gentzen tend to prefer the symmetric description because they favour more abstract ordinal notation systems. — Charles Stewart (talk) 14:54, 16 January 2022 (UTC)

  Hmm. I don't think it's a difference between subfields. I did take a course on proof-theoretic ordinal analysis in grad school. I feel I would have noticed if they had reversed the multiplication convention.

  I also don't really follow how one definition is more "abstract" or more "symmetric" than the other, or "simpler" than the other. It seems to me they're just the same, and it's just a question of which coordinate moves faster when you scan the Cartesian product, or equivalently whether you prefer to impose left-distributivity, as in the standard convention, or right-distributivity, as in the (older?) alternative one.

  To me, though, the standard convention seems like the poorer choice, for a couple reasons:

  1. When I see $x+x$, I shorten it as $2x$, not $x\cdot 2$. It's kind of natural to want to do the same with ω.
  2. The alternative convention seems to fit natural language better. If I see "two times omega" ($2\omega$), I think "two copies of omega", not "two, of which I take omega copies". If I see "omega times two" I think "omega copies of two", not "omega, of which I take two copies".

  But for some reason the choice that strikes me as poorer has become the standard choice, I'm fairly sure, in all of mathematical logic. I don't know why, but I do know how one makes oneself understood. --Trovatore (talk) 18:45, 16 January 2022 (UTC)

• Gentzen's 1936 paper with his consistency proof of PA defines addition on ordinals in such a way that $\omega +1=1+\omega$. I seem to recall Gentzen saying he was introducing a novelty but it is far more convenient for actually defining the assignment of ordinal degrees to proofs. The definition is a little less clean, though. I've presented my own work following Gentzen just saying I was using Gentzen's definition, but for all I know I was losing my audience when I said that. — Charles Stewart (talk) 22:32, 16 January 2022 (UTC)

  Chalst oh! I thought you were just using ordinary ordinal multiplication, but defined backwards, which there are some good arguments for doing, and which I think Cantor may have originally done, but for some reason is not the standard convention. If you were using a sort of ordinal addition that's commutative, that's a much more radical change.

  I am not familiar with Gentzen's operations. Are they by any chance the so-called Hessenberg operations, defined here? --Trovatore (talk) 18:06, 17 January 2022 (UTC)

• Yes: Gentzen needed addition, multiplication and exponentiation to define the degrees less than $\epsilon _{0}$ and he defined, less elegantly IIRC, commutative versions for addition and multiplication. That suggests reinvention: I had not heard of Hessenberg's work before you linked to it. I suppose I should actually read our articles on ordinals. I'm actually quite interested in finding out more about the early history. — Charles Stewart (talk) 18:35, 17 January 2022 (UTC)

(edit conflict) If we agree that not A implies B, and we succeed in proving that B is false, we have proved that A is true (in classical logic). Where is the contradiction? (Here A = "CH is true" and B = "CH can be proved or disproved"). Apart from that, it is conceivable (to mathematical Platonists) that there is a counterexample for which the logic is not strong enough to prove that it is a counterexample.  --Lambiam 15:01, 14 January 2022 (UTC)

@Lambiam: So, can the Goldbach conjecture and the Fermat last theorem (if it has not been proven) be undecidable? ——2402:7500:917:30C4:54AA:108F:3ECB:103F (talk) 15:04, 14 January 2022 (UTC)

The concept of undecidability does not apply to individual propositions, but only to predicates (problems that can be posed as a yes–no question of the input values). Undecidability then means the predicate is not a computable function. If you want to extend it to propositions, meaning being neither provable nor disprovable, then consider the following paradox:

The propositions true and false are (trivially) decidable.

Consider any proposition P. Then P ∨ ¬ P, or, equivalently, (P ⇔ true) ∨ (P ⇔ false). In either case, P is equivalent to a decidable proposition. Since P is equivalent to a decidable proposition, P is decidable.

The moral of the paradox is that you have to be very careful not to mix the logic with the metalogic, the logic used to reason about the logic.  --Lambiam 15:26, 14 January 2022 (UTC)

That's one usage of the word undecidable, but it's also commonly used to mean "not provable or disprovable". In this case, however, it's a binary relation between a statement and a set of axioms, not a unary relation. This is OP's mistake. They have an argument that no $\Pi _{1}^{0}$ sentence can be undecidable, despite Gödel's canonical example being $\Pi _{1}^{0}$. I've seen at least one math popularizer make the same mistake.--Antendren (talk) 18:51, 14 January 2022 (UTC)

Just a note here: The use of "undecidable" to mean "independent" is as you say common, but it's also — how can I put this subtly and nonjudgmentally — bad. "Undecidable" should be used only in the context of decision problems. A fixed proposition can be independent of a given formal theory, but it can't be "undecidable".

(Here I'm talking in the context of normal Platonistic mathematics. It's different when you're talking with intuitionists — they sometimes use "undecidable", not to mean "neither provable nor disprovable", but rather "neither true nor false".) --Trovatore (talk) 18:59, 14 January 2022 (UTC)

One other point to keep in mind is that, when we talk about "proving" that some set is a counterexample, we have to have a way to talk about that set in the first place. And we might not.

That is, it could be that CH is false, but that no counterexample is even a definable set. Then how are you going to prove such a counterexample is actually a counterexample? You don't even have a name for it. --Trovatore (talk) 22:51, 15 January 2022 (UTC)

“2ⁿ color theorem” in n dimensions?

Like four color theorem in two-dimension plane, is there a “2ⁿ-color theorem” in n-dimension space? Prove or disprove it. ——118.170.50.5 (talk) 10:12, 14 January 2022 (UTC)

Our article four color theorem includes a "proof without words" that the number of colours needed is unbounded in three or more dimensions. It is possible to arrange infinitely many solid objects in 3 dimensional space which all border on one another, so infinitely many colors are necessary. Staecker (talk) 12:35, 14 January 2022 (UTC)

I don't see any good reason to phrase it as "unbounded". The number of colors needed is infinite. Specifically, the smallest infinite cardinality, aleph-zero. (It can't be uncountable because Euclidean 3-space is separable. That's taking the "regions" to be connected open sets, where they "touch" if the intersection of their closures contains a nonempty 2D manifold. You could probably get an uncountable chromatic number if you took the graph-theoretic version; I'd have to think about it.) --Trovatore (talk) 05:52, 15 January 2022 (UTC)

The chromatic number, viewed as a function mapping finite collections of disjoint open 3-D sets to natural numbers, is an unbounded (but total) function. With this restriction to maps for a finite number of "solid" countries, the term "unbounded" is appropriate. There are infinite collections, though, for which no finite number of colours suffices.  --Lambiam 12:23, 15 January 2022 (UTC)

But why would you restrict to finite collections in the first place, or require the answer to be a natural number? The answer is naturally a cardinal number, and the chromatic number is still well-defined even when that cardinal happens to be transfinite. --Trovatore (talk) 19:34, 15 January 2022 (UTC)

I don't require the answer to be a natural number, but if the collection is finite, so is (obviously) its chromatic number. The restriction to finite maps is natural in the original setting – colouring a map of the counties of England – and likewise if the regions are countries or administrative divisions of other countries; their number will not exceed the size of the human world population, which is bounded by the number of baryons in the observable universe. Being mathematicians, we seek to generalize; to the typical reader this may come across as a perverse urge strange.  --Lambiam 20:48, 15 January 2022 (UTC)

@Staecker: I don’t think that it is possible to arrange more than 2ⁿ solid objects in n dimensional space which all border on one another, how do you arrange infinitely many solid objects in 3 dimensional space which all border on one another? ——2402:7500:917:30C4:54AA:108F:3ECB:103F (talk) 13:05, 14 January 2022 (UTC)

Just look at the visual proof. What more do you want?  --Lambiam 15:57, 14 January 2022 (UTC)

I think OP would be happy if the "visual proof" showed nine pieces. —Tamfang (talk) 05:09, 15 January 2022 (UTC)

After all, use Euler's formula in n dimensions ($k_{0}-k_{1}+k_{2}-k_{3}+\cdots =1$, where $k_{n}$ is the number of n-dimension cell in the given polytope), we can show that in n-dimension space, there is always at least one solid object with degree k−1 or less, where k is the kissing number in n-dimension space, since all solid objects have degree ≥k will make contradiction (if all have degree = k, then there will be infinitely many solid objects), like that in two-dimension plane, there is always at least one region with degree 6−1=5 or less. ——2402:7500:917:30C4:54AA:108F:3ECB:103F (talk) 13:13, 14 January 2022 (UTC)