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.

  • $\begingroup$ 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. $\endgroup$ May 23 '20 at 10:33
  • $\begingroup$ 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. $\endgroup$
    – xuq01
    May 23 '20 at 10:40

The De Bruijn-Erdős theorem seems like a good candidate, its statement only involves graphs, which computer science students with no abstract algebra exposure should also be familiar with.

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

This theorem (and its version for hypergraphs) can be proved by a straightforward application of the compactness theorem for first order order logic, although this was not the first proof given historically

  • $\begingroup$ 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 $\endgroup$
    – Anonymous
    Jun 2 '20 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.