Mathematical logic required background

Question

Does one needs undergraduate knowledge of every branch of mathematics in order to study mathematical logic at the graduate level, or is undergraduate knowledge in only mathematical logic sufficient?

Answer 1

Well, you certainly don't need undergraduate knowledge in every branch of mathematics: $$\neg[\text{is-prepared-to-take-grad-logic}(s)\rightarrow\forall b[\text{branch-of-knowledge}(b)\rightarrow\text{knows}(s,b)]]$$ (smiley).

But I think you'd need a good background in at least one branch. Specifically, abstract algebra: the "patterns of thought" of algebra find a lot of play in much of mathematical logic. Also, examples in the logic course are quite apt to draw on algebra. Discrete math might also be a reasonable alternative.

Basic set theory (at the level of, say, Kaplansky's Set Theory and Metric Spaces, or Halmos's Naive Set Theory) is a must, but people don't usually take a course just in that.

There's quite a range in undergrad logic courses. Sometimes the emphasis is mainly on the notation of first order predicate logic, especially if they're given by the philosophy or linguistic departments. This does not strike me as an adequate background by itself. Others cover the beginnings of model theory, the incompleteness theorems, maybe some axiomatic set theory and some recursion theory. Someone who does well in a course like that is probably in good shape.

My advice is to spend a day skimming through a few textbooks, at both the undergrad and grad level. (E.g., Shoenfield, Mathematical Logic for grad level.) Obviously you won't absorb everything, but if the grad-level material looks like gibberish, that's a red flag.

Let me close with a "mini-quiz". I think anyone starting grad-level logic should not find these questions too daunting.

1. Why do you need the axiom of choice to show that if $f:A\rightarrow B$ is onto, then $f$ has a left inverse, i.e., a $g:B\rightarrow A$ such that $gf=\text{id}_A$? Also, does $g$ have to be injective?
2. The $\epsilon-\delta$ definition of a limit involves two quantifiers. If we "alternate the quantifiers" (i.e., replace $\forall\epsilon\exists\delta$ with $\exists\delta\forall\epsilon$), what does the resulting statement mean? Can it be true? (Extra credit: explain how alternation of quantifiers is behind the distinction between plain-old continuity and uniform continuity.)
3. Say an operation $\circ$ is well-defined with respect to an equivalence relation $\equiv$. Express this as a formula in first-order logic.
4. Universal quantifiers commute, as do existential quantifiers: $\forall x\forall y$ is equivalent to $\forall y\forall x$, likewise for existential. Supoose we introduce the "most of" quantifier for a structure with a finite universe: $Mx\phi(x)$ means that more than half of the elements of the universe satisfy the predicate $\phi$. Construct an example to show that $MxMy$ is not necessarily equivalent to $MyMx$.

(Hint for (4): blood types.)