14
$\begingroup$

A bit of background: I'm currently taking a logic class whose ultimate goal is to show soundness, completeness, and undecidability of FOL, and which is following this Sets, Logic, Computation book. I've also started to take a look at the next book in the series, Incompleteness and Computability, which starts out by defining theories as closed sets of sentences in a language, treating only the logical framework of FOL.


I've often heard that most of mathematics can use ZFC set theory as a foundation. With ZFC being a set theory in first-order logic, I presume this means that mathematical statements can be written in the language of ZFC and derived from its axioms. However, intuitively I would think that there are mathematical theorems whose statements can only be stated in second-order logic (I can't think of any examples, and some that I've found seem to confuse second-order quantification with quantifying over sets of sets). So how would ZFC be able to even express such statements, being first-order?

I've also heard that ZFC set theory is "stronger" than second-order logic (in this answer, for instance). First of all, how could a theory in first-order logic be stronger than second-order logic if second-order logic is more expressive? And second of all, how is it even possible to compare a theory (a closed set of sentences in some language) to a logic (a framework for languages with canonical semantics for its logical symbols) especially when a logic encompasses many languages, each of which can admit many theories?

$\endgroup$

1 Answer 1

12
$\begingroup$

The point is that using ZFC we can interpret1 second-order logic. ZFC gives us a way to understand the notion of sets and relations which are necessary for second-order logic.

We can prove, as a first-order statement in the language of ZFC, that there is a unique Dedekind-complete ordered field (up to isomorphism). This is a second-order statement about the real numbers, yes, but we can interpret that in ZFC, which transforms it into a first-order logic statement in the language of set theory.


1. In the non-technical sense.

$\endgroup$
6
  • 5
    $\begingroup$ This is obviously right, but I tentatively think the word "interpret" in the first sentence might better be replaced with something else since when we use its technical meaning that's false. $\endgroup$ Mar 15, 2020 at 18:51
  • $\begingroup$ Any suggestions? $\endgroup$
    – Asaf Karagila
    Mar 15, 2020 at 18:59
  • 2
    $\begingroup$ Not sure, actually - "interpret" is clearly the right natural-language word here. Maybe something like: "The (first-order) language of set theory is strong enough to describe second-order logic, and the (first-order) ZFC axioms are strong enough to prove many things about it." Really the technical term should be different. It's a minor point, though - alternatively, maybe put a footnote ("This word has a technical meaning which isn't being used here")? $\endgroup$ Mar 15, 2020 at 19:04
  • 1
    $\begingroup$ I think the footnote is the right approach. Thanks. $\endgroup$
    – Asaf Karagila
    Mar 15, 2020 at 19:05
  • 1
    $\begingroup$ Maybe this is a separate question, but how does ZFC interpret or describe second-order logic? Is it just that what would be quantifying over properties (for instance) becomes instead simply quantifying over sets, in some way? $\endgroup$
    – ionchy
    Mar 16, 2020 at 1:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .