1. Games and Determinacy: This is a particularly great subject, as it requires little mathematical background, and yields many results relevant to games that people actually play. Most people figure out fairly quickly that a good tic-tac-toe player will always either win or draw the game. The player is said to have a winning strategy in this situation, and games where a player has a winning strategy are called determined. There are many games that we can prove to be determined by either brute force (tic-tac-toe) or induction (the ‘matchstick game’). Once we develop a mathematical formalization of games, we are able to show that in any zero-sum, perfect information, two player game (such as chess, checkers, tic-tac-toe, etc.), one of the players must have a winning strategy. This proof is simple, and follows from just a bit of mathematical logic. This prompts one to wonder ‘what kinds of perfect information games are not determined?’ To answer this question, we must look to infinite games, a generalization where each player takes infinitely many moves, and the winner is determined by a type of limit. In exploring these games, we use infinite trees, (very) elementary topology, and a small amount of set theory. Perhaps the most fun aspect of this topic is that the proofs usually play out as games against some very skilled imaginary opponent. There is a phenomenal free text in this topic, aimed at mid-level undergraduates: Infinite Games, by Yurii Khomskii.
2. Introductory Computability Theory: Computability theory is the study of algorithms and programs on idealized computers. These days, everyone is familiar with computers, and knows the power of computation. A tenet of computability theory is that any task that can be completed via algorithm can also be carried out by an idealized computer. Are there then tasks that cannot be completed algorithmically? After developing a bit of machinery to represent computers mathematically (as Turing machines), we are able to prove the existence of a set of natural numbers, whose membership function cannot be computed. The proof is by diagonalization, and like most proofs of this sort, can be represented visually. We then are able to develop a theory that allows us to gauge the difficulty of various computational problems. A related topic is the theory of decision problems, ’yes or no’ questions that can be asked of a computer. A personal favorite is the tiling problem: given a finite collection of tiles, does there exist a tiling of the plane using copies of the tiles? Can a computer answer this question? We are able to show that there is a collection of tiles, such that no computer can determine if they can tile the plane