Something I’ve been wondering for a while now: if concepts like “natural number” and “set” can’t be adequately pinned down using first-order logic, how the heck do we know what those words mean? Take “natural number” as a given. The phrase “set of natural numbers” seems perfectly meaningful, and I feel like I can clearly imagine its meaning, but I can’t see how to define it.
The best approach that comes to my mind: for all n, it’s easy enough to define the concept “set of natural numbers less than n”, so you simply need to take the limit of this concept as n approaches infinity. But the “limit of a concept” is not obviously a well-defined notion.
I don’t think “set” has a fixed meaning in modern mathematics. At least one prominent set theorist talks about the set-theoretic multiverse, which roughly speaking means that instead of choosing particular truth values of various statements about sets such as the continuum hypothesis, set theorists study all possible set theories given by all possible (consistent) assignments of truth values to various statements about sets, and look at relationships between these set theories.
In practice, it’s not actually a big deal that “set” doesn’t have a fixed meaning. Most of what we need out of the notion of “set” is the ability to perform certain operations, e.g. take power sets, that have certain properties. In other words, we need a certain set of axioms, e.g. the ZF axioms, to hold. Whether or not those axioms have a unique model is less important than whether or not they’re consistent (that is, have at least one model).
There are also some mathematicians (strict finitists) who reject the existence of the “set of natural numbers”…
The standard approach in foundations of mathematics is to consider a special first order theory called ZFC, it describes sets, whose elements are themselves sets. Inside this theory you can encode all other mathematics using sets for example by the Von Neumann construction of ordinals. Then you can restrict yourself to the finite ordinals and verify the Peano axioms, including the principle of induction which you can now formulate using sets. So everything turns out to be unique and pinned down inside your set theory.
What about pinning down your set theory? Well most mathematicians don’t worry about set theory. The set theorists seem to be quite fine with it not being pinned down, but are sometimes need to be careful about inside which model they are working. A very useful consequence of set theory not being pinned down is a construction called forcing, which allows you to prove the independence of ZFC from the continuum hypothesis (there not being a set of reals which can’t be bijected into neither the naturals nor the reals). What you do in this construction is that you work inside a model of set theory which is countable, which allows you to define a special kind of subset that does not exist in the original model but can be used to create a new model where certain properties fail to hold.
Some people want to use second order logic, talking about properties as primitive objects, to get this kind of pinpointing instead. The standard criticism to this is that you need to formalise what you mean by properties through axioms and rules of inference, giving you something quite similar to set theory. I’m not very familiar with second order logic so can’t elaborate on the differences or similarities, but it does look like the next post in this sequence will be about it.
The thing about ZFC is that it doesn’t feel like “the definition” of a set. It seems like the notion of a “set” or a “property” came first, and then we came up with ZFC as a way of approximating that notion. There are statements about sets that are independent of ZFC, and this seems more like a shortcoming of ZFC than a shortcoming of the very concept of a set; perhaps we could come up with a philosophical definition of the word “set” that pins the concept down precisely, even if it means resorting to subjective concepts like simplicity or usefulness.
On the other hand, the word “set” doesn’t seem to be as well-defined as we would like it to be. I doubt that there is one unique concept that you could call “the set of all real numbers”, since this concept behaves different ways in different set theories, and I see no basis on which to say one set theory or another is “incorrect”.
Mathematics and logic are part of a strategy that I’ll call “formalization”. Informal speech leans on (human) biological capabilities. We communicate ideas, including ideas like “natural number” and “set” using informal speech, which does not depend on definitions. Informal speech is not quite pointing and grunting, but pointing and grunting is perhaps a useful cartoon of it. If I point and grunt to a dead leaf, that does not necessarily pin down any particular concept such as “dead leaves”. It could just as well indicate the concept “things which are dry on top and wet on bottom”—including armpits. There’s a Talmudic story about a debate that might be relevant here. Nevertheless (by shared biology) informal communication is possible.
In executing the strategy of formalization, we do some informal argumentation to justify and/or attach meaning to certain symbols and/or premises and/or rules. Then we do a chain of formal manipulations. Then we do some informal argumentation to interpret the result.
Model theory is a particular strategy of justifying and/or attaching meaning to things. It consists of discussing things called “models”, possibly using counterfactuals or possible worlds as intuition boosters. Then it defines the meaning of some strings of symbols first by reference to particular models, and then “validity” by reference to all possible models, and argues that certain rules for manipulating (e.g. simplifying) strings of symbols are “validity-preserving”.
Model theory is compelling, perhaps because it seems to offer “thicker” foundations. But you do not have to go through model theory in order to do the strategy of formalization. You can justify and/or attach meaning to your formal symbols and/or rules directly. A simple example is if you write down sequences of symbols, explain how to “pronounce” them, and then say “I take these axioms to be self-evident.”.
One problem with model theory from my perspective is that it puts too much in the metatheory (the informal argumentation around the formal symbol-manipulation). Set theory seems to me like something that should be in the formal (even, machine-checkable?) part, not in the metatheory. It’s certainly possible to have two layers of formality, which in principle I have no objection to, but model theoretical arguments often seem to neglect the (informal) work to justify and attach meaning to the outer layer. Furthermore, making the formal part more complicated has costs.
To me, it’s all about reflective equilibrium. In our minds, we have this idea about what a “natural number” is. We care about this idea, and want to do something using it. However, when we realize that we can’t describe it, perhaps we worry that we are just completely confused, and thinking of something that has no connection to reality, or maybe doesn’t even make sense in theory.
However, it turns out that we do have a good idea of what the natural numbers are, in theory...a system described by the Peano axioms. These are given in second-order logic, but, like first-order logic, the semantics are built in to how we think about collections of things. If you can’t pin down what you’re talking about with axioms, it’s a pretty clear sign that you’re confused.
However, finding actual (syntactic) inference rules to deal with collections of things proved tricky. Many people’s innate idea of how collections of things work come out to something like naive set theory. In 1901, Bertrand Russell found a flaw in the lens...Russell’s paradox. So, to keep reflective equilibrium, mathematicians had to think of new ways of dealing with collections. And this project yielded the ZFC axioms. These can be translated into inference rules / axioms for second-order logic, and personally that’s what I’d prefer to do (but I haven’t had the time yet to formalize all of my own mathematical intuitions).
Now, as a consequence of Gödel’s first incompleteness theorem (there are actually two, only the first is discussed in the original post), no system of second-order logic can prove all truths about arithmetic. Since we are able to pin down exactly one model of the natural numbers using second-order logic, that means that no computable set of valid inference rules for second-order logic is complete. So we pick out as many inference rules as we need for a certain problem, check with our intuition that they are valid, and press on.
If someone found an inconsistency in ZFC, we’d know that our intuition wasn’t good enough, and we’d update to different axioms. And this is why, sometimes, we should definitely use first-order Peano arithmetic...because it’s provably weaker than ZFC, so we see it as more likely to be consistent, since our intuitions about numbers are stronger than our intuitions about groups of things, especially infinite groups of things.
All of this talk can be better formalized with ordinal analysis, but I’m still just beginning to learn about that myself, and, as I hinted at before, I don’t think I could formally describe a system of second-order logic yet. I’m busy with a lot of things right now, and, as much as I enjoy studying math, I don’t have the time.
Something I’ve been wondering for a while now: if concepts like “natural number” and “set” can’t be adequately pinned down using first-order logic, how the heck do we know what those words mean? Take “natural number” as a given. The phrase “set of natural numbers” seems perfectly meaningful, and I feel like I can clearly imagine its meaning, but I can’t see how to define it.
The best approach that comes to my mind: for all n, it’s easy enough to define the concept “set of natural numbers less than n”, so you simply need to take the limit of this concept as n approaches infinity. But the “limit of a concept” is not obviously a well-defined notion.
I don’t think “set” has a fixed meaning in modern mathematics. At least one prominent set theorist talks about the set-theoretic multiverse, which roughly speaking means that instead of choosing particular truth values of various statements about sets such as the continuum hypothesis, set theorists study all possible set theories given by all possible (consistent) assignments of truth values to various statements about sets, and look at relationships between these set theories.
In practice, it’s not actually a big deal that “set” doesn’t have a fixed meaning. Most of what we need out of the notion of “set” is the ability to perform certain operations, e.g. take power sets, that have certain properties. In other words, we need a certain set of axioms, e.g. the ZF axioms, to hold. Whether or not those axioms have a unique model is less important than whether or not they’re consistent (that is, have at least one model).
There are also some mathematicians (strict finitists) who reject the existence of the “set of natural numbers”…
The standard approach in foundations of mathematics is to consider a special first order theory called ZFC, it describes sets, whose elements are themselves sets. Inside this theory you can encode all other mathematics using sets for example by the Von Neumann construction of ordinals. Then you can restrict yourself to the finite ordinals and verify the Peano axioms, including the principle of induction which you can now formulate using sets. So everything turns out to be unique and pinned down inside your set theory.
What about pinning down your set theory? Well most mathematicians don’t worry about set theory. The set theorists seem to be quite fine with it not being pinned down, but are sometimes need to be careful about inside which model they are working. A very useful consequence of set theory not being pinned down is a construction called forcing, which allows you to prove the independence of ZFC from the continuum hypothesis (there not being a set of reals which can’t be bijected into neither the naturals nor the reals). What you do in this construction is that you work inside a model of set theory which is countable, which allows you to define a special kind of subset that does not exist in the original model but can be used to create a new model where certain properties fail to hold.
Some people want to use second order logic, talking about properties as primitive objects, to get this kind of pinpointing instead. The standard criticism to this is that you need to formalise what you mean by properties through axioms and rules of inference, giving you something quite similar to set theory. I’m not very familiar with second order logic so can’t elaborate on the differences or similarities, but it does look like the next post in this sequence will be about it.
The thing about ZFC is that it doesn’t feel like “the definition” of a set. It seems like the notion of a “set” or a “property” came first, and then we came up with ZFC as a way of approximating that notion. There are statements about sets that are independent of ZFC, and this seems more like a shortcoming of ZFC than a shortcoming of the very concept of a set; perhaps we could come up with a philosophical definition of the word “set” that pins the concept down precisely, even if it means resorting to subjective concepts like simplicity or usefulness.
On the other hand, the word “set” doesn’t seem to be as well-defined as we would like it to be. I doubt that there is one unique concept that you could call “the set of all real numbers”, since this concept behaves different ways in different set theories, and I see no basis on which to say one set theory or another is “incorrect”.
Mathematics and logic are part of a strategy that I’ll call “formalization”. Informal speech leans on (human) biological capabilities. We communicate ideas, including ideas like “natural number” and “set” using informal speech, which does not depend on definitions. Informal speech is not quite pointing and grunting, but pointing and grunting is perhaps a useful cartoon of it. If I point and grunt to a dead leaf, that does not necessarily pin down any particular concept such as “dead leaves”. It could just as well indicate the concept “things which are dry on top and wet on bottom”—including armpits. There’s a Talmudic story about a debate that might be relevant here. Nevertheless (by shared biology) informal communication is possible.
In executing the strategy of formalization, we do some informal argumentation to justify and/or attach meaning to certain symbols and/or premises and/or rules. Then we do a chain of formal manipulations. Then we do some informal argumentation to interpret the result.
Model theory is a particular strategy of justifying and/or attaching meaning to things. It consists of discussing things called “models”, possibly using counterfactuals or possible worlds as intuition boosters. Then it defines the meaning of some strings of symbols first by reference to particular models, and then “validity” by reference to all possible models, and argues that certain rules for manipulating (e.g. simplifying) strings of symbols are “validity-preserving”.
Model theory is compelling, perhaps because it seems to offer “thicker” foundations. But you do not have to go through model theory in order to do the strategy of formalization. You can justify and/or attach meaning to your formal symbols and/or rules directly. A simple example is if you write down sequences of symbols, explain how to “pronounce” them, and then say “I take these axioms to be self-evident.”.
One problem with model theory from my perspective is that it puts too much in the metatheory (the informal argumentation around the formal symbol-manipulation). Set theory seems to me like something that should be in the formal (even, machine-checkable?) part, not in the metatheory. It’s certainly possible to have two layers of formality, which in principle I have no objection to, but model theoretical arguments often seem to neglect the (informal) work to justify and attach meaning to the outer layer. Furthermore, making the formal part more complicated has costs.
I think this paper by Simpson: Partial Realizations of Hilbert’s Program might be illuminating.
I guess I was confused about your question.
To me, it’s all about reflective equilibrium. In our minds, we have this idea about what a “natural number” is. We care about this idea, and want to do something using it. However, when we realize that we can’t describe it, perhaps we worry that we are just completely confused, and thinking of something that has no connection to reality, or maybe doesn’t even make sense in theory.
However, it turns out that we do have a good idea of what the natural numbers are, in theory...a system described by the Peano axioms. These are given in second-order logic, but, like first-order logic, the semantics are built in to how we think about collections of things. If you can’t pin down what you’re talking about with axioms, it’s a pretty clear sign that you’re confused.
However, finding actual (syntactic) inference rules to deal with collections of things proved tricky. Many people’s innate idea of how collections of things work come out to something like naive set theory. In 1901, Bertrand Russell found a flaw in the lens...Russell’s paradox. So, to keep reflective equilibrium, mathematicians had to think of new ways of dealing with collections. And this project yielded the ZFC axioms. These can be translated into inference rules / axioms for second-order logic, and personally that’s what I’d prefer to do (but I haven’t had the time yet to formalize all of my own mathematical intuitions).
Now, as a consequence of Gödel’s first incompleteness theorem (there are actually two, only the first is discussed in the original post), no system of second-order logic can prove all truths about arithmetic. Since we are able to pin down exactly one model of the natural numbers using second-order logic, that means that no computable set of valid inference rules for second-order logic is complete. So we pick out as many inference rules as we need for a certain problem, check with our intuition that they are valid, and press on.
If someone found an inconsistency in ZFC, we’d know that our intuition wasn’t good enough, and we’d update to different axioms. And this is why, sometimes, we should definitely use first-order Peano arithmetic...because it’s provably weaker than ZFC, so we see it as more likely to be consistent, since our intuitions about numbers are stronger than our intuitions about groups of things, especially infinite groups of things.
All of this talk can be better formalized with ordinal analysis, but I’m still just beginning to learn about that myself, and, as I hinted at before, I don’t think I could formally describe a system of second-order logic yet. I’m busy with a lot of things right now, and, as much as I enjoy studying math, I don’t have the time.
Second-order logic.
Second-order logic does not provide a definition of the term “set”.