Set-theoretic definition of natural numbers
Encyclopedia
Several ways have been proposed to define the natural number
s using set theory
.
are defined recursively by 0 = {} (the empty set) and n + 1 = n ∪ {n}. Then n = {0, 1, ..., n − 1} for each natural number n. The
first few numbers defined this way are 0 = {}, 1 = {0}, 2 = {0,1}.
The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ {n}. (For the existence of such a set we need an Axiom of Infinity
.) The structure (N,0,S) is a model of Peano arithmetic.
The set N and its elements, when constructed this way, are examples of von Neumann ordinals.
each proposed the following definition. Informally, each natural number n is defined as the set whose members each have n elements. More formally, a natural number is the equivalence class of all sets under the equivalence relation
of equinumerosity
. This may appear circular but is not.
Even more formally, first define 0 as
(this is the set whose only element is the empty set
). Then given any set A, define:
σ(A) is the set obtained by adding a new element y to every member x of A. This
is a set-theoretic operationalization of the successor function. With the function σ in hand, we can say 1 = 
, 2 = 
, 3 = 
, and so forth. This definition has the desired effect: the 3 we have just defined actually is the set whose members all have three elements.
This definition works in naive set theory
, type theory
, and in set theories that grew out of type theory, such as New Foundations
and related systems. But it does not work in the axiomatic set theory ZFC and related systems, because in such systems the equivalence classes under equinumerosity
are "too large" to be sets. For that matter, there is no universal set V in ZFC, under pain of the Russell paradox.
Hatcher (1982) derives Peano's axioms from several foundational systems, including ZFC and category theory
. Most curious is his meticulous derivation of these axioms from the system of Frege's Grundgesetze using modern notation and natural deduction
. The Russell paradox proved this system inconsistent, of course, but George Boolos
(1998) and Anderson and Zalta (2004) show how to repair it.
's work on incompleteness is that in any effectively generated axiomatization of number theory
(i.e. one containing minimal arithmetic), there will be true statements of number theory which cannot be proven in that system. So trivially it follows that ZFC or any other effectively generated formal system
cannot capture entirely what a number is.
Whether this is a problem or not depends on whether you were seeking a formal definition of the concept of number. For people such as Bertrand Russell
(who thought number theory, and hence mathematics, was a branch of logic and number was something to be defined in terms of formal logic) it was an insurmountable problem. But if you take the concept of number as an absolutely fundamental and irreducible one, it is to be expected. After all, if any concept is to be left formally undefined in mathematics, it might as well be one which everyone understands.
Poincaré, amongst others (Bernays, Wittgenstein), held that any attempt to define natural number as it is endeavoured to do so above is doomed to failure by circularity. Informally, Gödel's theorem shows that a formal axiomatic definition is impossible (incompleteness), Poincaré claims that no definition, formal or informal, is possible (circularity). As such, they give two separate reasons why purported definitions of number must fail to define number. A quote from Poincaré:
"The definitions of number are very numerous and of great variety, and I will not attempt to enumerate their names and their authors. We must not be surprised that there are so many. If any of them were satisfactory we should not get any new ones."
A quote from Wittgenstein:
"This is not a definition. This is nothing but the arithmetical calculus with frills tacked on."
A quote from Bernays: "Thus in spite of the possibility of incorporating arithmetic into logistic, arithmetic constitutes the more abstract ('purer') schema; and this appears paradoxical only because of a traditional, but on closer examination unjustified view according to which logical generality is in every respect the highest generality."
Specifically, there are at least four points:
These problems with defining number disappear if one takes, as Poincaré did, the concept of number as basic i.e. preliminary to and implicit in any logical thought whatsoever. Note that from such a viewpoint, set theory
does not precede number theory
.
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s using set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
.
The contemporary standard
In standard, Zermelo-Fraenkel (ZF) set theory the natural numbersare defined recursively by 0 = {} (the empty set) and n + 1 = n ∪ {n}. Then n = {0, 1, ..., n − 1} for each natural number n. The
first few numbers defined this way are 0 = {}, 1 = {0}, 2 = {0,1}.
The set N of natural numbers is defined as the smallest set containing 0 and closed under the successor function S defined by S(n) = n ∪ {n}. (For the existence of such a set we need an Axiom of Infinity
Axiom of infinity
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory...
.) The structure (N,0,S) is a model of Peano arithmetic.
The set N and its elements, when constructed this way, are examples of von Neumann ordinals.
The oldest definition
Frege and Bertrand RussellBertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
each proposed the following definition. Informally, each natural number n is defined as the set whose members each have n elements. More formally, a natural number is the equivalence class of all sets under the equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
of equinumerosity
Equinumerosity
In mathematics, two sets are equinumerous if they have the same cardinality, i.e., if there exists a bijection f : A → B for sets A and B. This is usually denoted A \approx B \, or A \sim B....
. This may appear circular but is not.
Even more formally, first define 0 as
(this is the set whose only element is the empty setEmpty set
In mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
). Then given any set A, define:
-
as 
σ(A) is the set obtained by adding a new element y to every member x of A. This
is a set-theoretic operationalization of the successor function. With the function σ in hand, we can say 1 = , 2 = , 3 = , and so forth. This definition has the desired effect: the 3 we have just defined actually is the set whose members all have three elements.This definition works in naive set theory
Naive set theory
Naive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
, type theory
Type theory
In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...
, and in set theories that grew out of type theory, such as New Foundations
New Foundations
In mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
and related systems. But it does not work in the axiomatic set theory ZFC and related systems, because in such systems the equivalence classes under equinumerosity
Equinumerosity
In mathematics, two sets are equinumerous if they have the same cardinality, i.e., if there exists a bijection f : A → B for sets A and B. This is usually denoted A \approx B \, or A \sim B....
are "too large" to be sets. For that matter, there is no universal set V in ZFC, under pain of the Russell paradox.
Hatcher (1982) derives Peano's axioms from several foundational systems, including ZFC and category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
. Most curious is his meticulous derivation of these axioms from the system of Frege's Grundgesetze using modern notation and natural deduction
Natural deduction
In logic and proof theory, natural deduction is a kind of proof calculus in which logical reasoning is expressed by inference rules closely related to the "natural" way of reasoning...
. The Russell paradox proved this system inconsistent, of course, but George Boolos
George Boolos
George Stephen Boolos was a philosopher and a mathematical logician who taught at the Massachusetts Institute of Technology.- Life :...
(1998) and Anderson and Zalta (2004) show how to repair it.
Problem
A consequence of Kurt GödelKurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
's work on incompleteness is that in any effectively generated axiomatization of number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
(i.e. one containing minimal arithmetic), there will be true statements of number theory which cannot be proven in that system. So trivially it follows that ZFC or any other effectively generated formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
cannot capture entirely what a number is.
Whether this is a problem or not depends on whether you were seeking a formal definition of the concept of number. For people such as Bertrand Russell
Bertrand Russell
Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...
(who thought number theory, and hence mathematics, was a branch of logic and number was something to be defined in terms of formal logic) it was an insurmountable problem. But if you take the concept of number as an absolutely fundamental and irreducible one, it is to be expected. After all, if any concept is to be left formally undefined in mathematics, it might as well be one which everyone understands.
Poincaré, amongst others (Bernays, Wittgenstein), held that any attempt to define natural number as it is endeavoured to do so above is doomed to failure by circularity. Informally, Gödel's theorem shows that a formal axiomatic definition is impossible (incompleteness), Poincaré claims that no definition, formal or informal, is possible (circularity). As such, they give two separate reasons why purported definitions of number must fail to define number. A quote from Poincaré:
"The definitions of number are very numerous and of great variety, and I will not attempt to enumerate their names and their authors. We must not be surprised that there are so many. If any of them were satisfactory we should not get any new ones."
A quote from Wittgenstein:
"This is not a definition. This is nothing but the arithmetical calculus with frills tacked on."
A quote from Bernays: "Thus in spite of the possibility of incorporating arithmetic into logistic, arithmetic constitutes the more abstract ('purer') schema; and this appears paradoxical only because of a traditional, but on closer examination unjustified view according to which logical generality is in every respect the highest generality."
Specifically, there are at least four points:
- Zero is defined to be the number of things satisfying a condition which is satisfied in no case. It is not clear that a great deal of progress has been made.
- It would be quite a challenge to enumerate the instances where Russell (or anyone else reading the definition out loud) refers to "an object" or "the class", phrases which are incomprehensible if one does not know that the speaker is speaking of one thing and one thing only.
- The use of the concept of a relation, of any sort, presupposes the concept of two. For the idea of a relation is incomprehensible without the idea of two terms; that they must be two and only two.
- Wittgenstein's "frills-tacked on comment". It is not at all clear how one would interpret the definitions at hand if one could not count.
These problems with defining number disappear if one takes, as Poincaré did, the concept of number as basic i.e. preliminary to and implicit in any logical thought whatsoever. Note that from such a viewpoint, set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
does not precede number theory
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
.
See also
- Peano arithmetic
- ZFC
- Axiomatic set theory
- New FoundationsNew FoundationsIn mathematical logic, New Foundations is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name...
- Ackermann codingAckermann codingAckermann coding is the encoding of finite sets as natural numbers as devised by Wilhelm Ackermann in his 1940 paper "Die Widerspruchsfreiheit der allgemeinen Mengenlehren"....
External links
- Stanford Encyclopedia of PhilosophyStanford Encyclopedia of PhilosophyThe Stanford Encyclopedia of Philosophy is a freely-accessible online encyclopedia of philosophy maintained by Stanford University. Each entry is written and maintained by an expert in the field, including professors from over 65 academic institutions worldwide...
:- Quine's New Foundations — by Thomas Forster.
- Alternative axiomatic set theories — by Randall Holmes.
- McGuire, Gary, "What are the Natural Numbers?"
- Randall Holmes: New Foundations Home Page.