Set theoretic concepts in first order logic

Solution 1:

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.

Solution 2:

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)].

Solution 3:

I believe that this post about building blocks may address some of your underlying philosophical inquiry. After that, let me address the specific details in your question:

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).