On Sep 20, 2010, at 5:29 AM, Alex Shkotin wrote:
In FOL to get definition (for R_ in my case) we need additional clause, just as Doug has written.
And putting all that clauses together we do get recursive definition for R_
(as it is written by Prof. Swartz at http://www.sfu.ca/philosophy/swartz/definitions.htm#part5.6):
R_(x,y) =df (R(x,y) or there_exists z such_that R_(x,z) and R(z,y))
Actually, recursive definitions are not proper definitions in FOL, so the "=df" is in fact misplaced here (Prof Swartz's use of the notation notwithstanding). In a genuine definition, the defined term is in a certain (rigorous) sense dispensable; it is a convenience that one could, in principle, do without. Unlike a recursive definition, then, in a genuine definition, the defined _expression_ cannot occur in the definiens.
A recursive definition, by contrast, asserts that a certain unique function or relation (i.e., in set theoretic terms, a certain set of ordered n-tuples) satisfying the definition exists. As the paradoxes of set theory taught us, one cannot simply go about asserting the existence of sets, functions, and relations willy-nilly. Hence, recursive definitions in general must be justified by a theorem to the effect that the functions or relations asserted to exist by such definitions do exist. (This is, unsurprisingly, called the "definition by recursion" theorem, which was first proved by von Neumann (who also first recognized the need for such a proof) in the 1920s and generalized by Tarski in the 1950s).
From a formal perspective, then, both ordinary definitions and recursive definitions in general are best thought of as axioms that one adds to an existing theory that introduce one's new function/relation symbols. In the case of ordinary definitions, that such axioms are "safe" is demonstrated by showing that anything that can be proved using the defined expressions could be proved by replacing the defined expressions with their definitions.* In the case of recursive definitions, such axioms are guaranteed to be "safe" by the definition by recursion theorem, which, once again, shows that the functions/relations that the axioms explicitly name and characterize do, in fact, exist.
to say frankly I still doubt - may be we need to keep in mind something like "smallest transitive relation" like in "In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R."
Good example. That there exists a unique, smallest such set for every binary relation is a nontrivial theorem of set theory.
*To count as genuine definitions, one also has to prove that the new axioms are "conservative", i.e., that they don't permit one to prove theorems not involving the new symbols that one couldn't prove before.