# Set theoretic concepts in first order logic

I have been reading introductory texts on first order logic (for example, Leary&Kristiansen). All of them used concepts that I have heard in set theory courses - ordered pairs, functions, bijections, isomorphism and so on.

I have read a lot of material in Math.StackExchange on set theory and first order logic and their interplay. I understand that we cannot define mathematics from nothing - we have to have primitive concepts. My problem is with understanding which are primitive concepts and which are not. Of course, different books might take these to be different, but still - maybe there are commonly accepted principles and notions that noone doubts.

For example, I am willing to accept that strings exist, that they can be glued together or separated, also I am willing to accept recursion and induction. I am also willing to accept counting numbers (which could as well be infinite: I, II, III, ...).

Question 1: As far as I have read and understood - sets in first order logic are different than those in set theory. But how so? At first I thought that it is because sets in first order logic are finite by definition and are basically just collections of finite terms, strings, and so on. Then, paradoxes that arise in set theory due to infinities do not arise in logic. But on the other hand, we use counting numbers and then, for example, the number of terms can be infinite.

Question 2: Are sets, ordered pairs, functions, bijections - primitive notions (by primitive notion I understand concept that is not defined) in first order logic (at least in the one that most of the mathematicians use)?

Question 3: If sets, ordered pairs, functions are indeed primitive notions then are they different from set theoretical definitions? If yes, then in which way? If no, then why define these concepts once again in set theory if we had them in the language of set theory anyway?

Question 4: If sets, ordered pairs, functions are not primitive notions in first order logic then how are they defined?

• In ZFC, the only primitive notions are set and the element-of relation. We can build up first order logic with these. Commented Apr 4, 2018 at 6:52
• @Berci I always felt that ZFC is built upon first order language. Can you please give me some textbook or reference to read about ZFC without first order logic and then first order logic from such ZFC? Commented Apr 4, 2018 at 6:56
• Well, it's a kind of 'chicken or egg' problem.. Commented Apr 4, 2018 at 7:55
• I recommend these two answers by Carl Mummert: math.stackexchange.com/a/1592730/305738 and math.stackexchange.com/a/1592209/305738 Commented Apr 4, 2018 at 8:11
• @Daniels Krimans: ZFC, by definition, is defined using first order logic. But the more general semi-formal theory of sets, as used by the majority of mathematicians who cannot name the ZFC axioms, is just like any other semi-formal mathematical theory, which can be understood without knowing anything about first-order logic. That kind of semi-formal set theory is often the metatheory that authors assume when they study first-order logic. This is no different, of course, than studying any other mathematical topic. Commented Apr 4, 2018 at 11:06

The questions assumes that there is some notion of "set" in first-order logic itself, but there is not. We use sets to study first-order logic, particularly the semantics (models) aspect. But these are part of the metatheory we use to study logic, not really part of "first order logic". For example, if we look at the first-order theory of groups, there is nothing in it about "sets".

If we look more at the syntactic (proofs) side, we can get by with a much weaker metatheory, one which only needs to manipulate strings. Theories often used for this purpose include Peano arithmetic and the weaker Primitive Recursive Arithmetic. In these theories, there aren't directly any "sets", just natural numbers, although these theories have ways to talk about functions from numbers to numbers and, as such, indirectly talk about some kinds of sets.

The really fundamental concepts in first-order logic are alphabet, signature, language, theory, formal proofs/derivability, and models/satisfiability. All but the last of these can be very satisfactorily studied using Peano arithmetic as our metatheory. Once we move to studying models - which are again a fundamental part of first-order logic - we usually find it more satisfactory to work in a stronger metatheory that is able to construct and work with models more directly.

## On the nature of logic

The other thing about this particular question: it is common for people first studying mathematical logic to think that the main purpose of studying logic is to find the most primitive objects of mathematics and then to rebuild mathematics from these primitive objects -- this is the foundational aspect of logic.

That is indeed one aspect of mathematical logic, but not the only one by far. Historically, the foundational aspect was of particular interest around the turn of the 20th century, but it is not of such primary interest any longer. From the contemporary viewpoint, another purpose of mathematical logic is simply to understand mathematics better by using techniques that have come to be called "mathematical logic". I think that, for historical reasons and because it's interesting, the foundational aspect tends to be slightly over-emphasized in introductory materials.

For example, another common and important thread in mathematical logic is definability - the study of which aspects of mathematical structures can be expressed in which formal languages. This thread runs very heavily through computability theory and model theory, and is also found in set theory and proof theory.

Yet another common thread is an interest in the mathematical objects of logic for their own sake: some logicians study sets because they like sets, not as a way to study foundations. Some study computability because they like computability, without much interest in philosophical aspects. Some research topics in model theory are essentially indistinguishable from abstract algebra or analysis.

The foundational aspect of logic is still important, of course, and there are still people who work primarily on foundations. But the idea that mathematical logic will provide some sort of rock-solid foundation to all the rest of mathematics is not really part of the contemporary study of foundations. Instead we think about a range of theories, each suitable for its own foundational purpose. For studying the semantics of first-order logic, we need a theory that includes some way to handle models, which are particular kinds of sets.

As the shift from a mainly foundational viewpoint to a more broadly mathematical viewpoint occurred, several mathematical logic books from the mid 20th century included detailed explanations in the introduction about why they use advanced mathematical methods to study logic. One good treatment of this topic is in Monk's logic book, which can be found pretty cheaply these days.

The purpose of this section, which may be a slight digression, is to explain that one reason that it is not easy to see how logic is developed "out of nothing" from absolutely first principles is that, often, that isn't the goal that contemporary logicians have in discussing logic. They aren't necessarily trying to develop logic and mathematics from absolutely first principles.

• By reading you and Monk's logic book I think that I understood that mathematical logic absolutely has the right to use full formal set theory in its discussion. I think I also understood that I am confused about the first principles and semi-formal logic. Could you please give some reference texts about minimum semi-formal logic necessary to lay foundations of modern set theory which is then used to formally treat logic? Commented Apr 11, 2018 at 5:55
• The challenge is that, because the system that most mathematicians use is only semi-formal, there is no detailed accounting of exactly what it includes. I expect that, for most mathematicians, the semi-formal system actually gets stronger over time, as they learn more mathematical techniques. So, unfortunately, I don't have any references to point to. I think this is something that mathematicians learn solely through experience. Commented Apr 11, 2018 at 10:27

Logic (like FOL) presupposes (natural) language and the "basic machinery" of language: the concepts related to syntax (like e.g.: string, (meaningful) expression, etc.) and to semantics (like e.g.: truth value, reference, etc.) as well as the mechanism of counting.

In this way, we can develop a semi-formal treatment of logic, in the same way used for every scientific theory: geometry, arithmetic, physics (see e.g. Aristotle's Logic).

Example : in this context, we do not need set theory to understand the concept of function (i.e. a correspondence between objects of a domain and objects of a co-domain) or that of (binary) relation (like that between father and son).

When we want to develop logic as a full mathematical discipline, we have to formalize it, developing the theory of logical system with the tool of mathematics.

In order to formalize syntax and semantics we have to define them as precise mathematical objects: we can do this using (a limited amount of) set theory, like Hereditarily finite sets [see e.g. M.Fitting, Incompleteness in the Land of Sets (2007)] or arithmetic, like some subsystems of Second-order arithmetic [see: S.Simpson, Subsystems of second-order arithmetic (2009)].

• Can you please recommend some textbook that considers in detail what is presupposed in studying logic and specifically considers development of semi-formal logic? I think that I understood that mathematical logic as subject on its own just as complex analysis has the right to use full machinery of, say, ZFC. That means I am actually interested not in the logic but semi-formal logic (maybe metalogic)? Commented Apr 11, 2018 at 5:41

For example, I am willing to accept that strings exist, that they can be glued together or separated, also I am willing to accept recursion and induction. I am also willing to accept counting numbers (which could as well be infinite: I, II, III, ...).

Perhaps surprisingly, one can talk about (finite binary) strings using a very very weak system, such as the Theory of Concatenation (TC). As shown in the linked post, TC is so weak that it cannot even prove cancellation. Let TC* be TC plus a suitable induction schema, just like Peano Arithmetic (PA) can be axiomatized as PA plus induction. TC* can then prove basically all the basic properties of strings, within which you can easily encode the natural numbers.

It may also be surprising that TC, despite being so weak, is essentially incomplete, meaning that no computable extension of it can prove or disprove every sentence over TC. This is roughly because TC is able to express any given instance of the halting problem, and able to verify the output of a given program that halts on the given input. (Details here.)

As far as I have read and understood - sets in first order logic are different than those in set theory.

Usually, sets that are constructed in basic logic are very nice sets. Often they are arithmetical (as defined in the building blocks post). This also means that a lot of fundamental results in logic can be proven within ACA, including the unsolvability of the halting problem, Godel's incompleteness theorem, Henkin's proof of the semantic completeness theorem, and so on.

But in higher logic, especially when investigating ZFC set theory, logicians typically work within ZFC as the meta-system.

At first I thought that it is because sets in first order logic are finite by definition and are basically just collections of finite terms, strings, and so on. Then, paradoxes that arise in set theory due to infinities do not arise in logic. But on the other hand, we use counting numbers and then, for example, the number of terms can be infinite.

This seems to be based on a serious misconception. As you noted, there are infinitely many finite strings. Furthermore, paradoxes do not 'arise' due to infinity. They arise when people make assumptions for nebulous concepts that turn out to be inconsistent. This happened with naive set theory, in which Russell's paradox yields a contradiction without any infinite set.

Many logicians believe that ACA is conceptually sound, and we certainly do not expect any proof of contradiction over ACA. Some logicians doubt ZFC's arithmetical soundness, and there is no clear philosophical justification for its meaningfulness, but nobody has yet found any evidence to indicate a problem. Some of them even doubt $Π^1_1$-CA, which is an impredicative fragment of second-order arithmetic (see this and this regarding predicativity), unlike ACA.

Are sets, ordered pairs, functions, bijections - primitive notions (by primitive notion I understand concept that is not defined) in first order logic (at least in the one that most of the mathematicians use)?

As Carl implies, these are primitive notions for most mathematicians who do not really care about foundational issues. From a foundation-agnostic view, it is fair to consider tuples and sets and functions to be primitive. Not bijections (or injections), because they can be defined as special kinds of functions. Of course, it is dangerous to say this, otherwise Russell would ask what prevents construction of his famous set $\{ x : x \notin x \}$. So ultimately one still has to think about foundations, like it or not.

But nobody actually cares how tuples or functions are encoded in ZFC set theory, for very good reason: we only care that we can manipulate them as expected. For tuples, we just need tuple formation and projection. For functions, we just need function construction and application.

If sets, ordered pairs, functions are not primitive notions in first order logic then how are they defined?

If it is not yet clear, first-order logic is merely the logical language, and has nothing to do with sets or pairs or functions. ZFC set theory is a first-order theory because "$\in$" can be treated as a binary predicate-symbol. There are other first-order theories too, such as PA and the theory of groups and the theory of linear orders.

But these notions can be considered primitive in the mathematical field called mathematical logic, though if you want to be precise about what sets and functions you can construct, you have to decide on your foundational system. Also, most people (even set theorists) do not work within pure ZFC but within a more informal system that supports on-the-fly definitorial expansion and even inductive definitions (details here).

It is worth adding to the other answers that in fact, while it is conventional to talk about sets when giving the metatheory of first-order logic, it just isn't necessary. (A lot of set talk in mathematics is unnecessary overkill.)

1. Instead of talking of consequence as a relation between a set of wffs (premisses) and a wff (the conclusion), we can treat it as a relation between wffs (plural) and a wff.
2. Instead of talking of the domain of quantification as one thing, a set of objects, we can take the quantifiers as ranging over things, plural.
3. Instead of talking of the interpretation of a predicate as a set of things (the extension of the predicate), we can talk of the things (plural) that satisfy the predicate.

And so it goes (fine print: take 'plural' to cover, as necessary, the zero and singular cases).

It is convenient and familiar to trade in plural talk for set talk; but it isn't necessary. We can take the plurals seriously (indeed sometimes we have to -- e.g. we can't take the domain of quantification of set theory to be a set, for the familiar reason that there is no set of all sets). And if we like, we can theorise about our familiar first order logic in a formal metatheory with a plural logic, without invoking sets at all.

• Or we can use some kind of type theory where the notion of typing is interpreted as a categorization, and so we need not actually have the 'completed' collection. By the way, in my linked post on building blocks I mentioned your PDF about ACA as a natural stopping point for predicative arithmetic. I wonder what you think about the natural higher-order extension; namely each object's defining formula can only quantify over objects of lower order, just like sets in ACA can only quantify over naturals. The extension of course has the full higher-order induction schema, so it is stronger than ACA. Commented Apr 5, 2018 at 5:24
• @user21820 "We can use some kind of type theory ..." Do you have a nice reference where this is actually done? "What [do I] think about the natural higher-order extension of ACA?" Good question. To be honest, I haven't really thought more about ACA and related matters since that note that you link to -- I got distracted by other projects! Commented Apr 5, 2018 at 17:33
• I don't have a nice reference, but there are three main approaches: (1) Use a type theory with typing judgements such as in Calculus of Constructions, where "$x:S$" is not a statement (so no truth value) but a judgement (so either derivable or not), and hence one cannot form a boolean expression that means "$x$ is of type $S$". (2) Use Kleene's 3-valued logic, so "$x \in S$" may be true/false/null (See this post). (3) Use intuitionistic logic, so that "$x \notin S$" is weaker. Commented Apr 6, 2018 at 3:34
• All three approaches can be considered compatible with 'plurality', in the sense that while you can happily quantify over types, you do not always have boolean (true/false) membership in a type, and so membership is not captured by a boolean relation. As for my inquiry about predicative higher-order arithmetic, I am very interested to know how strong it is, because we can philosophically justify it as follows: If we restrict the induction schema to first-order then it is a conservative extension of PA. And the full higher-order induction schema can be justified by meta-induction in ACA. Commented Apr 6, 2018 at 3:40
• And, if you prefer, we can continue discussion in the Logic chat-room. =) Commented Apr 6, 2018 at 3:42

If you're at all interested in semantics — that is, interpreting logical statements as referring to mathematical objects in some universe — then it is most natural to develop first-order logic within that same mathematical universe.

When doing so, things like "set", "natural number", "function", and so forth all mean the same thing they would mean if you were studying any other subject: they're provided to you by the context in which you're doing mathematics, not something you need to postulate and axiomatize from scratch.

Note, however, that sometimes a thing people do in first-order logic that could give rise to confusion is to consider a first-order theory of sets.

When you are doing this, you are in the unfamiliar situation of simultaneously contemplating two completely different notions of set:

• The usual notion, referring to the sets of the universe
• The objects of the theory you're studying

When doing this, it is very easy to mix the two notions up.

I've had this same question for a while and I have been working to build up a description of the language of first order logic which is explicit about which "informal" mathematical concepts are required to define the language of first order logic, and then subsequently ZFC so that these and other mathematical concepts can be formalized. That said, I am by no means an expert. This is just what I've come up with so far.

An important caveat: I am explicitly trying to avoid any semantics. I'm interested in seeing how much can be done with syntax alone, so if you see a notable absence of semantics and perhaps sense an overzeal for syntactic rigor this is intentional. I'm also focused on the foundational aspect of first order logic which is I think a helpful clarification in light of Carl Mummert's answer.

First I'll give paragraphs with what informal concepts I think we need in context, then I'll just give a list extracting the foundational informal concepts required.

• We're going to need an informal concept of the natural numbers $$\mathbb{N}$$. This is because when we try to talk about strings of symbols we are going to need to talk about things like "the first element of a string" or the "second element of a string" or $$n$$-ary function symbols.
• We need to be able to talk about informal objects. The most important informal concept about an object is that we can tell if one object is the same or different from another object. Symbols will then be certain types of objects.
• We'll similarly need an informal concept of a set of objects. The set of symbols is called Symb. For first order logic we probably have $$n$$-ary predicate or function symbols so this means that already Symb may be an infinite set, so we already need infinite sets. We'll also need informal versions of typical set concepts like set union, intersection, and subtraction to do various metalogical or metasyntax proofs.
• We will need informal functions. There will be many uses for functions. In fact one use will be to define the complexity of a formula (the depth, or length, for example). If we have a formula $$\phi$$ then it might be the case that $$\phi \equiv \pi \implies \theta$$, but it might also be the case that $$\phi \equiv \pi' \implies \theta'$$ with $$\pi\not\equiv \pi'$$ and $$\theta\not\equiv\theta'$$. If this were the case then it would not be possible to give a well-defined definition for the complexity $$C(\phi)$$. Nonetheless, it will still be possible to define the complexity as a relation on the formulas and the natural numbers. Of course unique readability guarantees that this function will indeed be well-defined, but to discuss the concept I think it will be necessary to introduce informal relations as the foundational concept and informal functions as special types of relations. Other informal uses of functions will be more straightforward.
• We of course need an informal concept of strings of symbols. I think the foundational concept here can be the informal concept of finite ordered lists of objects. Let $$\bar{n} = \{0, \ldots, n-1\}$$ denote the informal set of natural numbers less than $$n$$ and let $$\Sigma$$ be an informal set of informal objects. A finite ordered list over $$\Sigma$$ is a informal function from $$\bar{n}\to \Sigma$$. The informal set of all finite ordered lists over $$\Sigma$$ is $$\Sigma^*$$. Strings then arise as $$\textbf{Str} = \textbf{Symb}^*$$. Perhaps we could use an informal notion of ordered tuples where tuples are defined as in set theory, but then it would be much more difficult to define the $$i^{\text{th}}$$ element of a list the length of a list.
• We'll require concatenation of strings. I think it might be possible to define concatenation as an informal function $$\textbf{Str}\times \textbf{Str} \to \textbf{Str}$$. I guess we might need an informal Cartesian product for that, or at least informal notion of a function or relation between more than just two sets.
• In proving various things about strings, manipulating strings, and performing metalogical proof deduction we will require heavy use of informal strong mathematical induction
• It's almost to obvious to say, but an informal understanding of logic is required as well. For example we ought to informally understand that if $$A$$ implies $$C$$ and $$B$$ implies $$C$$, that if we know $$A$$ or $$B$$ to be the case then $$C$$ is the case. Such informal logic will be used in various metalogical or metasyntactic proofs.

Extracted list of bare-minimum necessary informal concepts for first order logic.

• Informal understanding of the natural number $$\mathbb{N}$$.
• Informal understanding of objects
• Informal understanding of sets of informal objects and simple set operations such as set union, intersection, and subtraction.
• Informal understanding of relations between informal sets.
• Informal understanding of strong induction over the informal natural numbers.
• Informal basic logic

To couch my view in your questions:

(1) Right.. The informal sets used for first order logic may be infinite as described above, so it is not finiteness that saves them from the pitfalls of naive set theory (which formal set theory solved). I think the paradoxes of naive set theory are avoided in informal set theory for first order logic because there is no need to consider any sorts of pathological sets to write down the syntax and manipulation rules for first order logic. But I'm not sure about this. And if one begins doing crazy metalogic stuff I could imagine this assumption beginning to break down.

(2) Yes, on my understanding, informal versions of objects, sets, ordered lists, relations are some of the primitive concepts required to describe/define first order logic.

(3) Ok, in my opinion, the informal versions of sets, etc. differ from the formal versions in the following important ways. To understand formal set union as defined in ZFC it is necessary to first understand the language of first order logic and understand what some of the axioms of ZFC say. To understand informal set union you merely need to understand the idea that if you have two groups of objects you can make one big group with all the objects. Furthermore, you can even "prove" things like DeMorgan's law and such all using the informal understanding of sets. That is, I learned that $$(A\cup B)' = A' \cap B'$$ before I learned set theory. The essential difference is that the informal concept is what we have come to understand as humans living in the world, while the formal concept is something that we only understand or prove after some time playing the first order logic string manipulation game. That said, you've already accepted that some informal concepts are necessary for first order logic. The of this post then, from a foundations perspective, is to at least codify then minimal sets of informal concepts needed to bootstrap ourselves up to formal mathematics.

(4) N/A in my opinion.

edit: I think more is needed. In addition to induction on the natural numbers, I think it is necessary to have an informal understanding of structural induction, the structural inductive closure and structural recursion. The structural inductive closure and structural recursion are necessary to understand how formulas are built up from atomic formulas and rules for constructing new formulas. Structural induction is necessary to understand metatheorems on recursively defined structures.