3.1.3 - single-variable
3.1.3
Functions of a Single-Variable
Introduction
In this article we will explore the numeric-to-numeric functions. These are functions which take a number as input and return another number (possibly the same, but not necessarily) as the output. These are normally referred to as "functions of a single variable", or as "unary functions". These are the most common functions discussed in associates level mathematics and below. It is also possible to have more than a single variable as input, but many problems in mathematics, science, and engineering can be modeled as a function of a single variable. Consequently multi-variable functions are much more rare. In googology however, multi-variable functions become much more common. In fact, we will find that a theory of large numbers restricted only to single-variable functions is far too limited.
On the other hand, unary functions have the advantage of simplicity. Once we have gained a good grounding in the theory of unary functions, we can extend it to a theory of multi-variable functions.
Function Notation
Before we begin to explore the single-variable functions, it will be convenient to establish the use function notation. This notation can be seen introduced in college level mathematics, and it use carries over to computer science, among other fields.
Begin by recalling that a function is simply something which takes an input and returns an output. For our purposes here a function of a single variable simply takes a number as input and returns a number as output. The input is known as the argument of the function. The argument is usually represented by a variable of some sort. Common choices, are x,y,z,t (usually for real arguments), or a,b,c,i,j,k,n,m, etc. (usually for integer arguments). We will call the output of a function it's dependent. The dependent is often represented either by another variable, or by a "function name". Commonly the variable "y" is used for the dependent. Common function names are f, g, or h. However the dependent (which often serves as the representative of the function itself) can really be represented by any letter (other than the one chosen for the argument), or any word.
One way to think of a function of a single-variable, is as a relation between a pair of variables representing the input and output of the function. Typically the argument is x, while the dependent is y. Some formula will be used to relate these two variables to each other. The argument, x, is said to vary freely over its domain, while the value of y is dependent upon x. "y" is a function of "x".
Function notation is introduced to allow us to speak in general about functions, but also to provide a convenient means to label and distinguish the outputs of a function.
When y is a function of x, we will notate this as:
y= f(x)
This does not mean that y is the product of "f" and "x". Rather the symbol f(x) signifies "x" inside of "f". It is the input being put "inside" our function. The symbol f(x) therefore has two parts: firstly there is the outer container "f( )", and then there is the argument placed inside, "x". f(x) serves as the symbol for any function of a single-variable. It can also be used to represent a specific function that we are currently working with. The "f" is not essential here. We may use any of a variety of "function names", which are appended to the left side of the parentheses:
g(x)
h(x)
ln(x)
sin(x)
abs(x)
etc.
Letters are often used for generic functions, ie. f(x), g(x), h(x). Sometimes abbreviated names are used for commonly used functions, ie. ln(x), sin(x), abs(x).
The argument "x" is also not essential. It could be switched with any other letter, but conventionally it is chosen to imply the boundary of the function. "z" or "c" is sometimes used for complex inputs, "x", "y", or "z" for real inputs, and "i" can be used for integer inputs, and "n", and "m" are typically used for whole or natural inputs.
Here are some examples:
ln(z)
log(x)
P(i)
S(n)
etc.
Parentheses are not always essential. We can omit them when confusion is not likely to ensue:
sinx
cosx
lnx
Here only the last letter represents the argument. The rest of the letters are the functions designation. The function name may also be put out in front in certain rare circumstances. The factorial is an example:
x!
Here the exclamation mark can be thought of as both the functions designation, and also as an "operator" (we will eventually see that operations are really just functions).
The second use for function notation is to provide convenient labels for specific outputs of function, even when we don't necessarily know their exact value. To do this we replace the argument with any number permitted in its boundary. For example f(2) represents the output of the function f when the argument x=2. f(2) is not simply 2. f(2) may or may not be 2, depending on the nature of the function itself.
Function notation and its uses will become much more clear as we work out actual examples.
Restricted Process Functions
So far we have mainly focused on restriction of the Input and Output of a function. In this article however we want to move beyond mere definitions and give actual examples of the processing phase of a function. Firstly we'll want to restrict the kinds of processes to consider. At the same time however, we will not want to restrict it too much, as we are trying to gain as full an understand of the concept of single-variable functions as possible. To achieve this we will begin with the simplest kinds of processes: explicit maps, and work our way up to more sophisticated perspectives. Later we will expand the processes to include recursive, non-computable, and unknowable processes.
Explicit Maps
The simplest way to define a function is simply to predetermine exactly what the output is for any particular input. That is, we can explicitly create a map that tells us exactly what the results are. For example we might define a function in the following way:
input --> output
2 --> 6
7 --> 3
9 --> 1
4 --> 5
From this table we can gather a few of the basic properties of this function based on the terminology established in the last article. We can see that the boundary of the function is the natural numbers. Using the function notation, f(x), to represent our function we can "compute" certain values of the function.
For example...
to compute f(2) we simply look at the above table and observe the first row " 2 --> 6"
therefore when the input of our function is 2, the output is 6
we notate this as:
f(2) = 6
The only "computation" we had to perform was simply to see the answer on the table. Easy. None the less by our earlier definition of a function, this is clearly a function, although a very simple one. It as an input phase (choosing the input number), a processing phase (looking up the output on the table), and an output phase (displaying the output). We can see that we can easily "compute" several values for this function:
f(7) = 3
f(9) = 1
f(4) = 5
What happens if we plug in an input not represented on the table? Let's consider:
To compute f(1) we would look on the row with an input of 1 and ... ... ... ...
If a computer was asked to do this task it would simply never finish it. It could never find the row with input=1 because it simply doesn't exist. The value f(1) simply isn't defined, because we never bothered to define it. So f(1) = undefined. I often like to use the abbreviation ud. So we can say:
f(1) = ud.
f(3) = ud.
f(5) = ud.
etc.
By our previous definitions we can see that the Domain of f has to be only those values resulting in a valid output. Thus the Domain is the set {2,4,7,9}. The Image is the set {1,3,5,6}. What else can we say about such a function? Not much.
While such explicit maps are perhaps the most direct and natural way to define a function, by literally defining all its outputs, there are clearly some major drawbacks. Firstly, we can only map a finite number of input to outputs. We could never define a function in this way with an infinite domain. Another problem is a practical one. Even though the "computational" part seems pretty easy for this example, explicit mapping quickly becomes an impractical way to work with functions. Imagine if our explicit map contained thousands or even millions of input values. This would result in tedious look-up tables, where errors would be prone, and time would be needed to "compute" (look-up) certain values. Believe it or not, sometimes in science and engineering, when the behavior of a certain phenomenon is too complex to express as a simple elementary function, look-up tables are used instead. This is obviously not ideal, and should be avoided if possible, but if no other means of describing a function is available explicit maps are our fall back method for all functions.
In googology however we have no more than a theoretical interest for these kinds of functions. As you can probably surmise, they are completely useless for generating large numbers. Why? Because to "generate" such functions we actually have to supply it with all the answers. Therefore any "output" we get for a chosen "input" is simply a large number we already put there to begin with. Why then go through the trouble, since you could already define the large number in the first place?! So explicit maps can not serve any purpose for us. We need much more powerful ways to define functions other than an explicit listing of resultant outputs.
Explicit Functions of a Single Variable
The key, as you might have already guessed, is to come up with an explicit formula which relates the input to the output. A function defined through an explicit formula we will call an Explicit function.
Let "x" be the argument of our explicit function, f(x). To express how the function, which we will call "f", converts input to output we use the following explicit formula:
f(x) = 2x
This defines a function which takes any number as input and simply doubles it as output. To understand how this works it is best to simply try an example. To help visualize what going on imagine that our function, f, is really just a black box with some internal mechanisms for "computing" input into output. There is an input slot in which you can write any number on a slip of paper and insert into the machine. The machine then "processes" the information on the paper, and produces a number piece of paper out of the output slot on which is printed the double of the number you put into the machine. Let's imagine that we placed a piece of paper with a "3" written on it. What number will it print as output? We can simply use our explicit formula to find out:
We say that if x=3, then we simply "substitute" (3) for x in the explicit formula to obtain the value of f(x). This means we simply replace every occurrence of "x" with "(3)" in the formula:
f(x) = 2x
therefore...
f(3) = 2(3) = 6
therefore if x=3 then f(x)=6
So what kinds of numbers can we input into our black box? Well basically, any number, x, for which 2x is defined. Since the product of two real numbers is also a real number, the domain of the function f can be as wide as the real numbers. So we will say that the domain of f is the real numbers. We can therefore pick any real number and we would be able to find it's double.
Unlike our explicitly mapped function, where we had to state all of the outputs of the function individually, we only need one statement to define our explicit function, namely, "f(x)=2x". This rule is general over all of the real numbers, and it therefore defines a relation between an infinite number of inputs and outputs! The use of explicit formulas is very powerful, and gives us great flexibility in defining an infinite variety of functions with infinite domains. There is one draw back however: there is a limited number of functions that explicit formulas can express (technically the explicit formulas are countably infinite, where as the absolutely general functions of a single-variable are uncountably infinite, and therefore represent a much larger set. This implies that there are single-variable functions which can not be modeled by an explicit formula). Consider the explicit map that was defined under the previous heading. It would not be easy to devise an explicit elementary formula which gave those outputs at the specified inputs, and even if you could (probably be fitting a polynomial) I could just define another input/output pair for the map which would not match up with the formulas output. Doing this in an ad hoc manner ad infinitum would gradually generate an absolutely sporadic function! This suggests that there are certain functions which are just impossible for us to express in anyway what so ever because there is no formula to express them, and yet they have an infinite number of seemingly random output values. That being said however, the explicit functions are still quite vast, and will still be far more useful than explicit maps for generating large numbers.
Returning back to our function f(x)=2x, it might seem that since there are an infinite number input/output pairs we can't gain any general picture of what the function is doing. This is not true however. We can graph the function f(x) = 2x, by letting the horizontal axis of an infinite plane represent "x", and the vertical axis represent "f(x)". Each point on the plane represents a particular combination of real numbers, but only some of these combinations will represent an actual input/output pair of our function. The graph of f(x) = 2x looks like this:
The point where the horizontal (violet) and vertical (red) axes cross is known as the origin. The origin corresponds to the real pair 0,0. The property that the output is twice the input can be seen clearly reflected in the graph. Basically, for any point along the black line (the input-output pairs of the function f), we find that the distance along vertical axis from the origin is always twice that of the horizontal axis from the origin.
We will have little use for functions of a real-variable. Almost always we will restrict ourselves to only the natural numbers, and occasionally the integers. Any explicit formula which we could use to define a function of a real-variable we could also use to define a function of a integer or natural-variable. All we need to do is restrict our boundary to the set of integers or natural numbers.
Here is the same function, as a function of natural numbers:
In this graph, number pairs are not represented as points, but rather as squares on a grid. The output is represented by the height of the stack of colored squares. So for example, in the third column from the left we have a stack 6 high. In this way we can present natural-to-natural functions.
We actually won't have much need for graphs even of this kind. The reason is that most of the functions we will be studying grow far to quickly for a standard graph to be of any use (They quickly go of the edge of the page).
In any case we are now familiar with the different ways we can display a function.
But just what kinds of functions can we express with explicit formulas, and how can we use this to generate large numbers?
Exploring the Googologically Elementary Functions
At this point in the discussion we will restrict our discussion of explicit functions to those of a natural-variable, as this is the standard in googology.
To talk about the class of explicit functions we are first going to want to come up with a restricted and provisional definition of an elementary explicit formula.
I suggest the following:
An elementary explicit formula is one composed of elementary operations performed on constants and the argument of the function
What are elementary operations? These would be the seven elementary operations: addition, subtraction, multiplication, division, exponentiation, roots and logarithms. For googological purposes however we have little use for inverse functions, which almost always produce outputs smaller than their inputs, and which are not closed under the whole numbers. So we will discard division, roots and logarithms from this discussion. We will make an exception in the case of subtraction however, as it sometimes shows up in explicit formulas for certain recursive functions.
The kinds of functions we could define with only these operations which are total functions over the naturals, we will call the googologically elementary functions.
Thus we can say that the googologically elementary functions are total functions of a single-natural-variable defined by an explicit formula composed only of natural numbers and the argument of the function under the operations of addition, subtraction, multiplication, and exponentiation.
The googologically elementary functions are analogous to the elementary functions of professional mathematics, except with the restriction of division, roots, logarithms.
Here are some examples (I'm using "n" instead of "x" because the argument is meant to be in the set of naturals instead of reals):
f(n)= 2n+1
f(n) = 3n
f(n) = 3n-1
f(n) = 3n+4
f(n) = n^2
etc.
The functions we could generate with only these operations aren't particularly fast growing. For example if we let f(n) = 3n+4, then f(6) = 3(6)+4 = 18+4 = only 22. Not very large at all.
With the exponent we can define functions that grow with moderate speed. For example, consider the unary function:
sq(n) = n^2
This is the square function (hence the "sq" as the function name). It returns the square of the input. This is well defined over the integers. Here we have some example values:
sq(1) = 1^2 = 1*1 = 1
sq(2) = 2^2 = 2*2 = 4
sq(3) = 3^2 = 3*3 = 9
sq(4) = 4^2 = 4*4 = 16
sq(5) = 5^2 = 5*5 = 25
...
sq(10) = 10^2 = 10*10 = 100
The square function doesn't produce very large numbers, but we can get larger values by choosing a larger power. For example we might look at the cubic function:
cu(n) = n^3
We would have the values:
cu(1) = 1^3 = 1*1*1 = 1
cu(2) = 2^3 = 2*2*2 = 8
cu(3) = 3^3 = 3*3*3 = 27
cu(4) = 4^3 = 4*4*4 = 64
cu(5) = 5^3 = 5*5*5 = 125
...
cu(10) = 10^3 = 10*10*10 = 1000
Higher powers will produce a succession of vaster growing googologically elementary functions. However we can get a function which is faster than all of these (in a technical sense) by placing the argument in the exponent instead of the base. For example, let:
ex(n) = 3^n
We then have the values:
ex(1) = 3^1 = 3
ex(2) = 3^2 = 3*3 = 9
ex(3) = 3^3 = 3*3*3 = 27
ex(4) = 3^4 = 3*3*3*3 = 81
ex(5) = 3^5 = 3*3*3*3*3 = 243
...
ex(10) = 3^10 = 59,049
That's a little better, though still pretty paltry by googology standards. What could we do to get an even faster function? We could put the argument in both the base and exponent. This function has even been given a standard name (we'll learn about it in the next chapter as well as some even faster growing ones):
fz(n) = n^n
Here are some values:
fz(1) = 1^1 = 1
fz(2) = 2^2 = 4
fz(3) = 3^3 = 27
fz(4) = 4^4 = 256
fz(5) = 5^5 = 3125
fz(6) = 6^6 = 46,656
fz(7) = 7^7 = 823,543
fz(8) = 8^8 = 16,777,216
fz(9) = 9^9 = 387,420,489
fz(10) = 10^10 = 10,000,000,000
Now we are starting to get somewhere. The "fz" function grows a little faster than exponential, but we are still generating numbers well within our means. How can we progress even further. We'll according to our definition we said anything that only involved addition, subtraction, multiplication, and exponentiation was elementary, so why couldn't we stack exponents. Let:
hypx(n) = 2^(2^n)
This function (the hyper-exponent function, or hypx for short) will quickly outclass the fz function:
hypx(1) = 2^(2^1) = 2^2 = 4
hypx(2) = 2^(2^2) = 2^4 = 16
hypx(3) = 2^(2^3) = 2^8 = 256
hypx(4) = 2^(2^4) = 2^16 = 65,536
hypx(5) = 2^(2^5) = 2^32 = 4,294,967,296
...
hypx(10) = 2^(2^10) = 2^1024 =
179 769 313 486 231 590 772 930 519 078 902 473 361 797 697 894 230 657 273 430 081 157 732 675 805 500 963 132 708 477 322 407 536 021 120 113 879 871 393 357 658 789 768 814 416 622 492 847 430 639 474 124 377 767 893 424 865 485 276 302 219 601 246 094 119 453 082 952 085 005 768 838 150 682 342 462 881 473 913 110 540 827 237 163 350 510 684 586 298 239 947 245 938 479 716 304 835 356 329 624 224 137 216
Woah, that's more like it! This number is slightly larger than E308, so its bigger than a centillion. Note that it wasn't difficult to define this function with exponents, and that are input is still pretty small. The number of digits in the output is actually roughly doubling every time the argument increases by 1. So imagine how large hypx(100) is! or hypx(1000), or hypx(centillion)! Yikes! As you can see, the function notation is already making what was arduous before, a simple matter. And we can get even faster growing elementary functions simply by stacking more and more exponents:
2^(2^(2^n))
2^(2^(2^(2^n)))
2^(2^(2^(2^(2^n))))
etc.
The key here is that once we define a fast growing function its recyclable. For example, say that I define:
fast(n) = 10^(10^(10^(10^(10^(10^(10^(10^(10^(10^n)))))))))
I can now easily define fast(1), fast(2), fast(3), ... fast(100), ... fast(1000), ... fast(centillion). Every time I chose a new argument I don't have to rewrite the whole stack of exponents. fast(n) serves as a shorthand. Using conventional methods the best I can do to describe a really large number is to write out a large series of exponents explicitly. At very least we can see that this process can be automated with the concept of a function.
So what, you might say. We were generating numbers like this previously without the concept of a function. All we've done is made something we could already do easier. But how does this help us go beyond what we could do before? Well understand that the upshot of making the difficult easy, is that the even more difficult becomes obtainable. So even in this limited sense, we can already guess this handy shorthand trick is probably going to come in handy down the road. But this is really just the tip of the iceberg. I haven't even begun to tap into the full power of functions. It gets much better than this, just bare with me...
Piecewise functions
So far we have come up with two ways to actually define functions: explicit maps, and explicit formulas. A third way which combines the two approaches is used to define piecewise functions. Although we can achieve a great deal of variety with explicit formulas, we are still somewhat limited in what we can express in this way. To give us even greater variety in the functions we can actually define, we can cut and paste previously defined functions to create new functions. How does this work? Well first imagine taking a set of n functions. For this example let's just use two:
f(x) = 2x
g(x) = x^2
As we know, both of these functions are defined over all the real numbers, since every real number has both a double and a square. To create a new piecewise function out of f and g we define a new function, h, where:
h(x) = f(x) if x < 2
&
h(x) = g(x) if x>=2
Note that h(x) is not defined by a single formula, but is rather defined by two, and which formula is used is determined by the value of x being "plugging into" h. Here is a table of values for our new function h:
I have displayed f and g along with h so that you can see how h(x) borrows from each function and combines them into a distinct function. What makes it distinct from both f and g even though it borrows from both of them. Here is the definition for distinction:
Two function, f(x) & g(x), are distinct from each other if and only if there exists at least one x such that:
f(x)=!g(x)
Conversely two functions are identical if for all x f(x) = g(x)
Note that according to this definition it doesn't matter how the two functions f(x) and g(x) might process input into output. Even if they have very different processes if the outputs are identical for any given input than the two processes define the same function. The processes are therefore not the functions themselves, but only the ways in which we make the function manifest.
By this definition h(x) is distinct from both f(x) and g(x). Why? because:
h(4) =! f(4) since h(4) = g(4) = 4^2 = 16, and f(4) = 2*4 = 8
So h(x) and f(x) are distinct
h(1) =! g(1) since h(1) = f(1) = 2*1 = 2, and g(1) = 1^2 = 1
So h(x) and g(x) are distinct
This should make it obvious that by including piecewise methods into our function defining tool box we are able to express even a broader class of functions.
We can combine as many functions as we like for any values we chose in our piecewise functions, within the limits of what we can actually express.
The piecewise functions will give us no greater ability to express large numbers at this point, since a piecewise function is simply and amalgamation of the same elementary functions we've already seen. The reason I am introducing them here however is that later we will see that all the higher recursive functions are really just piecewise functions of a more general sort.
Functions of a Natural Value and Sequences
Before I move on to the next topic, I would like to point out an important connection between Functions of a Natural value and sequences. The concept of a sequence has certain advantages, like functions, that help us generalize processes for generating large numbers.
Basically a sequence, is a serial list of numbers, with a first member, a second member, and so on. A finite sequence, has a last member, but an infinite sequence does not.
The natural numbers are an example of such a sequence:
1,2,3,4,5,6, ...
The idea of a sequence can be related directly to the notion of a function, because we can ask the question, "what is the nth member of the sequence". The answer is the nth member of the sequence. Thus we can think of as "n" as an input to the function, and the nth member as the output. For the nth member of a sequence I usually like to use the notation S(n), which is really just a function. By letting S(n) be defined via an elementary function, we also define an infinite sequence. So we could let S(n) = n^3+n^2. We then get the following function values:
S(1) = 1^3 + 1^2 = 1 + 1 = 2
S(2) = 2^3 + 2^2 = 8 + 4 = 12
S(3) = 3^3 + 3^2 = 27 + 9 = 36
S(4) = 4^3 + 4^2 = 64 + 16 = 80
etc.
We can then form an infinite sequence by letting S(1) be the 1st member of the sequence, S(2) the 2nd member, S(3) the 3rd, etc. Thus we form the sequence:
2,12,36,80, ...
Sequences, especially growing sequences, are a good way to conceptualize growth rates. For a fast growing sequence, we can think of generating a large number by plugging a large argument into a function as analogous to skipping far ahead in the sequence. This ability to "skip" the in between steps will become our key to blasting off towards infinity!
Conclusion
As amazing as all this is, we still have only a very narrow understanding of what a function is. Do not fall into the misconception that a function is merely a explicit formula. A function is more general than that. A function also shouldn't be thought of as purely operating on "numbers", but rather as an "interpreter of symbols". This more advance view however will take time to develop and formalize. Our first step will be to expand the boundaries of functions (both literally and figuratively) beyond single-variable inputs to multi-variable inputs. We will find this more general notion of a function far more useful and freeing for googology.