23

While the title of this question is subjective, I hope to make what I'm looking for quite concrete. The first, and main question is this: If you believe that a problem you are working on is formally undecidable, but you are not a logician, what are some ways to begin learning the tools necessary for you to try to prove undecidability? Where should one begin?

Now, for an explicit example. In ring theory one of the big open problems is called Koethe's conjecture. There are many equivalent ways to state the conjecture such as "The sum of two nil left ideals is still nil." Let me give another equivalent description.

Let $R=\mathbb{Z}\langle a,b\rangle$ be the free ring on two non-commuting generators. Suppose that $I$ is a left ideal of $R$, containing some power of $b$, and containing some power of every element of $Ra$. Then the conjecture asserts $I$ contains some power of $a+b$. Note that $R$ is countable, and in fact we can easily enumerate the elements of $Ra$ as $f_1,f_2,\ldots$.

Thus, given any sequence of positive integers $\vec{n}=\{n_0,n_1,n_2,\ldots\}$, the conjecture asserts that the left ideal containing $b^{n_0},f_1^{n_1},f_2^{n_2},\ldots$ also contains a power of $a+b$.

For some sequences $\vec{n}$ (such as eventually constant sequences), it is not difficult to compute that the conjecture is true. But in general the computations get extremely difficult. Lam says in his "First Course in Noncommutative Rings" p. 171, that there has been a

(long-held) suspicion that the Conjecture is false.

If so, then it is false for a sufficiently fast growing sequence $\vec{n}$.

However, one of the troubles here is that nobody knows how to control the behavior of $I$ for fast growing sequences $\vec{n}$, and there are also ways to modify $I$ only slightly and provably not produce a counter-example.

My current hunch is that the conjecture is false, but to see this we need tools to assert that (for fast growing vectors $\vec{n}$) the ideal $I$ stays complicated. I'm not confident that the regular tools from ZFC are sufficient to the task; but have no idea where to go from here.

One last comment: There is always the danger of fearing that a problem one is working on is formally undecidable, just because you can't immediately solve it. Because of this I haven't given up hope that there is such a solution. However, there is also the chance that some stronger set theory may provide tools to look at the problem differently, and really that's what I'm after.

Ricardo Andrade
  • 6,139
Pace Nielsen
  • 18,047
  • 4
  • 72
  • 133
  • 1
    You said "There is always the danger of fearing that a problem one is working on is formally undecidable, just because you can't immediately solve it." The same theory that says there are undecidable problems also says there are really, really difficult problems. I think the fear that one's problem is undecidability and the fear that one's problem is the next Riemann hypothesis are not very different. (Although one can prove that a problem is undecidable. I don't know how to prove that a problem is difficult.) – Jason Rute Feb 06 '15 at 17:13
  • 7
    You become a set theorist, and prove that the problem is undecidable! :-) – Asaf Karagila Feb 06 '15 at 17:23
  • 3
    So there are a number of graph theory results saying that problem X is undecidable by showing that a procedure to decide problem X would lead to a procedure to decide problem Y (which is known to be undecidable). One such problem Y that I have used is the problem of deciding whether the plane can be tiled with a given set of Wang tiles (http://en.wikipedia.org/wiki/Wang_tile). Of course I have no idea whether this is useful in your problem. – Anthony Quas Feb 06 '15 at 18:06
  • 1
    I was thinking at the same type of problem as Anthony. Also, more similar maybe, given a collection of integer 3x3-matrices, determining if any product of these matrices is the zero matrix, is also undecidable. – Per Alexandersson Feb 06 '15 at 18:16
  • 4
    If I am not misunderstanding the problem, then it can be stated as a $\Pi_1^1$ statement. If so, this at least means that forcing technique cannot change its truth value. (see the relevant absoluteness result here) – Burak Feb 06 '15 at 18:25
  • @AnthonyQuas, that is an interesting idea. From the wiki, it appears this form of undecidability ultimately comes from embedding some form of Turing machines into the tiling process. Is there any literature on making rings into Turing machines? If so, does nilpotence play an important role? – Pace Nielsen Feb 06 '15 at 18:35
  • 2
    @Burak: This actually gives an opportunity of proving things with forcing. It suffices to show that you can always force a particular truth value in order to prove the statement. – Asaf Karagila Feb 06 '15 at 18:53
  • 1
    @PaceNielsen: You give a nice formulation of Koethe's conjecture -- where is it from? (Lam, page 171 gives a number of equivalent formulations of this conjecture, but your version does not seem to appear there). I particularly like your formulation because it 'reduces' the problem from arbitrary rings to a particular ring. – Stefan Kohl Feb 06 '15 at 18:54
  • 8
    @AnthonyQuas and Per Alexandersson: “Undecidable problem” means one of two different things: (1) a non-computable set of integers (or other finite objects); (2) a statement independent of a given theory. Wang tiles are an instance of (1), whereas the question asks for (2). – Emil Jeřábek Feb 06 '15 at 19:00
  • 2
    @AsafKaragila: I know absoluteness results are how we prove things via forcing. Since the title suggested that the problem might be independent of ZFC, forcing will not help. On the other hand, as you have noted, if one can force this statement to be false, as Pace suspects, then it is false. – Burak Feb 06 '15 at 19:00
  • 2
    @StefanKohl, good question. Start with the claim "the sum of two nil left ideals is nil". The only trouble here is closure under additivity. Thus, if this were false, $a+b$ would not be nilpotent while $Ra$ and $Rb$ were nil ideals. Further, if it were false somewhere, then it would be false freely. Finally, the reduction from $Rb$ being a left nil ideal to just $b$ being nilpotent is something I came up with (although I think it was found long ago by Puczylowski, and I believe it is open even for $b^2=0$!). – Pace Nielsen Feb 06 '15 at 19:06
  • 3
    @EmilJeřábek, thank you for the clarification between the two meanings of undecidable. You are correct that I am most interested in (2). That said, a related question is whether given a vector $\vec{n}$ (as above) one can compute an integer $m$ so that $(a+b)^m\in I$ (or output $\infty$ if no such integer exists). So decidability/computability in the sense of (1) is also somewhat relevant! – Pace Nielsen Feb 06 '15 at 19:10
  • 2
    @PaceNielsen: How do you give the infinite sequence $\vec n$ to an algorithm as input? Anyway, once you do it in such a way that generators of the ideal are enumerable, you can compute an $m$ by brute-force search (assuming it exists in the first place). – Emil Jeřábek Feb 06 '15 at 19:18
  • 1
    @EmilJeřábek, of course you are right, I should have seen that. A brute-force search to larger degrees (iterating over larger and larger initial segments of $\vec{n}$) will either produce $m$ or never halt. So the question is ultimately whether that algorithm always halts. – Pace Nielsen Feb 06 '15 at 19:28
  • 20
    $$\begin{array}{l}\text{When in danger or in doubt,}\cr \text{Run in circles, scream and shout.}\end{array}$$ – Will Jagy Feb 06 '15 at 20:44
  • @Pace "Is there any literature on making rings into Turing machines?" That's the wrong way around, you typically want to interpret Turing machines into ring structures. – François G. Dorais Feb 06 '15 at 22:36
  • 1
    It's hard to decide. – Włodzimierz Holsztyński Feb 07 '15 at 06:00

2 Answers2

37

The first thing to say is that for a statement to be independent of some axioms means really two things, namely, that it is consistent with those axioms, and also that the negation of the statement is consistent with those axioms. And typically, the proofs of these two things are essentially unrelated. So in your case, where the question appears to be open, I would say that it is somewhat premature to speculate about full independence, when instead you should speculate about the consistency of the statement, or the consistency of the negation of the statement. Independence occurs only when both of these situations are the case.

The second thing to say is that of course almost every nontrivial statement is independent of some very weak set of axioms; you didn't specify which axiomatic system you were considering for independence, but the nature of the independence proofs varies quite a lot depending on the system that one is considering. Often, statements that are proved independent of PA or some other weak system are provable in ZFC, and similarly a statement that is independent of ZFC might be provable from ZFC plus large cardinals or some other strong system. No statement is independent in any absolute sense, since in the theory taking a position on that statement, it becomes settled. So the property of a statement being independent is only sensible relative to a particular axiomatic system.

Furthermore, I would say that the philosophical significance of an independence result can vary quite a bit depending on the background system for which it is established. To my way of thinking, the fact that PA does not prove, say, that $\epsilon_0$ is well-founded is less troubling philosophically than the fact that CH and many other statements appears to be unsettled by ZFC plus any of the known large cardinal axioms, which are consistency-wise the strongest theories we know about, since in the first case we might look upon it simply as a weakness of PA, but in the latter case we appear to be left with some angst about what is the real truth of the matter of CH.

So let me discuss the way a set theorist approaches the possibility of independence. These are some of the questions that come to mind when considering the possibility of independence.

Is the statement something that could be changed by forcing? The overwhelming majority of known independence results in mathematics are ZFC independence results established by the method of forcing. Almost every natural nontrivial statement of infinite combinatorics has been proved to be independent of ZFC by forcing, and we have an enormous number of naturally occuring statements in mathematics that are known to be independent of ZFC.

Nevertheless, in some cases, we can tell that a statement can definitely not be shown independent by means of forcing, simply because of its logical complexity. Specifically, the Shoenfield absoluteness theorem shows that any $\Sigma^1_2$ statement is invariant by forcing.

For example, in the case of your example, it appears to have complexity $\Pi^1_1$, and this means that your statement is invariant by forcing. Thus, it will not be possible to prove your statement independent of ZFC by means of forcing. This doesn't mean it isn't independent of ZFC, but it will not be proved independent of ZFC in the way that most statements known to be independent of ZFC have been proved to be independent of ZFC.

Is the statement something that become settled if a certain set were to become countable? Any given set can become countable in a forcing extension, and this situation often settles many specific statements.

Is the statement settled by the continuum hypothesis, or by Martin's Axiom? Many statements can be proved consistent by being a consequence either of the continuum hypothesis or the generalized continuum hypothesis or by Martin's axiom or other axioms that are known to be relatively consistent with ZFC. This is a very common way for non-set-theorists to establish consistency results, by proving that the statement they are considering are simply a consequence of statements about which consistency results are already known.

Is the statement a consequence of the existence of large cardinals? Does it imply the existence or consistency of large cardinals? Sometimes it happens that the existence of large cardinals can imply the truth or consistency of a given statement, or a given statement implies the truth or consistency of lesser large cardinals, and in this way the consistency of the statement fits into the large cardinal hierarchy. This has consequences for independence. For example, if every set of reals is Lebesgue measurable, then $\omega_1$ is inaccessible to reals, and so the consistency of that situation with ZF implies the consistency of an inaccessible cardinal with ZFC. It follows that we cannot prove even in Con(ZFC) itself (if this is consistent) that ZF does not prove the existence of a Lebesgue non-measurable set. There are many similar situations, where a given statement $\varphi$ might imply the existence of an inner model with a given large cardinal, and so it follows that the consistency of the statement cannot be proved without assuming at least the consistency of that large cardinal hypothesis.

For independence over weaker systems, such as the usual systems of second-order number theory, there are another whole list of questions that one would ask, and I would expect that some other MO users might elaborate on this. For example, Is the statement something that would be settled in the world in which everything is computable? If not, the statement has a hope to be independent of $\text{RCA}_0$, which is the universe of second-order number theory consisting essentially of computable sets only.

Ultimately, to prove that statement $\varphi$ is independent of theory $T$ means to prove both that $T+\varphi$ is consistent and also $T+\neg\varphi$, and so one needs to appreciate the depth and subtlety of consistency proofs for the various theories $T$ that might be under consideration.

Joel David Hamkins
  • 224,022
  • 1
    The Koethe conjecture is a conjecture in ordinary mathematics, so the relevant set of axioms is ZFC. – arsmath Feb 07 '15 at 09:57
  • 2
    Yes, except that since it has complexity $\Pi^1_1$, the natural context for independence results might be second-order number theory. The methods of reverse mathematics could conceivably have something to say about it. – Joel David Hamkins Feb 07 '15 at 12:46
  • 2
    This is an excellent answer, with a lot of questions that I hope some other people here might be able to address. – Pace Nielsen Feb 07 '15 at 17:15
4

Joel David Hamkins has given a good answer in the case of (2), where a certain notion when expressed formally in the language of a theory $T$ (and also the negation of this notion) may not be provable from $T$ using the appropriate proof system. I would like to touch on the other case (1), where it may be possible to show not only that the conjecture is false, but that it can be false in a noncomputable way. This would be a good resolution from the standpoint of the original poster, because it would shed light on the nature of algorithmic questions in general algebra.

(Disclaimer: In spite of my proximity to the subject, I am no expert on decidability. I recommend Algorithmic Problems in Varieties by Sapir and Kharlampovich, and also section 6 and earlier of Ross Willard's "An Overview of Modern Universal Algebra", both available on the Web. I had the privilege of being one of the first to see McKenzie present his work on Tarski's Finite Basis Problem: that work influences this post.)

Consider the possibility that Koethe's conjecture is false. As Pace Nielsen points out in his question, one way that it could be false is that there exists a fast growing sequence $n_i$ and a (hopefully recursive) enumeration $f_1,f_2, \ldots$ of $Ra$ such that $a+b$ and all of its powers avoids all the left-ideals generated by a finite subsequence of $b^{n_0}, {f_1}^{n_1}, {f_2}^{n_2}, \ldots$ . (Unless I missed something, this should be equivalent to his formulation.) It would be nice to be able to characterize those ideals which fail the conjecture, or given a particular ring, to characterize those sequences and enumerations which lead to failure.

As mentioned in the comments, to show that no recursive characterization is possible, one method would be to reduce an undecidable problem to this question. In other words, construct a recursive map $\phi$ so that for every instance $I$ of a problem known to be undecidable, $\phi(I)$ is a sequence (say) of exponents $n_j$ such that a certain enumeration of $Ra$ raised to exponents $n_j$ produces an ideal which contains a power of $a+b$ iff $I$ satisfies the property in the problem known to be undecidable. The Boone-Novikov result is well known (a finitely presented group with undecidable word problem), and the article of Sapir and Kharlampovich contains many more examples, and if the Koethe problem "looks" enough like one of the undecidable problems, one might then construct a recursive $\phi$ as suggested above.

Alternatively, one could have a mastery of the situation that one could try to build a sequence of ideals with such a property that "encoded" Turing machine computations. In the case of Tarski's Finite Basis problem (is there a computer program that can take as input the function tables of a finite algebra A of finite type, and output "yes" if the equational theory of V(A) is finitely-based, and "no" otherwise), there was a series of related problems that McKenzie was working on that allowed him to express a Turing program as an algebra with certain operations corresponding to the state transition table of the program, such that if the halting state were reached, that would correspond to a certain algebraic property in an infinite power of the base algebra, and not correspond otherwise. The properties involved had to do with residual smallness, and McKenzie told me that part of his thought process was to arrange all of the properties he needed in small groups, and make small changes in the algebraic construction to get the group of properties he needed (my wording based on a poor remembering of an event over twenty years in the past).

This is an attempt then to answer the question in a different way: if you suspect the answer is not just no, but no in a non-recursive way, try two approaches: reduction from something in Kharlampovich-Sapir (or other sources), or understand the properties of the ideals that satisfy Koethe's conjecture as well as those that don't, and see if those properties are recursively inseparable (can be related somehow to computations halting or not).

Gerhard "That's How I Would Start" Paseman, 2015.03.24

Gerhard Paseman
  • 3,199
  • 1
  • 18
  • 29