# What are some examples of "non-logical theorems" proven by Logic?

I am still an undergraduate student, and so perhaps I just haven't seen enough of the mathematical world.

Question: What are some examples of mathematical logic solving open problem outside of mathematical logic?

Note that the Ax-Grothendieck Theorem would have been a perfect example of this (namely, If $P$ is a polynomial function from $\mathbb{C}^n$ to $\mathbb{C}^n$ and $P$ is injective then $P$ is bijective). However, even though there is a beautiful logical proof of this result, it was first proven not specifically using mathematical logic. I'm curious as to whether there are any results where "the logicians got there first".

Edit 1:Bonus: I am quite curious if one can post an example from Reverse Mathematics.

Edit 2:This post reminded me that the solution to Whitehead's Problem came from logic (a problem in group theory). According to the wikipedia article, the proof by Shelah was 'completely unexpected'. It utilizes the fact that ZFC+(V=L) implies every Whitehead group is free while ZFC+$\neg$CH+MA implies there exists a Whitehead group which is not free. Since these two separate axiom systems are equiconsistent, hence Whitehead's problem is undecidable.

Edit 3: A year later, we have some more examples:

1) Hrushovski's Proof of the Mordell-Lang Conjecture for functional fields in all characteristics.

2) The Andre-Óort conjecture by Pila and Tsimerman.

3) Various results in O-minimality including work by Wilkie and van den Dries (as well as others).

4) Zilber's Pseudo-Exponential Field as work towards Schanuel's conjecture.

• What's "mathematical logic" in this case? Commented Jul 28, 2014 at 23:14
• en.wikipedia.org/wiki/Ax%E2%80%93Kochen_theorem Commented Jul 28, 2014 at 23:20
• You can find many examples of applications of model theory in this MathOverflow thread. Commented Jul 28, 2014 at 23:42
• I believe Ramsey's theorem was motivated by a problem in mathematical logic, but I guess that's not what you're looking for. Well, sticking with Ramsey theory, what about the Halpern-Läuchli partitio theorem? Wasn't that proved using mathematical logic?
– bof
Commented Jul 28, 2014 at 23:43
• I agree with @bof that the Halpern-Läuchli theorem is a good example. The original proof involved a custom-designed deductive system for efficiently handling the complicated nested quantifier combinations that need to be manipulated in the proof. Commented Jul 29, 2014 at 7:13

I was impressed by Bernstein and Robinson's 1966 proof that if some polynomial of an operator on a Hilbert space is compact then the operator has an invariant subspace. This solved a particular instance of invariant subspace problem, one of pure operator theory without any hint of logic.

Bernstein and Robinson used hyperfinite-dimensional Hilbert space, a nonstandard model, and some very metamathematical things like transfer principle and saturation. Halmos was very unhappy with their proof and eliminated non-standard analysis from it the same year. But the fact remains that the proof was originally found through non-trivial application of the model theory.

Another example is the solution to the Hilbert's tenth problem by Matiyasevich. Hilbert asked for a procedure to determine whether a given polynomial Diophantine equation is solvable. This was a number theoretic problem, and he did not expect that such procedure can not exist. Proving non-existence though required developing a branch of mathematical logic now called computability theory (by Gödel, Church, Turing and others) that formalizes the notion of algorithm. Matiyasevich showed that any recursively enumerable set can be the solution set for a Diophantine equation, and since not all recursively enumerable sets are computable there can be no solvability algorithm.

This example is typical of how logic serves all parts of mathematics by saving effort on doomed searches for impossible constructions, proofs or counterexamples. For instance, an analyst might ask if the plane can be decomposed into a union of two sets, one at most countable along every vertical line, and the other along every horizontal line. It seems unlikely and people could spend a lot of time trying to disprove it. In vain, because Sierpinski proved that existence of such a decomposition is equivalent to the continuum hypothesis, and Gödel showed that disproving it is impossible by an elaborate logical construction now called inner model. As is proving it as Cohen showed by an even more elaborate logical construction called forcing.

A more recent example is the proof of the Mordell-Lang conjecture for function fields by Hrushovski (1996). The conjecture "is essentially a finiteness statement on the intersection of a subvariety of a semi-Abelian variety with a subgroup of finite rank". In characteristic $0$, and for Abelian varieties or finitely generated groups the conjecture was proved more traditionally by Raynaud, Faltings and Vojta. They inferred the result for function fields from the one for number fields using a specialization argument, another proof was found by Buium. Abramovich and Voloch proved many cases in characteristic $p$. Hrushovski gave a uniform proof for general semi-Abelian varieties in arbitrary characteristic using "model-theoretic analysis of the kernel of Manin's homomorphism", which involves definable subsets, Morley dimension, $\lambda$-saturated structures, model-theoretic algebraic closure, compactness theorem for first-order theories, etc.

• Do you mean "recursively enumerable"rather than "recursive" at the end of the second paragraph?
– Ned
Commented Jul 29, 2014 at 22:52
• Yes, sorry about that Commented Jul 29, 2014 at 23:07
• Your first example sounds very convincing, but Hilbert's tenth problem has the concept of algorithm (or procedure, or whatever you call it) in the statement and so must be solved by developing a formalization of this. It's not surprising that this was, in fact, the case, and whether the resulting theory is actually a branch of logic is both an opinion and sort of incidental. Commented Jul 30, 2014 at 2:55
• @ Ryan Reich Only if you assume it was impossible. Euclid's algorithm existed for centuries without formalization of algorithms, and belongs to number theory as would a Diophantine algorithm if it existed. The ellipse method for linear programming was developed after formalization, and didn't use much of it. Hilbert, a founder of logic, didn't think it was impossible or needed formalization. The arguments Matiyasevich used (recursive deconstruction of expressions) are exactly of the type used in logic, which is why computability theory was developed by many of the same people as logic. Commented Jul 30, 2014 at 23:10
• And even if you assume it was impossible the non-existence of algorithms for squaring a circle with Euclidean tools, or for solving equations in radicals was proved long before formalization of algorithms, so there is no "must" there, and it was "surprising". I am not sure what "incidental" means, but that the type of computability theory used in the proof "is a field of mathematical logic" even according to Wikipedia, and their "main professional organization" is called Association for Symbolic Logic en.wikipedia.org/wiki/Computability_theory#Name_of_the_subject. Commented Jul 30, 2014 at 23:51

The Tarski–Seidenberg theorem says that the set of semialgebraic sets is closed under projection. It's a pure real-algebraic statement that was originally proved with logic.

Jacobson says this in chapter 5 of his Basic Algebra I:

More generally, Tarski's theorem implies his metamathematical principle that any "elementary" sentence of algebra which is true in one real closed field (e.g., the field of real numbers) is true in every real closed field.

Not sure if this qualifies, but Goodstein's theorem which appears quite number theoretic and states that any Goodstein sequence converges, was proved using ordinals.

• ... and it is interesting that you cannot do without ordinals, in some sense. (Details can be found at the wikipedia page.) Commented Jul 29, 2014 at 18:01

So automated theorem provers consist of an application of mathematical logic. Consequently, the solution of the Robbins conjecture by William McCune using EQP qualifies as solving an open problem outside of mathematical logic by using mathematical logic.

The compactness theorem gives many ways to generate theorems of the form "if all finite $X$s have property $P$, then so do all infinite $X$s".

A random example from Bell and Slomson Models and Ultraproducts:

Let $B$ be an infinite set of boys each of whom has at most a finite number of girlfriends. If for each integer $k$, any $k$ of the boys have between them at least $k$ girlfriends, then it is possible for each boy to marry one of his girlfriends without any of them committing bigamy.

This can be deduced (with some work) by using the compactness theorem with this finite version of the lemma:

If $C$ is a set of $m$ boys and for each $k\le m$, any k of the boys have at least k girlfriends between them, then it is possible for each boy to marry one of his girlfriends without any of them committing bigamy.

There are a number of better examples here: Most astonishing applications of compactness theorem outside logic

(Although if you're looking for real world applications of logic, I think type theory for programming languages is a big one.)

Terry Tao has been using Abraham Robinson's framework and more generally ultraproducts (often considered to be "logic" as you put it), as for example his solution of Hilbert's Fifth problem in this recent book.

The BaumgartnerHajnal theorem says that, for any countable ordinal $\alpha,$ and for any coloring of the edges of the complete graph on the vertex set $\omega_1$ (the first uncountable ordinal) with finitely many colors, there is a monochromatic complete subgraph of order type $\alpha.$ This theorem of classical set theory was proved using the method of forcing (in the form of Martin's axiom) and absoluteness. It seems reasonable to consider forcing and absoluteness as logical, and classical set theory as non-logical.