6

I'm posting this here because it's more of a philosophical question than a mathematical one.

In set theory, we define a function as a particular type of set; and since the natural numbers are defined as particular sets, we know exactly what we mean by a function from the natural numbers to themselves. The kind of function they study in computability theory, or number theory. Inputs a natural, outputs a natural, and has existence as a particular collection of ordered pairs.

Now if we are using only the Peano axioms, I'm not sure I know what a function is. It's a mapping that inputs a number and outputs a number. But I don't know formally what that is. How do I know there is any such thing?

How did philosophers regard functions before set theory?

The specific application I have in mind for this question is a bijection between the natural numbers and a proper subset of themselves. In set theory this is perfectly sensible. I'm wondering if this is sensible using only the Peano axioms, and for what meaning of the word function?

user4894
  • 2,890
  • 2
  • 15
  • 25
  • mathematicians before Dirichlet conceived functions in a less abstract way, as formulas or algorithms with variables. As a formula 2n can be understood without set theory, but how can you say that by this you get a bijection to a proper subset of the natural numbers ***without*** set theory? – viuser Feb 24 '17 at 04:35
  • @wolf-revo-cats Yes that's what I'm interested in. Galileo's paradox and the like. Galileo was implicitly contemplating a completed infinity of natural numbers. He anticipated Cantor in that regard. You can't have a bijection unless the infinite set is there first. I think that's the philosophical issue I'm chasing. – user4894 Feb 24 '17 at 04:54
  • So, I feel like you're asking four questions here and three are different from the title question. It seems you're asking (1) What are functions in the Peano axioms? (2) How do I know that functions in PA exist? (3) How did philosophers regard functions before set theory? Finally, (4) Does the PA concept of a function also have the form of a bijection between sets. Usually its asked that you only ask one actual question per question, are there any of these that you can ask as another question? To me, (1) (2) and (4) seem like they _could_ be one question but (3) is decidedly different. – Not_Here Feb 24 '17 at 05:21
  • At any rate, I'm going to answer what I see as the main combined question of (1) (2) and (4), maybe you could repost (3) as another question because it seems to be an altogether different question, with a very interesting answer said above in these comments. – Not_Here Feb 24 '17 at 05:23
  • @Not_Here Yes nothing in my brain is much of a fit for this site. It's all one related subject in my mind but I agree with you that it's four or more specific questions by Stackexchange standards. Happy to see whatever responses and comments I get. – user4894 Feb 24 '17 at 05:39
  • I didn't mean it to be derisive, I think that I can supply you with an answer to 1, 2, and 4 but 3 would definitely be great to ask as well as a different question. I think after my answer you should be able to understand the main points of what your question is asking, at least hopefully – Not_Here Feb 24 '17 at 05:41
  • @Not_Here Oh no I quite agree with you and took your observation as being perfectly correct. My question's too general for this site. – user4894 Feb 24 '17 at 06:23
  • On the early history od the *function* concept, you can see the post : [concept-of-a-function-and-idea-of-a-formula-as-a-function](http://hsm.stackexchange.com/questions/252/concept-of-a-function-and-idea-of-a-formula-as-a-function). – Mauro ALLEGRANZA Feb 24 '17 at 07:01
  • On Galileo's Paradox, you can see the post : [what-are-the-origins-of-galileos-paradox](http://hsm.stackexchange.com/questions/5712/what-are-the-origins-of-Galileo's-paradox) as well as [did-Galileo's-writings-on-infinity-influence-Cantor](http://hsm.stackexchange.com/questions/451/did-galileos-writings-on-infinity-influence-cantor) and [was-there-anybody-before-Cantor-who-conjectured-existence-of-infinities](http://math.stackexchange.com/questions/1012453/was-there-anybody-before-cantor-who-conjectured-existence-of-infinities-of-diffe). – Mauro ALLEGRANZA Feb 24 '17 at 07:04
  • 1
    For Peano's original axiomatization, see his [Arithmetices principia (1889)](https://books.google.it/books?id=v4tBTBlU05sC&pg=PA91): **Ch.VI Functions**. A *function* is a formula **φ** of the system (and thus of arithmetic) defined on a *class* **s** such that : "for every **x,y ∈ s**, if **x=y**, then **φx = φy**". – Mauro ALLEGRANZA Feb 24 '17 at 10:47
  • @MauroALLEGRANZA Thanks for the references. – user4894 Feb 24 '17 at 16:44
  • @MauroALLEGRANZA Just noting that Dave L Renfro's response to one of the links you gave http://hsm.stackexchange.com/questions/451/did-galileos-writings-on-infinity-influence-cantor is an awesome reading list and commentary on the subject of what Cantor knew about Galileo's infinity. – user4894 Feb 25 '17 at 00:15
  • From a reverse mathematics perspective, there is actually a rather nice answer to your question. Note that you can describe a function using a first-order arithmetical formula, as @Not_Here has described in his/her answer. If you just take the obvious next step of treating these function descriptions as first-class objects, you get ACA0, which is conservative over PA. Taking the natural next step of adding the second-order induction schema gives ACA, which is sufficient for nearly all mathematics relevant to the real world. If you want more details, feel free to ask! – user21820 Aug 22 '17 at 04:37
  • Oh I forgot to mention something. It is totally **false** that in set theory we "know exactly what we mean by a function from the natural numbers to themselves". What are functions on natural numbers will change with the chosen foundations, even in set theory, and doesn't even agree with our intuition. ACA can be considered a kind of set theory where set-specification is predicative, unlike ZFC where set-specification is dangerously impredicative. Roughly, the more assumptions, the more subsets of the naturals you get. – user21820 Aug 22 '17 at 05:09
  • Note that we can uniformly convert any given useful formal system S to a program P such that if S is Π2-sound then P is total, but S cannot prove P total. P on input x enumerates all proofs over S with length at most |x|, and if the proof is of the totality of some program Q, then P runs Q(x). Finally P outputs a string longer than the outputs of all the runs. Clearly if S is Π2-sound then P only runs total programs, and hence P itself is total. And S cannot prove totality of P, otherwise P(x) for sufficiently long x will find that proof and hence run P(x) and output a longer string than P(x). – user21820 Aug 22 '17 at 05:31
  • The point of my preceding remark is that it applies to essentially every potential foundation for mathematics, including PA and ZFC, because we have to believe they are arithmetically sound otherwise we should throw them out. But then the above construction gives us an explicit program that we believe is total (representing a function on naturals) but which our chosen foundations cannot prove, so it is 'ignorant' of the existence of such a function that we believe exists... – user21820 Aug 22 '17 at 05:37

1 Answers1

6

An Intuitive Walkthrough of PA as a formal system

*Peano Arithmetic are a set of axioms in first order logic that describe how arithmetic of the natural numbers works. A first order formal language is a collection of variables, constants, logical symbols (such as negation, conjunction, etc.), parentheses, function letters, and predicate letters. Function letters represent functions that take some amount of variables and or constants and map them to another variable or constant. Predicates are similar, however they map to truth values. An obvious example of the difference between functions and predicates from mathematics is the difference between "addition" which is a function and "less than" which is a predicate. Remember that when we are starting out with a formal language we are starting out with syntax, the symbols don't have interpretations yet, that's what the semantics of model theory is for. Functions in this form, without the semantics, are just things that take one symbol and map them to another. When we introduce interpretations, thats when we have actual numbers being mapped to other numbers.

In the Principia Mathematica Bertrand Russell found that it is perfectly fine to replace functions with predicates. This is referred to as "function elimination." As an example consider this pair:

F(x,y): z where x,y,z, are variables or constants in a formal language, and F is a 2-place function that maps x and y to z.

G(x,y,z,): True, False where x,y,z, are variables or constants in a formal language, and G is a 3-place predicate that maps x, y, and z to a truth value.

If we give an interpretation for F and G that describe the concept of addition, then we would say

F(1,1): 2

G(1,1,2): True

So, because it is logically equivalent, you can view functions as something that maps variables and or constants to variables and or constants or you can view them as predicates that map variables and or constants to truth values. The next thing to understand are interpretations and model theory. Remember that a model of a set of axioms is a pair of sets (D,I). D is the domain of the model and I is the function that maps members of the domain to the variables, functions, constants, and predicates of the formal language. This is the formal language interfacing of semantics and syntax.

In a minimal form of PA we have variables, one constant "a", one 1-place function "F(x)", and one 2-place predicate "P(x,y)". "a" is the constant which when we give it an interpretation will become the number 0. "F(x)" is a function that will take a variable, or the constant, and map it to another variable, which when we give it an interpretation will become the "successor" function, which maps a number to its immediate successor. "P(x,y)" is a predicate that takes two variables or the constant and maps them to a truth value. When we give P an interpretation it will become the identity function, or "=", and will map to a True truth value if and only if x and y are the same.

Peano Arithmetic is made up out of a bunch of variables, one constant, one function, and one predicate. When we give it an interpretation (the natural numbers and our understanding of zero, successor, and equality) we are then presented with a system that works the same way that arithmetic works. Note the idea of composition of functions as well. The successor of 0 is 1, the successor of 1 is 2 and so on. We can come up with a new function, "A(x,y)", which starts at x and applies the successor function to "x" "y" times. This, of course, is a recursive definition of addition. Recursive definitions can be created for multiplication and exponentiation in the same way. Note that you don't need to introduce addition, multiplication, or exponentiation to get arithmetic. Those functions can just be viewed as "short hand" for successive application of the successor function.

Finally, remember that I said before that Russell showed us we can eliminate n-place functions and reintroduce n+1-predicates in their place. To do this with the successor function we would create a new predicate, S(x,y) that maps to a True truth value if y is the successor of x. Consider these two examples:

F(0):1

S(0,1): True

So, functions are viewed as a mapping from symbols to symbols. Once they are given an interpretation they make meaningful statements about actual numbers. Russell showed us that it is logically equivalent to replace functions with predicates that map to a truth value instead of a variable. Both of these are logically equivalent ways of thinking about the formal language.

The successor function is what is referred to as a primitive recursive function. These are a set of functions that are crucially important in the foundations of mathematics and computer science. You might be interested in reading on their history and why they are considered to be "primitive" or "irreducible" functions that are used to compose more complex functions.

*As a reference I have been using Introduction to Mathematical Logic, Sixth Edition (Discrete Mathematics and Its Applications) by Elliott Mendelson.

Answers to the subquestions of the question

(1) What are functions in the Peano axioms?

(2) How do I know that functions in PA exist?

(3) Does the PA concept of a function also have the form of a bijection between sets?

The answer to (1) and additionally (3) is that they are mappings of symbols to symbols before semantics. It maps numbers to numbers after semantics are introduced via a model. Regrettably I think I could do a better job of showing this if I was able to use super scripts and subscripts however Phil.SE does not allow for mathjax. The only function in a minimalist program of PA is the successor function. The successor function takes a symbol and maps it to another symbol and with an interpretation it maps a number to another number. The domain of the successor function is every variable and constant in the language, which with an interpretation correspond to all of the natural numbers. Likewise, the range is the set of natural numbers, excluding zero because zero is defined as not being the successor of any natural number. So the range of the successor function is a subset of the domain, it is the domain without zero.

What does this mean if we eliminate the function and replace it with a predicate? The successor predicate maps in the exact same way except that its range is a set of truth values. S(0,x) will always map to false because zero is not the successor of any number. S(4,1) will also map to false, S(2,3) will map to true, and so on. The domain of the function is ever ordered pair (x,y) of natural numbers and the range is the set of truth values that correspond to whether or not y is the successor of x.

The answer to (2) is that PA is a formal system and formal systems have functions, or predicates or both. Remember, formal systems are just systems of logic. They are a formal syntax and semantics. We use interpretations to give them meaning outside of just a collection of symbols. Functions and predicates are an intrinsic part of logical systems so PA has them because it is a logical system.

Community
  • 1
Not_Here
  • 2,831
  • 1
  • 19
  • 40
  • 1
    Thanks for that detailed writeup. I'll work through it to see if I get some insight. I think I'm starting to focus in on my actual question. I want to know if Galileo's paradox anticipates Cantor or if it's already valid without the Axiom of Infinity. That's probably the question I should have asked. – user4894 Feb 24 '17 at 06:32
  • @user4894 Thats a little bit of what I was afraid of, because I took the title of your question as well as most of the body to be asking about how formal systems and PA work with repsect to functions. Another question specifically about Galileo's paradox and set theory would definitely be well received! – Not_Here Feb 24 '17 at 06:34