How much set theory is necessary for serious logic?

Question

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?

Answer 1

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!]

Answer 2

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