2
$\begingroup$

I should start with the following disclaimer that I know virtually no logic, sorry forgive me if my questions are ill-posed. I appreciate that all of this is probably completely obvious to a logician, but I've gone round asking all these to a lot of mathematicians around me and have so far failed to get any sort of satisfactory answer/reference on the topic.

I'm going to start with a pair of formal questions, and then explain where these come from.

  • Could it be that the statement "$\pi$ is a disjunctive number" is undecidable?
  • Could it be that the statement "The circle diffeomorphism $x \mapsto x + \sqrt{2} + 0.1 \sin(2\pi x)$ has irrational rotation number" is undecidable?

(One more disclaimer, I don't know the formal definition of the concept of undecidability. I take it that a statement is undecidable if assuming that it is true or false in a coherent logical system doesn't create any incoherence).

Undecidability and unprovable statements Like many people I suppose, I've always regarded the question of undecidability as a fairly esoteric one which I shouldn't concern myself with, as it is unlikely I ever come across an undecidable statement. This is mostly because the only example of undecidable I knew about was the continuum hypothesis, and until I'd come across a concrete, reasonable set whose cardinality couldn't be established it would always feel like an empty statement.

Now it's come to my attention that there could be statements which are true but that one couldn't prove. For instance, you could imagine two somewhat explicit functions $f,g : \mathbb{N} \longrightarrow \mathbb{N}$ such that the statement $\forall n, f(n) > g(n)$ is undecidable. That's where my understanding of logic becomes too shaky, but I can't imagine a statement of this form not being, for any reasonable definition of the concepts, either true or false. For all $n$, I can check whether it is true. So if it were to be false, I could exhibit a particular $n$ for which $f(n) \leq g(n)$.

If the statement is undecidable, it's just that it can't be proved.

Now (sorry if it's getting too philosophical), most statements that we try to prove we have reasons to think that they are true; a proof is not just a formal logical reasoning, it's also taming some sort of phenomenon which we thought was behind the statement.

There could well be some (simple) statements, which turn out to be true for no particular phenomenological reason. Such statements, I would actually be surprised if they could be proven to be true, as in my semi-religious belief a proof is a phenomenological justification for why something is true. It's bumping into such a statement (the second one above) that I started wondering about this kind of things.

The rotation number as a potential source of undecidability For those who do not know much dynamical systems, to a circle homeomorphism $T : S^1 \longrightarrow S^1$, one can associate a number $\rho(T) \in S^1 = \mathbb{R}/\mathbb{Z}$ which has some dynamical significance. It's a well-known theorem that in parameter families like $T_{\alpha, \epsilon} := x \mapsto x + \alpha + \epsilon \sin(2 \pi x)$, the probability that a parameter $(\alpha, \epsilon)$ corresponds to a rational/irrational rotation number has positive probability.

The definition of the rotation number involves taking a limit of infinitely many iterations of the map $T$, and somehow is highly transcendental with respect to the parameters $(\alpha, \epsilon)$. I want to speculate that the precise value of $(\alpha, \epsilon)$ is somewhat uncorrelated to the actual dynamical behaviour of $T_{\alpha, \epsilon}$. If there were a proof that $x \mapsto x + \sqrt{2} + 0.1 \sin(2\pi x)$ has irrational or rational rotation number, it would suggest that arithmetic properties of $\alpha$ and $\epsilon$ are reflected in the highly transcendental process of taking a limit of many iterations of $T_{\alpha, \epsilon}$. I would find this hard to believe, and therefore I would incline to believe that such a statement cannot be proven!

$\pi$ is disjunctive A number is disjunctive if its decimal expansion contains every finite sequence. It is relatively easy to prove that almost every real number is disjunctive. But now if one takes a number which is not defined in terms of its decimal expansion and that its decimal expansion cannot be made somewhat explicit using the (a) way it is defined, I would expect that

  • it is disjunctive (because almost every number is)
  • it is impossible to prove if the way the number is defined is "transcendental with respect to the decimal expansion".

Are such statements undecidable? The more I do maths, the more I come across conjectures about particular objects, the heuristical reasons why they are believed to be true seem to be true only generically for a wider class of objects. Has anyone considered the fact that such statements could be very good candidates for being undecidable statements?

A general question to conclude would then be : do logicians have interesting things to say about problems with this general structure? (a statement $S$ about a particular object $A$, known to hold true only generically for a wider class of objects $\mathcal{C}$, the definition of $A$ being "transcendental" with respect to the properties used in the proof that generic objects of $\mathcal{C}$ satisfy $S$).

Improve this question
$\endgroup$
17
  • 2
    $\begingroup$ "you could imagine two somewhat explicit functions $f,g$ [...]" here is a simple example: let $f(n)=n+2$ and $g(n)$ to be the unique natural number $k$ such that there exists a limit (or $0$) ordinal $\alpha$ with $2^{\aleph_n}=\aleph_{\alpha+k}$ $\endgroup$ Commented Nov 9 at 12:30
  • 2
    $\begingroup$ "Decidable" usually means there is an algorithm (i.e., Turing machine) which outputs "yes" or "no" in finite time. It is not clear if that's what you mean. $\endgroup$ Commented Nov 9 at 13:28
  • 5
    $\begingroup$ @StanleyYaoXiao That’s one definition of (un)decidable; but there’s a different (closely related) usage in logic, used to mean independent of a certain set of axioms, see this MO question, and it’s clear OP means the other. $\endgroup$ Commented Nov 9 at 15:08
  • 4
    $\begingroup$ The answer to your question is simple - yes, for all we know, those questions could be independent (of ZFC, say), as is true of almost every open problem out there. However, I don't think many people would seriously entertain that idea. There is no real evidence for it besides "we haven't managed to resolve it yet". $\endgroup$ Commented Nov 9 at 17:23
  • 3
    $\begingroup$ @SelimG The short answer is that any open question is potentially undecidable, unless it has been reduced to a finite computation. See my answer to a related MO question. Somewhat related are Knuth's intuition that Goldbach might be unprovable and True by accident (and therefore not amenable to proof). Just because a problem seems hard does not mean that we have any hope of showing that it's undecidable. $\endgroup$ Commented Nov 10 at 15:35

1 Answer 1

Reset to default
3
$\begingroup$

"it is unlikely I ever come across an undecidable statement. This is mostly because the only example of undecidable I knew about was the continuum hypothesis"

Your hunch that undecidable statements are as esoteric (or at least removed from "ordinary mathematics") as the Continuum Hypothesis is in fact incorrect. A natural question in group theory known as the Whitehead problem turned out to be independent of ZFC, as proved by Shelah. The problem sounds innocent enough: "Is every abelian group A with $Ext^1(A, \mathbb Z) = 0$ a free abelian group?" It can be reformulated easily enough even without the $Ext^1$ condition. There are many other problems of this seemingly non-set-theoretic sort.

Your point about things either being true or not being true is sort of valid with regard to $\Sigma_1$ or $\Pi_1$ statements (i.e., statements involving no alternations of quantifiers). Once you allow for alternations of quantifiers, the sky is the limit: even the twin prime conjecture could in principle turn out to be undecidable relative to, say, the Peano Arithmetic.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I absolutely agree, I just wanted to highlight my naivety when it came to undecidability. Now that you mention this example, this is precisely where my understanding of logic fails me. If I take a specific abelian group, I can define (and a priori compute?) $Ext^1(A,\mathbb{Z})$? If the statement " every abelian group with $Ext^1(A,\mathbb{Z}) =0$ is free abelian" is false, there would be a free abelian group $A$ with $Ext^1(A,\mathbb{Z}) \neq 0$, right? If so, if it's undecidable, every explicit abelian group I will find should have $Ext^1(A,\mathbb{Z}) =0$. What's wrong with this reasoning? $\endgroup$ Commented Nov 11 at 8:44
  • 2
    $\begingroup$ That's an interesting question, but before we get into that, it may be helpful to sort out whether there is an alternation of quantifiers involved. It seems to me that there is: the claim is that for all group extensions $B\to A\to\mathbb Z$, there is a splitting map (but it needs to be confirmed that the alternation cannot be avoided). Second, we are talking about uncountable groups (in the countable case the answer is affirmative). So then your question is not really different from asking: given an uncountable subset of $\mathbb R$, either it is or it isn't of cardinality $c$ :-) $\endgroup$ Commented Nov 11 at 8:57
  • 1
    $\begingroup$ @SelimG, I don't think this is true. Here's what's true: (1) Whitehead problem is independent of ZFC. (2) If one adds Martin's axiom and ¬CH, then there exist counterexamples to Whitehead problem. But it does not follow that one can exhibit a specific exact sequence (over ZFC) which cannot be shown not to split but such that if one throws in those additional axioms, it can be shown to be split. (correcting a misprint) $\endgroup$ Commented Nov 12 at 9:17
  • 1
    $\begingroup$ @SelimG, I am not much of an expert in this area, but one possible hypothesis that makes the answer affirmative is that of "constructible universe" (which is usually labeled V=L). I assume if you require the groups to be constructed or definable in a suitable sense, they would live in the constructible universe, in which case there would be no counterexamples. $\endgroup$ Commented Nov 12 at 18:53
  • 2
    $\begingroup$ I don't get your point about quantifier alternations. Many $\Pi^0_1$ statements are independent of ZFC, starting with the consistency of ZFC. All we can say is that if a $\Pi^0_1$ statement is false then PA (and therefore ZFC) refutes it. $\endgroup$ Commented Nov 13 at 0:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.