3-1-2

Home

Return to 3 - 1

Previous Article (3-1-1)

INTRODUCTION TO FUNCTIONS

The concept of a function is very useful in mathematics, and it is especially useful to the subject of large numbers. In essence a function takes in a set of inputs, and produces a single output. How a function converts input into output does not matter as far as the definition of a function goes. As long as we have some way to assign a single output for any given combination of inputs it is a valid function.

To better understand what a function does consider this example: A function might take a single number and double it. We notate this as ...

f(n) = 2n

Now for any value of n, we can say it's double is f(n). Basically this notation allows us to talk about the input and output. Let's say we want to find the "value" of f(3). To do so we substitute "3" for the variable "n" in the given equation. Thus we can say:

f(3) = 2(3) = 6

So f(3) = 6.

The great thing is that we can define any function we want as long as we can explain how input is converted into output.

Although you didn't start out grade school learning about functions, from a certain point of view, you were using them all the time when you were adding, subtracting, multiplying and dividing. Consider the addition:

2+3 = 5

The addition symbol in this case is taking two inputs and producing a single output. Functions, it must be noted, can take any (finite) number of inputs. If there is more than one input we can separate the inputs with commas. Also, the symbol we use for the function can be any letter we want to use. Let's use A to represent the addition function. We can define addition as...

A(n,m) = n + m

We can then say ...

A(2,3) = 5

Now there is an important point to be made here. Our functions f(n) and A(n,m) were defined using the operations of addition and multiplication. Addition and multiplication are functions themselves ! So we are using functions to define functions ! Does this mean that addition and multiplication are defined by functions themselves? How far does this regression go? In order to have a non-ambiguous starting point to our discussion of functions we need to begin by defining our fundamental functions. The fundamental functions are the simplest functions possible. Their only purpose is to allow us to define more complex functions without having to resort to circular logic ( such as A(n,m) = n + m , which fails to actually define how the operation of addition is carried out).

The Four Fundamental Functions

A fundamental function, like a fundamental particle or fundamental force, is a function that can not be broken down into simpler functions. By studying various function used for large numbers I have found that only 4 functions are needed to define everything from Knuth up arrows, steinhaus polygons, conway right arrows, to array notation (We will be learning about all of these "functions" a little later in this section). In fact we can even reduce that number to three or two depending on how we want to interpret functional composition. I will now present the four fundamental functions in no particular order:

I. The Input/Output Function

Our first function is the input/output function. This function is truly elementary. All it does is take the input and return it as output. In other words, it does nothing. We can use I(n) to represent it. We can then say ...

I(n) = n

Admittedly this is a pretty useless function. However, since it can't be broken down further (depending on how we define composition) it's best considered a fundamental function. It also can serve as a fundamental basis for higher level functions sometimes. For example say we define f(n) such that ...

f(n) = I(n) if n < 2 , & f(n) = n+1 if n >= 2.

If we didn't acknowledge I(n) as a fundamental function then we would have to write f(n) = n when n < 2. This would require us to acknowledge that higher level functions are not merely built up from the fundamental functions, because n, by itself, would not be considered a function. However we want to construct a set of fundamental functions such that, all the functions we will be using will simply be composites of them. We will be learning more about generating composite functions from simpler functions later.

II. The Successor Function

Our second fundamental function is the Successor function. This one is very important, although it might seem quite trivial at the moment. Basically it takes any natural number as input, and returns the next natural in sequence as output. We can notate it as S(n). You may realize that it simply adds one to n. So we can simply write ...

S(n) = n + 1

But there is a problem with this. Can you guess what? If S(n) is a fundamental function, it shouldn't be defined with another function. Furthermore we will later be using the successor function to define addition, so using addition to define the successor function would be circular logic again! So how do we define it? Well we can try to describe it as follows ...

if n is an element of N then S(n) is the next element of the ordered set N after n, and is called the successor of n

Note however, that we used addition in the definition of N ! So even this is circular. In fact, I intend to replace n+1 in the definition of N with S(n) before the end of this article. So how do we get around the circular logic?

How do we define S(n)? We don't. Remember I said numbers are abstractions. Well the same is true of functions. In fact it doesn't matter what S(n) does, whether it adds one, two, doubles the number, squares it, whatever. The only important thing is that S(n) =! n. This means that S(n) =! I(n) and is distinct from it. It is also important that S(n) > n.

Although this may seem strange to you, sometimes mathematicians have to leave certain fundamental concepts undefined. What does it really mean to take the successor of a number. It just means we count to the next number. When children count 1,2,3,... they are invoking the successor function. We could then think of the successor function as being defined as "the successor of 1 is 2, the successor of 2 is 3 ... and so on". The successor function is simply our starting point. It is the first function which DOES something, what that something is isn't important. What is important is how various successors relate to each other. We will get to that when we start talking about our first axioms.

I should note that it is actually impossible to extricate the notion of the successor and the notion of the natural numbers. They are actually one and the same. They need each other in order to exist. It is therefore meaningless to talk of the successor function without first explaining the natural numbers, and its meaningless to speak of the naturals without first explaining the successor function. The only way out of this is not to worry about what they mean, but just to worry about the consequences of these ideas when they are extended (we're getting to that).

For convenience I also use the notation n' for S(n), because it's easier to write when it comes to lengthy definitions. So we can say...

S(n) = n' > I(n) = n

Now let's move on to our third fundamental function...

III. The Predecessor function

Our third fundamental function is called the Predecessor function. It is our first inverse function, being the inverse of the successor function. It takes a Natural (number) as an input and returns the preceding natural. In other words it subtracts one. We notate it as P(n) and we can say ...

P(n) = n - 1

Of coarse we don't want to do that. Instead we can use the undefined Successor function to define an important conditional property for P(n). We say ...

P(n) = m if and only if S(m) = n & m e N

Please note that P(1) is undefined. You might say, that's ridiculous, P(1) = 0. However for the purposes of our discussion, only the Naturals exist. 0 is NOT a natural number. Since 0 is the only number that satisfies the equation S(0) = 1, and 0 e! N that means there is no possible output for P(1). To avoid the problem of having to show no member of N = P(1) we can simply make note of this exception within the definition of P(n). To do this we will use "ud." as shorthand for undefined. Note that an undefined value has one important property. For any function f , f(ud.) = ud. This is an important point.

Consider S(P(1)). It may occur to you that S(P(1)) = S( 1 - 1 ) = 1 - 1 + 1 = 1 + 0 = 1

You might conclude that since the final output is a Natural there is no problem with this expression. However since P(1) is ud. it means S(P(1)) = S(ud.) = ud. So the entire expression is undefined. Although this may seem strange to you, you must remember that it's an issue of scope. By keeping our focus purely on Naturals, everything outside of that is undefined. So we redefine P(n) using a special set of rules...

If n e N then P(n) can be defined as follows...

1. if n = 1 then P(1) = ud.

2. if n =! 1 then P(n) = m if and only if S(m) = n & m e N

Note that P(S(n)) = n for all n e N , but S(P(n)) = n only if n =! 1. In this sense they are virtually perfect inverse functions. Only one fundamental function remains. This one may be the most fundamental of all.

IV. The Unity function

Note that the Naturals can be listed using 1 and the successor function alone. Instead of writing {1,2,3,...} we can write {1, S(1) , S(S(1)) , ...}. So is 1 the only pure number? Is everything else simply composite functions? Well as it turns out we can define 1 so that even it is a function. A function can have as many or as few inputs as you like. What I didn't mention was that you could even have a function with no inputs. In that case the function can only return the same result every time, because it's "input" never varies (is always empty). Thus we can define a empty function whose value is 1. We will use u() to stand for the unity function. We can then write ...

u() = 1

Furthermore we can use " () " or just " u " to stand for the unity function. In these instances these symbols represent 1. So we can say ...

u() = u = () = 1

Please note that u(1) is invalid here. The unity function can not take any inputs, so there must never be anything between the parenthesis. With the unity function in place, it is no longer necessary to concern ourselves with the meaning of 1. This may seem dis-concerning to some. However the reason I have set up things this way is to detach the subject of counting numbers from the act of counting, and interpret as a completely abstract process. We can then simply study the process in order to learn how to generate very large numbers.

Reducing the Number of Fundamental Functions

The use of four fundamental functions has a lot going for it philosophically. In numerology four represents completeness and foundation. We have the four directions, north,south, east, west. We have the four fundamental forces. The greeks believed there were four elements, earth, water, wind, fire, etc. However, from a mathematical standpoint we can actually reduce the number to three or two, depending on what we establish as legal forms of composition.

It turns out that the input function can be interpretted as a composition of the Successor and Predessor function. Basically:

I(n) = P(S(n))

Basically composition means that we define one function using other functions. Since the input function can be defined using the successor and predecessor function it can be broken down into "simpler" functions and is therefore not fundamental. Please note that:

I(n) =! S(P(n))

The order of composition matters here. The reason is because in the case of S(P(n)) is undefined when n = 1, and so is not equal to I(1) = 1. In order for expressions to be equivalent, they must be equivalent for every possible input. P(S(n)) never runs into this problem, because it takes the successor first before taking the predecessor. Since the Successor function is always defined this never leads to a problem. The smallest value the predecessor function can take is S(1) = 2, and P(2) is defined and = 1. Thus it is P(S(n)) is ALWAYS equal to I(n), where S(P(n)) is almost always except at n = 1.

One objection to this might be that returning an input is actually simpler than the composition of P and S. Afterall, we don't add one just to subtract it to get back where we started. We simply take the input as is. The fact that the input function seems simpler than the combination of its parts might lead us to disallow this kind of composition. The problem is, mathematically, how would we define "simpler". We therefore are drawn to the conclusion that the input function is actually unnecessary as a fundamental function.

This leaves us with S(n), P(n), and u(). The predecessor function however can be understood as being defined using the Sucessor function. This means it can be thought as a "composite" of sorts. In the subject of large numbers we will have very little use for "inverse functions", but the one inverse function we can absolutely not avoid using is the predecessor function. It is absolutely essential to having functions which "terminate" (the significance of this will become more self-evident as we continue studying large numbers). Inverse function however are defined very different than composite functions. Rather than define a function as plugging an input into a series of other functions, inverse functions require a condition to be met in order for an output to be valid. This is not computation in the usual sense. One could then argue that the Predecessor is not a composite of the sucessor function in the usual way, and should therefore be considered a distinct fundamental function. We will certainly treat it as distinct. None the less we might argue that in truth there are really only two fundamental functions: the successor, and the unity function. Everything else is simply an extension of these most basic functions.

Personally, based on how I have used these functions I would have to say the most logical choice seems to be that there are three fundamental functions, S(n),P(n), and u(). We will use S and P explicitly all throughout our study of large numbers, and we will be using u() implicitly when we use 1 to define initial conditions. When I(n) is used it is usually in the form f(n) = n, so it is somewhat extraneous to call it a fundamental function, and we can of coarse think of it as a composition of S and P, making it largely unnecessary in a theory of large numbers. In any case, these fundamental functions will serve as our foundation for everything to follow, so make note of them.

Redefining N

Now without using a reference to addition, or even the number 1, I can redefine the Natural Numbers using our four fundamental functions. Note: Let N'() = N'(0), and let S(0) = 1. Here is our new definition ...

Definition of N

N > A N'(k)

N'() = {}

if N'(k) is known, construct N'(k') as follows...

1. if N'(k) = {} then N'(k') = {u}

2. if N'(k) =! {} then N'(k') = N'(k) U { n' } , where n = max[N'(k)]

Note the use of k' and n'. These mean S(k) and S(n) respectively. While this definition certainly looks impressive, and our fundamental functions may seem sufficient to get started, none of this actually does very much yet. In order for these structures to make sense we have to provide some basic logic for them to work with. This doesn't give us the ability to say for example , that 3 < 5. For that we need to have some basic axioms that provide properties for our fundamental functions. Once this is in place however we will have a true mathematical foundation on which to begin a work of "creation".

For convenience here are the four fundamental functions again ...

I(n) = n

S(n) = n + 1

P(n) = n - 1

u() = 1

I've only written them in that form for simplicity sake. It is better to think of them in terms of properties rather than as operations on n. As you will see a little later, these functions can be combined together in a multitude of ways to create a wide variety of functions and all of the popular large number functions. This will enable us to start talking about operations and how they work on numbers step by step.