Isn't "transitive" the wrong word?

[Janice Caron]

On 06/04/2008, Jeff Nowakowski <jeff at dilacero.org> wrote:
>  I'd be interested in your definition of "recursive", given at the same
> level of detail with which you examined "transitive".

Wikipedia defines recursion as follows:

Recursion, in mathematics and computer science, is a method of
defining functions in which the function being defined is applied
within its own definition.

Further down the page, it tells us:

Functional recursion - A function may be partly defined in terms of
itself. A familiar example is the Fibonacci number sequence: F(n) =
F(n − 1) + F(n − 2). For such a definition to be useful, it must lead
to values which are non-recursively defined, in this case F(0) = 0 and
F(1) = 1.


Now, the way I see it, const() is a function. It's a function which
takes a type as its input, and returns a type as its output. According
accu-functional.pdf, const() is defined by four rules (numbered 0 to
3). Rule 1 says:

Rule 1: If T.field has type U, then const(T).field has type const(U)

That, to me, looks like a classic example of a recursive definition.



> I'd think you'd find
> you're saying exactly the same thing.  Transitivity is recursive in nature.

Are you sure about that? In what way is "less than" recursive? "Less
than" is certainly transitive, by definition (if (a < b), and (b < c),
then it must be true that (a < c)). However, you'd be hard pressed to
claim that "less-than" was "recursive". It's not defined in terms of
itself.

If I recall correctly, (a < b) is defined to be true if and only if
there exists a positive number c such that a + c = b. That is a surely
a non-recursive definition? The transitivity of "less than" is merely
an emergent property, a /consequence/ of that definition. No recursion
involved.