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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.)

Answer 6

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.

Answer 7

The Baumgartner–Hajnal 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.