Main Page | Report this Page
 
Loading..
   
Science Forum Index  »  Logic Forum  »  recursive/inductive definitions?
Page 2 of 2    Goto page Previous  1, 2
Author Message
Mitch Harris
Posted: Thu Jan 08, 2004 4:16 pm
Guest
Torkel Franzen <torkel@sm.luth.se> wrote:
Quote:
Mitch Harris <harrisq@tcs.inf.tu-dresden.de> wrote in message

As to usage, I was about to say the opposite, that definitions are
called inductive when they (explicitly or not) involve well-foundedness,
and a definition that is (merely) recursive has no such presumption, the
usage of "recursive", by association with recursive functions, applying
in the not necessarily total (terminating) instance.

You're thinking of definitions of functions?

Yes.

Quote:
Definitions of e.g.
primitive recursive functions are not usually called "inductive",

I agree.

Quote:
so
I don't know what you have in mind by saying that "definitions that
involve well-foundedness" are called inductive.

I'm not sure I follow you either. All I am saying is that, very
intuitively as a justification for usage, whether the large part of people
do it or not

Quote:
where "hereditary" is practically a synonym for inductive!!

No it isn't.

In my usage, which may well be very contrary to yours, they share quite a
lot.

hereditary family - a set of sets F such that every subset of a set in F
is also a member of F

induction - A predicate is true of an object x if it is true for all
objects y where y < x (for some well-founded order "<")

hmmm.. so maybe you object to my characterization because hereditary does
not involve a well-founded order? I suppose when I think of hereditary, it
is usualy with respect to sets of finite structures and so I am usually
thinking of something with a well-founded order. Is that the problem with
my statement?

Mitch Harris
Back to top
mx
Posted: Thu Jan 08, 2004 8:59 pm
Guest
hi,
i've gotten a reply from Prof. Melvin Fitting concerning the
recursive/inductive distinction. here it is:
"I'm not sure, since this usage is not entirely standard, but I think
what he means is this. An inductive definition of a predicate is one
that makes use of itself in the 'recursion' clause. But not everything
that is inductively definable is recursive, which is a technical term.
A recursively defined predicate is given by an inductive definition,
and is effective in that, for each instance we know whether or not the
predicate applies. Near the end of paragraph 53 Kleene uses the
example of 'provable formula'. The definition is inductive: axioms are
provable; applying rules of inference to provable formulas yields
provable formulas. There is a ground case (axioms) and an inductive or
recursive case (rules of inference). But the set of provable formulas
of first-order logic is not recursive since there is no decision
procedure for it. (It is recursively enumerable, though.) Inductive
definitions turn up all over mathematics, without decision procedures
always being available. For instance, the definition of addition for
ordinal numbers is usually given inductively, but ordinals do not even
constitute a set in the technical sense.

Hope this helps."


maxim

ps i accidentally posted essentially the same message outside of the
thread. please disregard it.














David C. Ullrich <ullrich@math.okstate.edu> wrote in message news:<3ornvv4jo9rje433p04mkbvotrbh075cnl@4ax.com>...
Quote:
On 6 Jan 2004 10:28:24 -0800, mx@is23dt.com (mx) wrote:

what is the difference between recursive and inductive definitions? if
there is none (as i was told by my professor) , why do we have to
notions?

Evidently, from reading some of the other replies, there _is_ a
distinction in some areas. But that's a very specialized
usage - in the rest of this post I'm going to ignore that and
talk about the way it seems to me most people use the words:

In the way most people use the terminology there is no difference
at all - your professor's claim seems to me to be precisely
consistent with how most people use the words. On the other
hand, a lot of people would talk about recursive _definitions_
and inductive _proofs_ (which seems "right" to me), but a lot
of people talk about inductive definitions as well.

Then why are there two notions? There are not two notions;
the people who talk about inductive definitions are referring
to exactly the same notion as the people who talk about
recursive definitions. There are two different _words_.

thank you


************************

David C. Ullrich
Back to top
Torkel Franzen
Posted: Fri Jan 09, 2004 4:24 am
Guest
harrisqqq@tcs.inf.tu-dresden.de (Mitch Harris) wrote in message news:<btkhai$80mit$1@uni-berlin.de>...

Quote:
induction - A predicate is true of an object x if it is true for all
objects y where y < x (for some well-founded order "<")

Such a well-founded < can always be defined, but when we use inductive
definitions in the form of base clause+inductive clause+(usually implicit)
extremal clause, no such < is explicitly introduced, and nothing is gained
by doing so. Instead we just get an induction principle corresponding to
the inductive definition. Thus in the case of the hereditarily countable
sets, we get the principle "If the empty set has property P, and A
has property P whenever A is countable and every member of A has property P,
then all hereditarily countable sets have property P."

Quote:
I suppose when I think of hereditary, it
is usualy with respect to sets of finite structures and so I am usually
thinking of something with a well-founded order.

Finite inductive definitions are the most common case, but even when the
definition is not finite, as in the case of the hereditarily countable sets,
a well-founded order can always be defined when we justify such definitions
in set-theoretical terms. But of course we can also take them as primitive.
Back to top
 
Page 2 of 2    Goto page Previous  1, 2   All times are GMT - 5 Hours
The time now is Sat Aug 30, 2008 2:06 am
Science Forum Index

Powered by phpBB & ML | Disclaimer



Contact Us