Popular lecture on mathematical logic

Background:

I am to hold a short (10-15 min) talk that is supposed to inspire first-year undergraduate students to (in the future) take on courses in mathematical logic. They have only been introduced to the very basics of propositional logic. An obvious candidate would be Gödel's incompleteness theorems, but there is already so much accessible material produced on this topic, so I would rather choose something else. I have considered something on the arithmetical hierarchy, but I find it difficult to point to a result in this topic that is mindblowing in the same sense as Gödel's theorems are.

Furthermore, I think it would be especially nice to introduce them to some topic in constructive mathematics. I have considered explaining why the seemingly controversial statement every function on the reals is continuous is not as crazy as it sounds. I'm thinking that perhaps this should catch their attention.

Question(s):

To summarise i have three questions (independent of each other)

1. Are there any other counterintuitive results in general mathematical logic that you think would be met with as much enthusiasm as I believe that Gödel's incompleteness theorems would be (sorry, I do realise that this question is somewhat vague).
2. What would be a good way to introduce the fundamental concepts of the arithmetical hierarchy in a captivating way that does not require any background in logic? Do you have any suggestions of results I can present that will both be accessible and (hopefully) interesting to a non-specialised undergraduate student.
3. Do you have any suggestions for how I can introduce the concepts and ideas behind constructive mathematics? It would be nice to include some counterintuitive result, like the one I mentioned.

Any suggestions would be very much appreciated!

EDIT: I do realise that there are thousands of threads like this, but there is little on mathematical logic in these. In any case, if this has been asked before, then I apologise in advance.

• Could you refine your question slightly? As it stands now, your question is probably too broad for our site. Do you have any ideas for the topic yet? – Toby Mak Sep 16 at 10:18
• Maybe talk a bit about paradoxes? They tend make people think, and it shows the importance of having a precise logical system (so that they are either resolved, or cannot occur). – Mark Kamsma Sep 16 at 10:33
• Maybe the Ax theorem? The model theory-based proof illustrates how a disproof of the statement in the field of complex numbers can be generalized to any algebraically closed field in large enough characteristic — however, the statement holds in all $\overline{\mathbb{F}_p}$, hence a contradiction. – Mindlack Sep 16 at 10:44
• @TobyMak edited, hopefully it is more precise now – KurtKnödel Sep 16 at 10:48
• Maybe Eric Schechter's 2001 paper Constructivism is difficult, Sebastiaan A. Terwijn's 2016 expository survey The mathematical foundations of randomness (and Rutger Kuyper's 2018 expository paper An introduction to (algorithmic) randomness), the reverse mathematics program, and this book – Dave L. Renfro Sep 16 at 12:33

In Forever Undecided, Smullyan made a detour from his normal (and amazing) Gödel discussions to talk about an intuitive reframing of Löb's theorem. If you feel like your students are already familiar with Gödel, that might be something fresh for them.

• This is a great suggestion. Thanks! – KurtKnödel Sep 16 at 11:02

I would suggest showing how much you can do with mathematical logic ... as a way to lead up to Godel.

Here is a good starting point: a website that lists the formal proofs that have been completed in various mathematical proof systems. You could follow some of the links and show some specific proof (I personally like Metamath's website, as all the subresults are linked, and so you get some idea as to how crazy big some of these proofs are).

In this context, you can then also take about the formalizations of the Four Color Theorem (first purely formal proof was produced in 2005), and Kepler's Sphere Packing Conjecture (formal proof completed in 2014) ... which can get into some nice discussions as to what exactly counts as a proof as well...

And, all this will then bring up the natural question: can we formalize all? ... thus Godel.

All in all, more like 30-40 minutes though .. rather than 10-15. But maybe you can polish it down to 20 minutes, Ted Talk -style