# Accessible examples of using ideas in mathematical logic to solve problems in "main-stream" mathematics

It is perhaps well-known that ideas from mathematical logic (esp. model theory) can help solve problems in "main-stream" mathematics, e.g. using ideas from model theory to solve problems in algebraic geometry. However, all of those examples seem quite advanced.

Is there an accessible example of using logical ideas to solve problems in other areas of mathematics (including theoretical computer science)? I'm going to give a lecture to undergraduates and would really like to highlight this to them, and ideally the examples would be easily explainable to someone with only basic mathematical training.

• Are you interested in problems which were solved using methods from logic or are problems for which subsequent simpler proofs were found using tools from logic also ok? There are many results accessible to undergraduates in the second case: the Ax-Grothendieck theorem, the De Bruijn-Erdős theorem, the Tarski-Seidenberg theorem, the solution to Hilbert's 17th problem, weak forms of the Nullstellensatz etc. May 23, 2020 at 10:33
• Both are OK for me. I'm not actually sure many of them have taken abstract algebra, but at least I can explain the basic concepts easily. May 23, 2020 at 10:40

The chromatic number of a graph $$G$$, denoted $$\chi(G)$$, is the least number of colours needed to colour the vertices of the graph in a way such that every edge has endpoints of different colours. The De Bruijn-Erdős theorem states that, given a graph $$G$$, if $$\chi(H)\leq k$$ for every finite subgraph $$H\subseteq G$$, then $$\chi(G)\leq k$$.
• An important point: this relies only on the compactness theorem for propositional logic, not the one for predicate logic. That makes it much easier to state for an audience that doesn't know any logic. The compactness theorem for propositional logic is in fact equivalent to the statement that $\{0,1\}^A$ is a compact topological space for any set $A$ (a special case of Tychonoff's Theorem). A similar application is to the infinite case of Weyl's Marriage Problem. See here: link.springer.com/chapter/10.1007/978-0-8176-4842-8_11 Jun 2, 2020 at 5:45