# How much set theory is necessary for serious logic?

I'm currently studying logic at my university and I have been trying to squeeze in as much set theory on the side as possible. Considering that I am spending quite a lot of time studying set theory independently from my logic coursework I have begun to wonder if it would be a better to devote my extra time to just the logic. Should I expect to encounter necessary set theory for logic in the logic texts that I will use as I advance or is it necessary to study set theory as well as logic to develop a firm grasp of logic?

• For most branches of Logic, no more (and usually less) than one needs for analysis. Aug 26 '14 at 22:36
• Which aspect of logic are you studying ? model theory ? Aug 27 '14 at 1:24
• I'd say that it's at least necessary some grasp of ordinal and cardinal arithmetic. Other than that, it depends on your interests; this link may be of help: logicmatters.net/tyl Aug 27 '14 at 6:32

There's logic and logic! And when does it start counting as "serious"?

For a first math logic course on first-order logic (and I'm including here things like the completeness proof for "ordinary", i.e. countable, languages) you need no serious set theory.

To be sure, it is entirely standard to use set theoretic notation and say e.g. that a model has a domain which is a set equipped with functions and relations where those are also identified with sets of tuples from the domain. But actually, this set-theoretic talk is doing little real work at the outset (and even can be positively misleading). For example, instead of saying that -- in a certain case -- the domain of quantification is the set (singular) of numbers, we can instead say simply that the quantifiers run over the numbers (plural), and so on.

But once you get into e.g. the elements of model theory (compactness, upward and downward L-S theorems and their applications, and a little more), then you'll need to know something about ordinals and cardinals and something about the axiom of choice: so this is where you'll begin to need to know a little set theory.

But how much? Not a lot at the outset. Take a look at the Teach Yourself Logic Guide you can download from http:// logicmatters.net/tyl. Just one of the elementary books mentioned at the beginning of the section on Beginning Set Theory will give you more than enough to get into the other parts of a first course in mathematical logic [Of course, as Asaf says in his comments, as you get further into serious model theory you get more and more embroiled with serious set theory!]

• "Not a lot" may vary. For some model theory you need very basic set theory knowledge; for other model theory you need to understand large cardinals, and forcing arguments. Similarly with logic, if you switch to infinitary logic, or other stronger logics you may run into independence, forcing arguments, and large cardinals pretty fast (see the works of Magidor-Vaananen, or Bagaria's work on polymodal provability logics, to see the flavor of arguments that may come in). Aug 27 '14 at 11:43
• Yes to Asaf! I was making a guess that the OP's rather unspecific "currently studying logic" (and evidently not doing a set theory course) indicated someone near the beginning ... Aug 27 '14 at 15:41
• I like that slogan! I agree with your assumption, but it is still worth knowing what might lie ahead. Aug 27 '14 at 16:09

You could say that set theory is logic - u have ontological axioms (like existence, pairing etc.) guaranteeing the existence of certain objects and comprehension essentially identifying formulas and sets. So what is the difference between $$\{x|S(x)\}\text{ and }S(x)$$

or $\{x\in A|S(x)\}$ and $A(x) \land S(x)$?

The thing with set theory is the following: that what it axiomatizes - the idea of something "belongs to" or "is part of" something - and how it axiomatizes it appears to be very familiar and somehow natural to our intuition. This seems to suggest that set theory is the appropriate base for all mathematics.

But despite that natural feeling with set theory, that claim seems to lack any further justification. Indeed more and more people think that taking set theory in any case for granted as a base for certain theories (like quantum physics or quantum gravity) might be just not appropriate and unjustified and involving it anyway might be the reason for some severe difficulties we face with these theories.

This is one motivation for being interested also in more general concepts like topos theory or typed $\lambda$-calculus - interestingly also theoretical physicists (f.i. C. Isham).

..for more views beyond set theory and logic(= introductory lectures on formal languages and systems, grammars, (in-)completeness + correctness, compactnes, Herbrand, Löwenheim-Skolem, computability, model theory, etc. ?) on logic u could f.i. see

Barnes + Mack: An algebraic introduction to mathematical logic

C. Isham: `What is a Thing?': Topos Theory in the Foundations of Physics

• I don't believe this answers the question that was asked. Aug 28 '14 at 13:51
• "This seems to suggest that set theory is the appropriate base for all mathematics." - no, that's not the reason set theory is an appropriate foundation. Aug 28 '14 at 13:52
• I tried to point out that it seems not useful to distinguish between logic and set theory or logic and model theory or.. (actually what should logic mean then in such claims?). And I tried to introduce also other views that can also mean logic such as more algebraic views on logic.
– FWE
Aug 28 '14 at 14:05
• @ Asaf Karagila - ..what is the reason set theory is an appropriate foundation?
– FWE
Aug 28 '14 at 14:39
• The reason is that set theory internalizes logic in a way which allows semantics as well. This allows us to talk about objects as if they exist (compare that to using second-order arithmetic as foundation, or even weaker systems, which sometimes can talk about provability, but can't quite construct all the objects). This allows us to take second-order statements like "There is a unique order complete field" and turn them into first-order statements in $\sf ZFC$ (or whatever set theory you prefer). And first-order logic is better than second-order logic, since it has reasonable proof theory. Aug 28 '14 at 15:12