This essay was begun in January 2002. Correction added Aug. 13, 2004, to include an inadvertently omitted "undecidable of the third kind." As the bulk of this essay was written nearly two decades ago, it does not necessarily represent my current thinking.
Without going into an extensive examination of phenomenology and the psychology of learning, perception and cognition, let us consider the mind of a child.
Think of Mommy controlling a pile of lollipops and crayons, some of which are red. In this game, the child is encouraged to pick out the red objects and transfer them to 'his' pile.
The child employs a mental act of separation (some might call this 'intuition') to select out an item, in this case by direct awareness of the properties of redness and of ease of holding with his hands. This primal separation ability is necessary for the intuition of replication. Crayon and lollipop are 'the same' on account of redness. In turn, this intuition of replication, or iteration, requires a time sense, whereby if the child hears 'more' he associates the word with an expectation of a craving being satisfied ('more milk').
The child becomes able to associate name-numbers with iteration, such that 'one thing more for me' becomes 'one thing,' which in time is abstracted to 'one.' A sequence of pulses is not truly iterative, because there is no procedure for enumeration. The enumeration procedure is essentially a successor function, with names (integers) associated with each act of selection by replication intuition. Likewise, we must have amorphous 'piles' before we can have sets. As adults we know that the 'mine' pile and the 'Mommy' pile have specific, finite numbers of elements. But we cannot discern the logico-mathematical objects of set and element without first having a concept of counting.
That is, in the minds of small children and of adults of primitive cultures, integers are associated with intuitively replicable material objects, such as apples and oranges. But the names are so useful that it is possible to mentally drop the associated objects in a process of abstraction. That is, we might consider an integer to be quite similar in spirit to an 'operator.' Whatever objects are associated with operators, a common set of rules of manipulation applies to the operators alone.
Platonism vs. intuitionism
Cantor's acceptance of 'actual infinities' seems to me to require a platonic concept of ideals: forms or formalisms that count as existing a priori.
The intuitionists, led by Brouwer and partially supported by Wittgenstein (and Kronecker before them), would object to a set or, possibly, a number that 'cannot be constructed.' Related to this division is the dispute as to whether a theorem or mathematical form is discovered, as the platonists see it, or invented, as the intuitionists see it.
I don't intend to inspect every wrinkle of these controversies but rather to focus on the concept of existence of mathematical statements and forms.
Forthwith, let's dismiss the concept of 'potential infinity' that was in vogue in the 19th century as a means of describing a successor operation. 'Potential' invokes the thought of 'empowered to achieve an end.' To say that 'potential infinity' is conceptually acceptable is to say that 'actual infinity' is also permissible.
Let us accept the Zermelo-Fraenkel successor set axiom as underpinning proof by induction and as underpinning open-ended successor functions, such as the function f(n) = n+1, which describes the natural numbers. This axiom is often known as the infinity axiom, but we are not, without further thought, entitled to take that leap. The successor axiom says that a recursion function needn't have a specific stop order. We may visualize a computer that spits out a stream of discrete outputs nonstop. (An issue here is that in thinking of a nonstop successor algorithm, we assume units of time being 1:1 with N, the set of natural numbers. Alas, our mental picture is inadequate to overcome the interdependence of primitive concepts.)
So at this point the successor axiom permits us to build ever-larger finite entities but does not permit us to assume some 'limiting value' associated with a particular successor function. Yet such limits are highly desirable.
Let us consider irrational reals. In the case of square roots, a geometric form -- the hypotenuse of a right triangle -- can be measured by a ruler (we neglect the issue of accuracy of the ruler, an issue that also applies to rationals) in less than a minute. Most would agree that the distance expressed by a square root exists and can be plotted on a number line, justifying the naming of that distance by a symbol such as x0.5.
However, other irrationals, such as 20.2 can be only ever-better 'approximated' as a rational by some successor function, such as Newton's method or an 'infinite' series. Because the nested interval in which such an irrational is found grows smaller and smaller, we might through careless thinking suppose that we can justify some limiting distance from origin because we believe we are getting closer and closer to an interval of zero length. But our successor function requires eternity to exactly locate that point. So in human terms, such a distance is unmeasurable and might be said by some to be nonexistent. Still, the difference between two nonstop successor functions, unequal in every finite output, may still be held to grow ever smaller, helping to justify existence of such a point.
Now, should we regard this distance/number as a fait accompli or should we regard it as impossible to achieve?
Consider the circle. Is the circle an ideal thought form that axiomatically pre-exists geometry or is it an artifact of human ingenuity which in fact doesn't exist because a 'true circle' requires a nonstop algorithm -- perhaps the positing of a a set of n-gons of evermore facets? (Then of course the straight line, the point and the plane must be accepted a priori.)
Daniel J. Velleman (Philosophical Review, 1993) proposed that constructivism be 'liberalized' to accept countable infinities (but not uncountable ones) on the grounds that 'performing infinitely many computations is not logically impossible, but only medically impossible.'
Yet, an intuitionist or constructionist might disagree that such a performance is logically possible, but rather argue that the term 'countable infinity' is simply a phrase for describing extension by induction. That is,
If X is infinite and countable, then x ∈ X <--> x+1 ∈ X.
Still, we are implicitly assuming that time is already divided into a countably infinite number of unit 1 intervals. That is, we face a circularity problem.
Nevertheless, the inductive model of X does not require that X ever be complete. That is, we can write
∃n ∈ N ∀ m ∈ N ∀ t ∈ T ( f(tm)--> (x ∈ X <--> x+1 ∈ X))
We would say that T is an ideal in P-space and not a result of a performable algorithm.
It seems quite evident that the pure constructivist program falters on the issue of time.
The issue is interesting because the successor axiom brings us to the issue of paradoxes (or antinomies), in particular those of Russell and Cantor. Though such paradoxes may be ruled axiomatically out of order, such an approach leaves a mild sense of disquiet, though I fear we must, if pressed, always resort to axioms.
At any rate, the value of a fundamental contradiction is that it demonstrates that a system of rules of thought based on form alone is insufficient to express the 'stuff' of being. And, of course, such a contradiction may pose serious questions as to the usefulness of a theory; I have in mind Cantor's paradox to the effect that the cardinality of U, the set of all sets, is unstable.
Following the Brouwerian path, Wittgenstein, who disliked such self-referencing anomalies, tried to dispose of them through a philosphical appeal to constructionist ideas. Cantor's champion, Hilbert, tried to limit the use of 'ideals,' but was nevertheless pushed to defend the notion of infinite totalities, at least implicitly. Without infinite totalities, or actual infinities, Cantor's paradise would fall.
The dispute between, essentially, platonists and constructionists is not resolvable without further elucidation, and is unlikely ever to be fully resolvable.
I suggest introduction of two axiomatic, or, primitive, concepts: a realm of thought assigned a timelike property, which, for short, we might dub T-space, for time-controlled, or Turing, space; a realm of thought with the property of timelessness, which we might dub P-space, for Platonic space. These spaces, or realms, are not topologically definable.
Now we are in a position to say that rules of mathematical thought that exist in T-space do not exist in P-space. There are no set-theoretic rules or relations in P-space, because no timelike operations.
We are permitted to collect all P-space objects into a set, but P-space itself is axiomatically not a mathematical set. The set of P-space objects is however an ideal and a resident of P-space.
Now, a P-space ideal may be exported to T-space and used in operations. Even so, if a P-space ideal is related to a T-space recursion function, the recursive's successor rule may not be applied to the ideal (no self-referencing permitted).
For example, a limiting value -- no finite nth step of an algorithm can go above it, or below it -- is permitted to exist in P-space. Likewise, the 'construction' of a circle occurs in T-space. The limiting form, a pure circle, is assigned to P-space.
At this juncture, it is necessary to point out that some constructions are purely logical, while others require repetitive computation. A recursion function, such as an algorithm to obtain pi, cannot yield an output value without the previous output value as an input value. That is, computation follows Fno F(n-1) o F(n-2) ... F0, where F0 is the initial step of a composite function. Here construction occurs by 'building' one brick at a time. In the case of, for example, [lim n--> inf.] n/(n+1), a recursive computation does not occur. However, an inductive logical operation does occur. That is, we mean that n/(n+1) < (n+1)/(n+2) < 1 for any finite n. Does such a logical relation imply 'construction'? We may say that it can be thought of as a secondary form of construction, since values of n are constructed by f(n) = n + 1.
Still, whether we have direct recursive construction or only indirect recursion, we place such mathematical operations in T-space. Because T-space is considered to be timelike, we avoid the issue of which comes first, the algorithm or the ideal.
Relations between T-space and P-space
An actual infinity can be defined as nondenumerable if it cannot be produced by a nonstop n-step algorithm. The algorithm's logical form is inductive: If property p holds for step n, then property p holds for step n+1.
In the case of a denumerable infinity, it is always possible to relate this platonic-space ideal to a Turing-space induction condition. However, simple induction of course is insufficient to justify a nondenumerable infinity. Cantor's diagonal proof of the nondenumerability of the reals uses the contradiction of the possibility of simple induction. Here we have a situation where the set of irrationals exists in P-space but the rule of inference in T-space is not induction alone.
So at this point we assert that if a relation between a P-space ideal and a T-space procedure cannot be justified to the satisfaction of the mathematical community, then we would say that the ideal is not recognized as a mathematical object, even if it be in some way numerical. For example, an infinite digit string which is a priori random would seem to have no direct relation to a T-space procedure, though perhaps an indirect relation might be found. However, if we set up a no-halt order procedure for pseudorandomly assigning at step n a digit to the nth digit space, the P-space ideal of an infinite pseudorandomly digit string would be held to exist as a mathematical object in P-space, being justified by an inductive claim: no matter how great n, there is no step at which the entire digit string inclusive of the nth digit can be known in advance.
In the case of a strict induction model for a geometric ideal, such as a curve, we can partly justify analytic methods here but the issue of the real continuum must also be addressed (see below). That is, we can say that if an n-gon with all facet endpoints equidistant from a centerpoint can be drawn, then a like (n+1)-gon can also be drawn. We relate this induction model to the ideal of a true circle by saying that 0 is the 'limiting value' of n-gon facet length.
Likewise, we can authorize the 'area under a curve' using a numerical 'approximation' induction model.
A significant analytic issue here is raised by the induction model of obtaining arc length as a sum of approximated line segments. As n is increased, the difference in facet length decreases, so that at the limit of 0 length, all points are of equal length. Yet, each point on the arc is 1:1 with a point on the axis, which are also of 0 length. Yet the infinite sum of the points of the arc may be unequal to the infinite sum of the points on the axis interval. Does this mean arc zeroes are unequal to interval zeroes? Anyway, isn't 0 x infinity equal to 0?
We can always write off such a puzzlement as 'counterintuitive' and leave it at that. But I think it might help to say that the ideal associated with the T-space arc formula A is not identical with the ideal of the T-space arc formula B. We cannot in this case 'compare zeroes.' But we can say that ideal A is a quantum-like ideal where the zero is related to a sub-ideal which we call an infinitesimal quantity. And infinitesimal quantities may be unequal.
Perhaps you accept that the epsilon-delta proofs of analysis have killed off the dread infinitesimal. By that you mean that the induction method obtains a numerical limit but that pure geometric forms are not in fact mathematical objects. The number exists but the curve is not 'constructible.' The 'actual infinity' that makes 'all' points of a curve 1:1 with 'all' points of a line does not exist in this scenario.
Yet if ideals are sometimes necessary in mathematics, why arbitrarily rule out a particular ideal, such as an infinitesimal?
I do not wish to assert that fundamental issues are now, voila!, all resolved. I simply say that the concepts of T-space and P-space may make us more comfortable from the standpoint of consistency. Yet, more reflection is needed as to what these concepts mean with respect to Goedel's incompleteness theorems.
Goedel's incompleteness theorems say that for a consistent formal system F based, for example, on Peano arithmetic, there is always a true statement P that cannot be proved in F.
If we extend F (call it F1) by adding P as a nonlogical axiom of F, then there is a statement PF that is true but not provable in F1.
We can define a set of systems such that Fn+1 is the formal system obtained by adding PFn as a nonlogical axiom to Fn.
So we have a T-space construction routine, or recursion algorithm, for compiling formal systems such that Fn --> Fn+1 --> PFn+1 is true but not provable in Fn+1.
If we define a P-space ideal lim n--> inf. Fn, we see that Goedel's result does not apply, since constructive activity is not permitted in P space, in which case the Goedel sentence PFn is not defined.
On a more fundamental level, we may wish to address the issue of belief that a theorem is true, based on our particular algebra, as against the theorem being a priori true, regardless of what one believes.
Consider what Wittgenstein saw as 'Moore's paradox,' which he obtained by coupling the statements 'There is a fire in the room' and 'I believe there is no fire in the room.' If statement A is a priori true, then, according to some, we would face a fundamental paradox.
You respond perhaps that one does not say 'There is a fire in the room' without either believing or not believing the assertion, whether or not there is an a priori truth to support it. That is, the truth value of a 'fact' is meaningless without a mind to review it. A cognitive act is not precluded by the notion that 'experience tells one' that previous sensory impressions (beliefs) about fire leads one to anticipate (believe) that one's current sensory impression about fire is valid.
So then, does a mathematical ideal require belief (perhaps justified by T-space inference) in order to exist? We come down to the definition of 'exist.' Certainly such an ideal cannot be apprehended without cognition. If, by cognition, we require a sense of time, then we would say that ideals are 'pointed to' from T-space thought patterns but also might exist independently of human minds in P-space, though of course the realms of mentation designated platonic space and turing space presuppose existence of some mind.
Of course, we must beware considering T-space to be a domain and P-space a range. These spaces are a priori mental conditions that cannot be strictly defined as sets or as topological objects.
Coping with paradoxes
Consider Cantor's paradox. The definition of power set permits us to compute the quantity of all elements of a finite power set. In every case, there are 2n elements. But does an actual infinity, U, the set of all sets, exist? Since U is a set, shouldn't it have a corresponding actually infinite power set? What of the contradiction (with U' meaning power set) expressed:
U ⊂ U' ⊂ U'' ⊂ U''' ...?
Our response is that U, as a P-space ideal, may not have its 'shadow' generation rule applied to it. We can also accept U', as a P-space ideal, which also cannot have its shadow generation rule applied to it. Though we might export U or U' to T-space for some logico-mathematical operation, we cannot do the operation U ⊂ U', which requires application of set-building rules on U, a banned form of self-referencing.
In general, we prohibit a successor rule from being applied non-vacuously to an actually infinite ideal. For example, [lim n->inf.](n) + 1 = n is simply the vacuous application of a successor rule.
Similarly for Russell's paradox: R, the set of 'all' (here assuming 'all' signifies an infinitude) sets that contain themselves as members, and S, which is R's complement, exist as P-space ideals. If exported to T-space a successor rule cannot be applied. So the question of whether R ∈ R is prohibited. However the T-space operation R ∪ S = U is permitted.
An infinite (or open-ended) set 'generated' by a successor rule requires a concept of time, which includes the concept of 'rate of change' (even if the rate is an unobtrusive 1). If we talk about a completed denumerably infinite set, we are saying that 0 is the limiting value of the generation algorithm's rate of change.
Let A be a finite set and P(A) be the power set of A. We now specify
P(A)-->P(P(A)), which we may express P[0](A) --> P[1](A).
So, in general, we have P[n](A).
Now to indicate the power set of the set of all power sets, we write
lim n--> ∑ P[n](A) The usual way to dispose of this paradox is to say that though a collection is an extension of the set concept, a collection is not necessarily a set. Hence the collection of all sets would not itself be a set -- a theorem stemming from the ZF axioms.
However, here we address the paradox by saying that, if the denumerably infinite set is construed as completed, then the generation algorithm's rate of change is 0, as in
lim n--> ∑P[n+1](A) = lim n--> ∑P[n](A).
In other words, lim n--> ∑P[n](A) exists in P-space and a 'self-referencing' T-space algorithm is prohibited.
The principle of the excluded middle
The principle of the excluded middle -- which is often read to mean a logico-mathematical statement is either true or false, with no third possibility -- was strongly challenged by Brouwer, who argued that the principle is unreliable for infinities. Our rule of prohibiting 'self-referencing' operations on ideals helps address that concern.
The reliability of the principle of the excluded middle is a concern in, for example, the Goldbach conjecture.
Let us define the Goldbach conjecture inductively as
i) Q = ((P(2x) --> P(2(x+1)))
A disproof requires
ii) ~Q = ~((P(2x) --> P(2(x+1)))
There is also the possibility that neither i) nor ii) is decidable [using '+' for the exclusive 'or']:
iii) ~(Q + ~Q)
Here we see a point where platonists and intuitionists clash. The platonists, rejecting iii) as a way of writing 'Q is undecidable' would claim that merely because we cannot know whether Q or ~Q is true does not mean that it is false that either has a truth value. The intuitionists would argue that Q's alleged truth value is of no mathematical interest.
If we accept iii), we must require that De Morgan's law not apply to the exclusive 'or,' even though truth tables for ~P v Q and ~P + Q are identical.
De Morgan's law transforms iii) into ~Q & Q, which is false by contradiction.
However,
P v Q = ((P & Q) + (P + Q))
But if P = ~Q, we would have
~Q v Q = ((~Q & Q) + (~Q + Q))
Yet the contradiction ~Q & Q is disallowed.
A similar philosophical perplexity arises from the question of whether Euler's constant is rational or irrational. The constant g is considered to be a number on the basis of at least one induction model. To wit:
lim --> ∑1/n - Ln 1/n = γ
where γ is an ideal constant.
It is quite plausible that gamma's rationality is undecidable, that there is insufficient data to determine rationality. So the statement 'gamma is rational' may not have a knowable truth value. Does it have an a priori truth value? Many mathematicians would assert that if a truth value is unknowable, the issue of a priori truth value is irrelevant.
Still, undecidability is most satisfactory if proved. Our position would be that, in the case of gamma, the irrationality conjecture would be proved undecidable if rationality could never be decided without application of a successor rule on gamma.
In the case of the continuum hypothesis, we see a case where a logico-mathematical statement has a 0 truth value, validating the warning against unrestricted use of the principle of the excluded middle. Goedel and Cantor have collectively shown that Cantorian and ZF set theory contain insufficient information for a yes or no answer to the conjecture, which says that there is no Cantorian cardinal number between cardN (or Aleph_null, if you like) and cardP(N) (another Aleph).
The implicit flaw in the continuum conjecture is the expectation that the conjecture is either true or false. If you draw a playing card face down from a well-shuffled deck an do not turn it over, the proposition 'the card is a face card' is either true or false -- even if you do not examine the obverse before shuffling the card back into the deck. Though the truth value remains forever undecidable, it is presumed to have an a priori truth value. I call such a proposition an undecidable statement of the first kind.
The continuum conjecture is then an undecidable statement of the second kind -- undecidable because the statement has no truth value in some logic system, whether that system be sharply or fuzzily defined.
[Thanks to Paul Kassebaum for drawing my attention to a difficulty with my categorization of undecidables. It seems that I inadvertently omitted the category of undecidable statements of the third kind, which would cover questions that are notionally answerable but which are computationally too difficult. For example, it is computationally imposssible to even name most numbers, let alone compute with them. However, Paul had a good point in noting that computational difficulty seems to fit my "first kind" category, in that, from a Platonist perspective, both categories have a priori answers that are inaccessible.
In addition, a "fourth kind" seems in order: the obvious one stemming from Goedel's incompleteness theorems: a sufficiently rich complete system contains at least one undecidable statement.]
There is of course the issue of the provability of the assertion that the playing card is either a face card or not; taking a cue from the Copenhagen interpretation of quantum mechanics, we cannot be sure that the two realities are not combined into a superposed state, with neither reality in existence until an observation is made. Though such an interpretation is normally applied to the nanometer world, the thought experiment about Schroedinger's cat shows that quantum weirdness can be scaled up to the macro-world. We cannot be sure that 'reality' does not work that way. (See 'The resurrection of Schrodinger's cat' at the link above.)
I have been unable to think of a logico-mathematical statement that is an undecidable of the first kind and I conjecture that such a statement cannot be proposed.
Of course, propositions of the second kind are common in mathematics, as in: 'The nth integer is prime.'
Goedel and Cohen have proved the continuum hypothesis to be such a 'meaningless' statement; similarly our scheme makes the paradoxes of Russell and Cantor equivalent to an undecidable of the second kind.
In our model, we would say that cardN
and cardP(N) are P-space ideals but that a cardX such that cardN less than cardX less than cardP(N) is not a mathematical object in P-space because no inference rule exists relating a T-space procedure to a P-space ideal.
In a 1930 paper, Heyting
(appearing in 'From Brouwer to Hilbert,' compiled by Paolo Mancosu, Oxford, 1998), says the intuitionists replace the concept 'p is false' with 'p implies a contradiction.' So then, ~p is a 'new proposition expressing the expectation of being able to reduce p to a contradiction' and '|- ~p will mean "it is known how to reduce ~p to a contradiction".' Hence comes the possibility that neither |- p nor |- ~p is decidable.
Heyting notes that |- ~~p means 'one knows how to reduce to a contradiction the supposition that p implies a contradiction,' and that |- ~~p can occur without |- ~p 'being fulfilled,' thus voiding double-negation and the principle of the excluded middle.
Through tables of such inferences, Heyting derives the logico-mathematical inference states of proved, contradictory, unsolvable, unprovable, not unprovable, not contradictory and not decided.
On the continuum
The obvious way to define the reals is to posit 'any' infinite digit string and couple it to every integer. Of course, Cantor's diagonal argument proves by contradiction that the reals cannot be enumerated. Since the rationals can be counted, it is the irrationals that cannot be.
It is curious that the if f is a function that yields a unique real, the family of such functions, Uf, is considered denumerable. That is, we might try to list such writable functions by i e I. We could then write an antidiagonal function g = f_i(i) + 1. But logicians disdain this type of paradox by requiring that f be written in a language L that imposes a finite set of operations on a finite set of symbols. It is found that the function g cannot be written without resort to an extended language L'.
(It is however possible to establish a nondenumerable subset of irrationals that is 1:1 with a subset of writable functions f if we permit the extended language L'. See 'Disjoint nondenumerable sets of irrationals' above.) So then we find that Cantor's diagonal proof reduces to an existence theorem for a subset of reals undefinable in some language L. To put it another way, such a real is 'unreachable.' We cannot order such an r by the inequality p/q < r < s/t (with p,q,s,t e Z) because we cannot ascertain p/q or s/t.
In my view, such unreachable reals are ideals. They exist in relation to the ideal of the totality of reals. But their shadows do not exist in T-space. So they have low relevance to mathematics. In fact, we cannot even say that the subset of such reals contains individual elements, raising a question as to whether such a subset exists. Again, the subset is a P-space ideal, and the T-space method of defining this subset by individual elements does not apply.
So then we have that cardR (whatever aleph that is after aleph-null) becomes a shorthand way of saying that there exists a set of irrationals whose elements are undefinable in L.
The concept of nondenumerability is useful in that it conveys that the set of irrationals is much 'denser' than the set of rationals. This gives rise to the thought of ordering of infinities with transfinite numbers. But 'X is nondenumerable' means X is ~cardN. The continuum conjecture could be expressed cardN < cardM < cardR. But it can be better expressed cardN < cardM < ~cardN. This last expression succinctly illustrates the result of the labors of Goedel and Cohen: that the conjecture is 'independent' of set theoretic logic.
Arithmetic recursives
Consider
åio i
We might call this a paradigm iterative function, where the domain and range intersect except at possibly initial and final (or limit) values. Such a function is considered 'non-chaotic' because the sequence is considered informative. That is the naming routine of å i is the same as the naming routine for i. The digit-place system is considered informative because we can order a number y less than x less than z in accord with this naming routine. That is, we know that 52 > 5 because of the rules of the digit-place system.
As shown below, a recursive function may be construed as non-chaotic if the recursive f is writable as some simple well-known function, such as n or n!
An arithmetic recursive can be written:
f(n) = h(n)f(n-1) + g(n)
We note that h(n) and-or g(n) can also be recursive, for a composite of the type: h(n) =k(n)h(n-1) + l(n)
and that it is also possible to have such expressions as
f(n) = h(n)f(n-1) + f(n-2)
where f(n-2) kicks in after a kth step of f(n).
A few recursive sequences:
h(n) = n, g(n) = 0
f(0) = 1, f(n) = n!
In general, if g(n) = 0, then f(n) = Õh(n).
h(n) = (n+1)/n, g(n)=n
f(0) =1, f(n) = 4, 9, 16 = n2; f(0) = 0, f(n) = 3/2, 3, 19/4...
h(n) = 1/n, g(n) = 1
f(0) = 1, f(n) = 1, 3/2, 11/8...
h(n) = 1/n, g(n) = n
f(0) = 1, f(n) = 2, 3, 4... = n
h(n) = 1/n, g(n) =1/ n
f(0) = 1, f(n) = 2, 5/2, 7/6, 13/24...
h(n) = 1, g(n) = 1/n
f(0) = 0, f(n) = 1, 3/2, 5/6 ...
f(0) = 1, f(n) = 1, 2, 5/2...
h(n) = n, g(n) = n
f(0) = 1, f(n) = 2, 6, 21...
h(n) = -n, g(n) = -n
f(0) = 0, f(n) = 0, -3, 8, -45 ...
h(n) = -n, g(n) = n
f(0) = 0, f(n) = 1, 0, 3, -8, 45...[recheck]
h(n) = -n, g(n) = -1
f(0) = 0, f(n) = -1, 1, -4, 15, -66...
if g(n) = 1, we get f(n) = 1, -1, 4, -15, 66...
Basic manipulations of such recursives:
Let f_k express h(n)f(n-1) + g(n) where f(0) = k and k is any real initial value.
If g(n) = 0, then f_k/f_j = (Õ h(n)k)/(Õ h(n)j) = k/j.
f_k - f_j = Õh(n)k - Õ h(n)j = Õ h(n)(k-j)
This last expression yields a function
m(k-j) = h(n)f(n-1) + 0g(n)
Denoting the discrete first derivative of f as f', we have, if h = 1:
f'(n) = f(n) - f(n-1) = g(n).
If h does not equal 1 at all values, we can write f' as an inequality, as in
h'(n) £ f'(n) £ g'(n), or g'(n) £ f'(n) £ h'(n)
Example:
f(n) = (n2 + (1)f(n-1) + n3
g'(n) is polynomial but Õ k(n^2 + 1) changes exponentially. Hence after some finite value of n, we have, assuming k is a positive integer:
3n2 < f'(n) < [Õ k(n2 + 1) - Õ k((n-1)2 + 1)]
Example:
f(n) = (n2 + 1)f(n-1) + Õ (n3 + 1)
Because g(n)'s exponential rate of change is higher than f(n)'s, we have, after some finite n:
h'(n) < f'(n) < g'(n)
Such inequalities are found in recursive ratios fa/fb, where fa =/= fb
For example, the irrational z(-2) can be written:
fa(n)/fb(n) = [n2fa(n-1) - (n-1)2!]/n2!
At step n+1, the ratio has a numerator that contains an integer greater than the numerator integer for step n; likewise for the denominator.
We see that ever-greater integers are required. Assuming the limit of fa/fb is constant, when this ratio at step n is converted into a decimal string, the string lengthens either periodically or aperiodically.
So we might say that [lim n-> inf]fa is an 'infinite integer' -- or a pseudo-integer. An irrational can be then described as a ratio whereby two pseudo-integers are relatively prime. Or, we might say that there exists a proof that if the ratio is relatively prime at step n, it must be relatively prime at step n+1.
Obviously [?], the set of pseudo-integers is 1:1 with the reals, a pseudo-integer being an infinite digit string sans decimal point.
If we require that a real be defined by a writable function based on the induction requirement, then the set of reals is countable. But if we divorce the function from the general induction requirement, then the set of reals is nondenumerable, as discussed here.
Do your best to present yourself to God as one approved, a workman who has no need to be ashamed, rightly handling the word of truth.
