5

I have never been formally trained in logic and philosophy. I became increasingly interested in the foundation of mathematics after I graduated from university.

Recently, I've been self-studying ZFC set theory and have realized that mathematical reasoning requires propositional logic, which is even more fundamental than set theory itself. I came upon with the so-called first order logic from this wikipedia page. It says that first order logic is the standard formalization Peano axioms of arithmetic and ZFC axioms of set theory, which I believe is the foundation of mathematics.

But after reading a few paragraphs of the "Syntax" section, I became very confused. It seems to me that lots of the definitions in formation rules in first order logic need the concept of set and natural numbers in the first place. Doesn't this seem like a loop?

Maybe one can make some compromise by using the term "collection" (in the plain English sense) instead of using the word set and hoping that there's a consensus on what collections mean, but still one cannot avert using integers.

Maybe I should rephrase my question in another way: what exactly is the relation between first order logic and ZFC axioms? Which one is more fundamental?

Improve this question
4
  • 3
    Your observation is correct, one does need some basic arithmetic and set concepts to set up a first order formal system, this is called meta-theory. The idea is that while they are needed to explain the workings of such a system they are not needed for the workings themselves, it is supposed to work like an automaton generating theorems. In any case, the minimally needed meta-theory is relatively modest, it is much less than ZFC or even Peano arithmetic, but it is more than "pure logic".
    – Conifold
    Commented Dec 18, 2022 at 20:58
  • 2
    The plain sense notion of a collection is what led to Russell's paradox. This was one of the main motivations for using logic to axiomatise set theory. But provided we don't go along with the logicist supposition that all of mathematics is reducible to logic, which is no longer a popular idea, then there is no reason to consider either set theory or logic to be more fundamental. Or category theory for that matter.
    – Bumble
    Commented Dec 18, 2022 at 21:10
  • You can see also the post Set theoretic concepts in first order logic as well as When does the set enter set theory? and Are the natural numbers implicit in the construction of first-order logic?
    – Mauro ALLEGRANZA
    Commented Dec 19, 2022 at 10:45
  • Kristian’s answer is more informed than mine, but I’d like to add a few ideas for contemplation. 1. I have found thinking of logic as primary to sets as very, very helpful in studying logic. Maybe at a more advanced level one can afford to begin questioning this, but at least so far in my studies, I was much more bewildered and confused about the circularity of things like logic and sets, until I became more familiar with modern conventions. I can’t remember who, but someone introduced me to a very useful term. First-order logic is a specification language. The variables represent *something
    – Julius Hamilton
    Commented Apr 3 at 15:16

2 Answers 2

Reset to default
2

From Benacerraf's identification problem (which undermines or at least underdetermines the reduction of natural numbers to sets) to the charge that second-order logic is "set theory in sheep's clothing, through the conflict between mathematical intuitionism and logicism and Platonism, we find examples of how logic isn't more fundamental than set theory, and perhaps set theory isn't more fundamental than logic, then, either.

In essays about the multiverse of set theories, no less, we find statements such as:

Part of the reason for this is a lemma of Gaifman’s, which asserts that if j: V → V is Σ1-elementary, then it is Σn-elementary for every meta-theoretic natural number n, by an induction carried out in the meta-theory. ... This statement is a theorem scheme, a separate statement for each meta-theoretic natural number n. ... Thus, the embedding j we produce arises via (∗) from an injection on At, and our argument shows as a theorem scheme that any embedding arising this way is Σn-elementary for any meta-theoretic natural number n. ...

So consider coherentism in epistemology, which is in some tension with the notion that logic or set theory or really any domain-of-discourse is "fundamental." One way to interpret coherentism is graph-theoretically, yet graph theory is, so it would seem, a subdiscipline of mathematics. But then if the regress problem in epistemology altogether admits of graph-theoretic representations, then do we say that graph theory is prior to epistemology, which would then be prior to specific theories of logic, yet then prior to a set-theoretic grounding for all mathematics? Don't we need to know graph theory to apply it—to epistemology or anything else?

Improve this answer
4
  • 1
    Why is this answer not useful? The OP asked if logic or set theory is more fundamental, I provided a bunch of citations indicating neither is, which is a possible answer to the question, after all. EDIT: Also, why was the OP downvoted? It's a legitimate question and the poster showed that they had been seriously thinking about it in the course of their studies, plus the site sidebar doesn't bring up any obvious duplicates, so...
    – Kristian Berry
    Commented Dec 18, 2022 at 20:29
  • "Benacerraf's identification problem" How does it show logic isn't more fundamental than set theory? "the charge that second-order logic..." OP asks about first-order logic. "the conflict between mathematical intuitionism and logicism and Platonism" How does it show logic isn't more fundamental than set theory? How does the quote about embeddings show logic isn't more fundamental than set theory? "So consider coherentism..." How is this relevant to OP's question?
    – user76284
    Commented Jan 9, 2023 at 4:18
  • 1
    @user76284, the ID problem is the context of so-called "junk theorems." If the justification of {{{}}} = 2, etc. is not deductive, is it logical? SOL is mentioned as relevant to the general question which the OP ref. to FOL is a specification of (I would've been inclined to edit the SOL ref. out but the OP poster did accept my answer as relevant...). Coherentism is relevant because it has to do with the nature of the OP's whole inquiry (foundationalism). Embedding axioms are fundamental for their incorporating set theories, but they're not always, if ever, reducible to FOL considerations.
    – Kristian Berry
    Commented Jan 9, 2023 at 12:25
  • @user76284, perhaps the SOL ref. is more relevant than even I supposed, though. "FOL is more fundamental than set theory," is not an FOL sentence. "Set theory is more fundamental than FOL," is not a first-order set-theoretic sentence. The nature of the OP's question seems caught up in the opening of the SOL question, then.
    – Kristian Berry
    Commented Jan 9, 2023 at 12:56
1

It seems to me that lots of the definitions in formation rules in first order logic need the concept of set and natural numbers in the first place.

They do not. Consider the following formation rules:

  • If A is a formula and B is a formula, A ∧ B is a formula.
  • If A is a formula and B is a formula, A ∨ B is a formula.
  • If A is a formula and B is a formula, A → B is a formula.

These rules do not use the concept of set. "is a formula" is a predicate. It is unnecessary to assume that there is a set of all things that satisfy a predicate (e.g., a set of all formulas).

what exactly is the relation between first order logic and ZFC axioms?

ZFC axioms are expressed in the language of first-order logic. (ZFC is a first-order theory.)

Improve this answer
3
  • Thanks for your explanation. I followed "The Joy of Sets", which doesn't explain anything about first order logic. The wikipedia page is obscure and full of jargons. What textbook do you recommend for students who want to study more about first order logic?
    – Xenomorph
    Commented Dec 19, 2022 at 5:25
  • Hi. What do you think on this post? mathoverflow.net/questions/248965/…
    – Xenomorph
    Commented Dec 19, 2022 at 5:31
  • @LibertarianFeudalistBot I don't have a particular textbook recommendation, but see this question. The post you linked to is about models (Wikipedia, nLab).
    – user76284
    Commented Dec 19, 2022 at 6:10

You must log in to answer this question.

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