Thread: Proving a fundamental Theorem using PMI

1. Proving a fundamental Theorem using PMI

I would appreciate some help on proving theorem #4 (last two images) using Peano's axioms and subsequent theorems. I have been working on it, off and on, for about two weeks.

The proof is divided into two parts, A and B. I understand neither half of the proof as given although I have put together my own form of proof for the first half which is perhaps just a more detailed version of the given proof.

For the second half of the proof I have nothing but questions but confine myself to the first half of the proof, perhaps that is all of the help I will need.

So the first question is this, is my version of the proof valid.

My version of the first half of the proof, Part A.

This theorem introduces and defines the addition operator designated by the infix symbol “+”, i.e “x + y”.

Using a prefix operator symbol one can write “x + y” = sum(x,y) which I prefer as an aid to my thinking process.

So the claim is that given that x, y are elements of N, where N is the set of Natural numbers, sum(x,y) is a function that produces a unique natural number, say “s” . sum(a,b) is required to have the properties:

Property 1: sum(x, 1) = x’

Property 2: sum(x, y’) = (sum(x, y))’

The first half of the proof says let x be a particular fixed natural number and show that sum(x,y) produces a unique “s” no matter what value of y is chosen.

The proof then refers to ay and by but does not say what either of those refer too. I assume to the experienced eye their meaning is obvious but I have considered three different possibilities and finally settles on this: (am I right? A critical question.)

Suppose sum(x,y) is not the only possible function that has the two required properties, suppose there is a
sum_A(x, y) = ay and a sum_B(x, y) = by ,

each of which subscribe to the two properties but when loaded with the same values for “x” and “y” produces different results. The proof then endeavors to show that each case produces the same result therefore they are only two different names for the same function and so

sum_A(x, y) = sum_B(x, y) = sum(x, y).

Now then with x a fixed natural number and assuming both sum_A(x,y) and sum_B(x,y) subscribe to the two required properties we say:

Let “M” be the set of natural numbers for which both functions, sum_A and sum_B produce the same results. We can write for both functions, since they each, by inductive hypthosis, subscribes to property 1, when y = 1 :

sum_A(x, 1) = x’ and

sum_B(x, 1) = x’

Therefore sum_A(x, 1) = sum_B(x, 1) when y =1 and so 1 is an element of M.

Now we come to the critical point for the first half of the proof. The author writes,
if “y” is an element of M then

1: sum_A(x, y) = sum_B(x, y) (by “inductive hypothesis” … is that correct?)

Since both sum_A(x, y) and sum_B(x, y) are expressions for the same natural number it follows by the uniqueness of a successor that:

2: [sum_A(x, y)]’ = [sum_B(x, y)]’

Finally, using property 2 from the right hand side back to the left hand side:

3: [sum_A(x, y)]’ = sum_A(x, y’), and

4: [sum_B(x, y)]’ = sum_B(x, y’),

So that 2: becomes

5: sum_A(x, y’) = sum_B(x, y’),

which shows that what is true for the inductive hypothesis with argument “y” : sum_A(x, y) = sum_B(x, y)
is also true for “y’ ” : sum_A(x, y’) = sum_B(x, y’),

therefore M contains all natural numbers y and so it is established that for a fixed “x” there is only one function:
sum(x, y), that subscribes to properties 1 and 2 and hence defines that defines addition for a fixed value of x.

If this proof is correct I will endeavor to understand the Professors proof for part A and part B, if not, help in where I went wrong would be appreciated.

2. Re: Proving a fundamental Theorem using PMI

Yes, that is correct. Basically, when proving (basic) facts about natural numbers, the go-to tool is induction.

The idea is, we find that the set on which $sum_A$ and $sum_B$ agree is the same set: all of the natural numbers.

3. Re: Proving a fundamental Theorem using PMI

Hi,
I agree with Deveno about the correctness of your uniqueness proof. However, I really don't think the existence proof as given by your 5th image is a good proof. (In Landau's Foundation of Analysis development of the real numbers, there is the same objection that I have.) The following is a discussion on recursive definitions.

4. Re: Proving a fundamental Theorem using PMI

OK, thank you both. I am still digesting both of your comments and will probably have more questions, I just wanted to let both of you know that I am still tuned in and appreciate your help , thanks again ... processing.

5. Re: Proving a fundamental Theorem using PMI

Originally Posted by johng
Hi,
I agree with Deveno about the correctness of your uniqueness proof. However, I really don't think the existence proof as given by your 5th image is a good proof. (In Landau's Foundation of Analysis development of the real numbers, there is the same objection that I have.) The following is a discussion on recursive definitions.

Interestingly enough, we can turn the situation "on its head", and DEFINE the natural numbers to be a set:

$N$, along with a distinguished element $u \in N$, and an injective mapping $s: N \to N$ such that if $f: X \to X$ is any function, and $a \in X$, there exists a UNIQUE function:

$\phi:N \to X$ with $\phi(u) = a$ and for all $n \in N$, we have: $\phi(s(n)) = f(\phi(n))$.

This makes the theorem johng proves "automatically true", but there is a price to be paid (there's always some catch, right?). For one thing, this doesn't establish such a set $N$ even exists (though if it does, we can define functions recursively using it). For another, it is no simple matter to show that $(N,u,s)$ satisfies the Peano axioms. Finally, even after taking $N = \Bbb N$, with $u = 1$, and $s(n) = n'$, there is no guarantee that this $N$ is unique. And in fact, it is NOT, anything that "acts" like $\Bbb N$ (but is some other set, perhaps a set of (hypothetical) elephants, for example) would do as well.

In the end, no matter how much FORMALISM one requires (and mathematicians often thrive on the stuff), whether or not these axiomatic systems actually capture what we do intuitively when we "count" or "reckon", is more a matter of philosophy than mathematics, a point addressed by Paul Benacerraf in his classic essay "What Numbers Could Not Be" (link here, interesting reading).

I bring this up not so much to question johng's excellent reply (a similar proof is found in Jacobson's Basic Algebra I), nor to overwhelm the OP, but merely to point out that while it is worthwhile to examine the "nuts and bolts" of a rigorous/formal construction of the natural numbers, one must in the end concede that there are more ways than one to skin that cat, and in the end one must form an INTERNAL conception of what the "things" (numbers) one is working with, actually are. Mathematicians rarely acknowledge this: that the "agreed-upon" meanings of their communications are in fact, incomplete (and no, this won't absolve you from ridicule if you claim that 6 and 7 is 12).

You'll notice that any definition of the natural numbers leans rather heavily on sets and functions (themselves special kinds of sets). Although this is quite standard in the mathematical community, and gives an air of polished and exact precision, do not be deceived: no one really knows what sets are (although we DO know exactly which rules they have to follow, if we ever decide upon the existence of anything besides the set consisting of emptiness). Questions of identity and being, are more complicated than they appear, at first glance.

6. Re: Proving a fundamental Theorem using PMI

M. Johng and M. Deveno, thanks for your detailed responses. I am afraid that I am not yet able to leap over tall buildings in a single bound, at best, small dwellings. That being the case I must essentially go over your responses line by line explaining my interpretation of what is being said, sorry. Any correction or edification would be appreciated, thanks.

Beginning with your first detailed response M. Johng.

First of all, yes, you have correctly identified the pics I included as being from Professor Landau’s “Foundation of Analysis”. For those interested a free .pdf can be found online.

So …

“What you have here is a definition by induction, more commonly called a recursive definition.”

I know what a recursive definition is but what I am unsure of is whether you can establish an “inductive set” without one. Without getting into the complications of this or that definition of an inductive set what I am thinking of is any set that can ordered using Peano’s axioms … if I can simplify things to that degree.

For example, the set of symbols that we commonly refer to as the set of “natural number” themselves, would it be correct to say that they cannot be proved to be an inductive set without providing the recursive means of manufacturing a next integer symbol?

Another example f(x) = 2x. does “2x” generate an inductive set by itself or would you need to recast it in the form of a recursive definition of a function? Now that I think of it, is any function that generates a one-to-one correspondence (a function that passes the vertical and horizontal tests) automatically a definition of an inductive set.

Another related question: It seems that when the PMI is employed that it is tacitly assumed that the proposition is stated within the context of an inductive set, is that right? Are there situations where one might not be sure whether a proposition’s domain is “inductive” or not … and this gets back to the first question, how can one be sure except perhaps empirically.

I have actually gotten further into your response then these questions indicate but I think I will not ask too many questions at once ... and these basic questions are distracting and impede progress. Also, I suspect I know the answer to some of my questions, but my sad experience is that in math, what is true is obviously true right up to the point where it is obviously false (wah, wah…). Thanks for any help you can provide.

7. Re: Proving a fundamental Theorem using PMI

Naively, a recursive definition of a function takes the form:

$f(1) = a$
$f(n+1) = g(n)$ <----note we need ANOTHER function $g$ to define $f$.

Here is an example:

$f(1) = 1$
$f(2) = 2$ <---here we need 2 "starting values", for reasons that will be clear in a moment
$f(n+1) = f(n) + f(n-1)$ <----for n > 2 (if we didn't have 2 starting values, f(3) would be a BIG problem).

Here $g(n) = f(n) + f(n-1)$, the only thing that keeps this from being a "circular" definition is that $n + 1 > n,n-1$, so we only define values for $f(n+1)$ AFTER we have computed EARLIER ones. This "leverages" the ordering we have on the natural numbers we obtain from successorship. Without this ordering, we'd be lost.

This allows us to compute, for example, f(5):

f(5) = f(4) + f(3) = (f(3) + f(2)) + f(3) = (f(3) + f(2)) + (f(2) + f(1)) = [(f(2) + f(1)) + f(2)] + (f(2) + f(1)) = [(2 + 1) + 2] + (2 + 1) = [3 + 2] + 3 = 5 + 3 = 8.

*******************

Your observation is essentially correct: we cannot define a function recursively without the natural numbers, and we cannot define the natural numbers unless we define them using a recursive function: successorship. This seems like a tough nut to crack.

So the idea is: we define a recursive function to be a function defined by a recursively-defined set. At first this appears to "do nothing", but if we can get our hands on a recursively-defined set (any one will do), we're home-free.

And THIS is what the Peano axioms tells us: there exists a recursively-defined set containing 1 contained in any OTHER recursively-defined set containing 1 and any successor of 1. In other words the natural numbers are just a "minimal recursively-defined set" closed under one PARTICULAR recursive function. So now we have slightly easier problem: how can we define a recursive function (just this ONE, the successor function) without using the natural numbers we need to define "recursive"?

The "standard answer" is this: we use UNION. Suppose we start with a set with just one thing in it: $\{a\}$ ($a$ might be anything, we don't care). We then make this definition:

$1 = \{a\}$ (the number 1 is a set with one thing in it. Often we use "the empty number" or 0, for $a$)

We then define:

$s(1) = 1 \cup \{1\} = \{0,1\}$ (or if you prefer, $\{a,\{a\}\}$).

We then give a NAME to:

$I = \{0,1,2,....s(s(s...s(1))...)\}$ as "the smallest set $I$ such that $1 \in I$ and $x \in I \implies s(x) \in I$ and for which: if $y \in I$ and $y \neq 1$, there exists $z \in I$ with $y = s(z)$". Now THAT's a mouthful, but at least it avoids using the words "recursive" and "natural number".

The EXISTENCE of such a set cannot, by itself, be PROVEN, so we take it as GIVEN that any set theory worth its salt, will have such a set. This is called the Axiom of Infinity, and is a point of some contention with some philosophers.

In layman's terms, it says: "There exists an infinite set".

HOWEVER.....logically speaking, this is "of the same strength" as the principle of Well-ordering for countable sets, and the principle of induction. So, in a sense, we're "back where we started", the natural numbers are something for which induction is true, BY DEFINITION...we cannot PROVE this, we have to take it "on faith". It seems intuitively plausible.

(Imagine, if you will, that our universe is a giant computer simulation, and that this computer has finite memory storage. If we try to exceed that memory capacity with too large an integer, we'll get an "overflow error". We have, at this point in time, no reason to know if this is actually the case, or not: the memory capacity could be very large, and so beyond our ability to test. Nevertheless, the concept of an infinite set of integers has proven so USEFUL, that we have built a large body of mathematics upon it, and in studying math, the "real world" conditions need not apply, it is (or can be) a purely formal discipline).

8. Re: Proving a fundamental Theorem using PMI

First thanks for your expertise and your labor in writing everything out … and your clarity. I need to continue going over things in detail but I do understand a large part of what you are saying, thanks.

So starting at the bottom of things … a definition of a single recursive function without using the standard template which makes use of the set of natural numbers, i.e.

f(1)=a
f(n+1)=g(n)

This needed single recursive definition is formulated in terms of the union of sets.

Basically a natural number is defined as a “cardinal number”, that is, the counted number of sets in a superset bearing it’s name. An important point is that the cardinal number symbol that names a superset is not included in that set thus it is the union of the contents of a superset plus its name that recursively defines the contents of the next natural number. Mnemonicly I see this recursion as a set of concentric circles, each next outer circle enclosing the previous set's contents plus its name.

Anyway, the point seems to be that the symbols that we use to count with (1,2,3 …) become shorthand for the sets and supersets they represent and that being the case the recursive generation of a next superset from a previous one can also be expressed in terms of natural numbers; that is, every natural number “n” has a successor whose name is issued to represent the union of its contents (subsets) plus its symbol name. So it is then that the existence of a first set (the null set) plus a particular type of recursively defined union of sets and subsets creates a recursively generated pattern:

I={0,1,2,....s(s(s...s(1))...)}, (or, perhaps, the sequence of concentric circles that I have suggested)

whose properties Peano’s axioms minimally describe in terms of the set of natural numbers … including the existence of a successor function.

My wording is probably not precise but I think I get the idea … and now try and go further:

Accepting Peano’s axioms, the first four axioms describe a the properties of a special type of recursively generated sequence, the last axiom, #5, the axiom of Induction, declares the minimum information needed to prove that a function, recursively defined, is a successor function, that is, a generator of a pattern that conforms to Peano’s first four axioms and is thus in a one to one relation with the set of natural numbers.

Do I have this correct so far because playing with your example at the top your post I have come to additional conclusions based on my current understanding as expressed above. Thank you.