| |
 |
|
|
Science Forum Index » Logic Forum » recursive/inductive definitions?
Page 1 of 2 Goto page 1, 2 Next
|
| Author |
Message |
| mx |
 Posted: Tue Jan 06, 2004 1:28 pm |
|
|
|
Guest
|
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?
thank you |
|
|
| Back to top |
|
| Daryl McCullough |
| Posted: Tue Jan 06, 2004 1:39 pm |
|
|
|
Guest
|
mx says...
Quote: 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?
thank you
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction.
--
Daryl McCullough
Ithaca, NY |
|
|
| Back to top |
|
| Daryl McCullough |
| Posted: Tue Jan 06, 2004 1:39 pm |
|
|
|
Guest
|
mx says...
Quote: 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?
thank you
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction.
--
Daryl McCullough
Ithaca, NY |
|
|
| Back to top |
|
| Aatu Koskensilta |
| Posted: Tue Jan 06, 2004 4:11 pm |
|
|
|
Guest
|
Daryl McCullough wrote:
Quote: mx says...
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?
thank you
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction.
"Inductive definition" is pretty common, although in the contexts I'm
familiar with "recursive definition" is used more often. There's even a
theory of inductive definitions.
--
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus |
|
|
| Back to top |
|
| Aatu Koskensilta |
| Posted: Tue Jan 06, 2004 4:11 pm |
|
|
|
Guest
|
Daryl McCullough wrote:
Quote: mx says...
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?
thank you
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction.
"Inductive definition" is pretty common, although in the contexts I'm
familiar with "recursive definition" is used more often. There's even a
theory of inductive definitions.
--
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus |
|
|
| Back to top |
|
| mx |
| Posted: Tue Jan 06, 2004 11:49 pm |
|
|
|
Guest
|
hey all,
just to make the discussion more focused:
Kleene in his "introduction to metamathematics" (available from Dover)
has a small portion (paragraph 52) called "inductive and recursive
definitions". he makes a distinction, but i don't really follow his
explanation.
thank you
maxim
daryl@atc-nycorp.com (Daryl McCullough) wrote in message news:<btevcv02aus@drn.newsguy.com>...
Quote: mx says...
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?
thank you
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction. |
|
|
| Back to top |
|
| namducnguyen |
| Posted: Wed Jan 07, 2004 1:56 am |
|
|
|
Guest
|
Daryl McCullough wrote:
Quote: mx says...
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?
thank you
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction.
I'd agree - that's what we generally hear. But I'd also think there is a
subtle difference
between "inductive definition" and "recursive definition", in general.
In formal systems,
there is such a thing called "generalized inductive definition", which
models after
the "inductive definition" of theorems, viz-a-viz "rules of inference"
of a formal system F:
<quote>
i) the axioms of F are theorems of F;
ii) if all of the hypotheses of a rule of F are theorems of F, then the
conclusion of the rule is a theorem of F.
</quote>
[Joseph R. Shoenfield, "Mathematical Logic" - 1.2 Formal Systems]
Imho, the adjective "inductive" comes from the fact that the conclusion
of hypotheses are "induced"
via rules of inference. [The adjective "recursive" doesn't seem to share
this "root".]
"A generalized inductive definition of a collection C of objects
consists of a set of laws, each of which
says that, under suitable hypotheses, an object x is in C. Some of the
hypotheses may say that certain
objects (related to x in a certain way) are in C." ........"Then in
order to prove every object in C has
property P, it suffices to prove that the objects having property P
satisfy the laws of the definition.
Such a proof is called a *proof by induction* on objects in C." [Shoenfield]
I actually don't know much about recursive functions, but my guess is
that in general, if recursion
connotes a degree of self-reference, a recursive definition would still
be based on inductive
definition, and ot the other way around. [Both the inductive definition
of theorems and the generalized
inductive definition does not mention anything about. self-reference at
all].
Just my 2 cent opinion of the subject.
---Nam
Quote:
--
Daryl McCullough
Ithaca, NY
|
|
|
| Back to top |
|
| Mitch Harris |
| Posted: Wed Jan 07, 2004 4:04 am |
|
|
|
Guest
|
mx wrote:
Quote: daryl@atc-nycorp.com (Daryl McCullough) wrote in message news:<btevcv02aus@drn.newsguy.com>...
mx says...
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?
The way I have heard the two terms used, "recursive" applies to
definitions, while "inductive" applies to proofs. So
you define a function using recursion, and then you prove facts
about that function using induction.
just to make the discussion more focused:
Kleene in his "introduction to metamathematics" (available from Dover)
has a small portion (paragraph 52) called "inductive and recursive
definitions". he makes a distinction, but i don't really follow his
explanation.
Reading the same, it seems that he uses "inductive definition" for
definitions of both predicates (provable things that one will attempt to
prove) and functions (things one might want to compute). But then he
uses "recursive definition" only (as far as I could see) to talk about
definitions of functions. So there is some fluidity as to usage as to a
modifier of "definition"
As to why we have two terms for what is essentially the -same- notion,
the terms "induction" and "recursion" come from totally different
intentions (as Daryl pointed out), proof and computation. The lexical
confusion comes from the slow realization that they refer to the same
idea.
Mitch Harris |
|
|
| Back to top |
|
| David C. Ullrich |
| Posted: Wed Jan 07, 2004 6:41 am |
|
|
|
Guest
|
On 6 Jan 2004 10:28:24 -0800, mx@is23dt.com (mx) wrote:
Quote: 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_.
************************
David C. Ullrich |
|
|
| Back to top |
|
| H. Enderton |
| Posted: Wed Jan 07, 2004 2:34 pm |
|
|
|
Guest
|
mx <mx@is23dt.com> wrote:
Quote: what is the difference between recursive and inductive definitions?
Usage of the phrases "recursive definition" and "inductive
definition" vary from one person to the next. But *one*
usage is illustrated by the following:
The exponential function f(n) = 2^n can be recursively defined
by the two equations f(0) = 1 and f(n+1) = 2f(n).
The set of propositional formulas can be inductively defined
by the three conditions:
-propositional letters are formulas
-if phi and psi are formulas, then so are ~phi, phi & psi, phi v psi.
-nothing else is a formula; the set of formulas is the smallest set
that contains the propositional letters and is closed under the
connectives.
--Herb Enderton |
|
|
| Back to top |
|
| Torkel Franzen |
| Posted: Thu Jan 08, 2004 4:05 am |
|
|
|
Guest
|
David C. Ullrich <ullrich@math.okstate.edu> wrote in message news:<3ornvv4jo9rje433p04mkbvotrbh075cnl@4ax.com>...
Quote: 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_.
There are, however, somewhat systematic differences in usage. For example,
the theory of inductive definitions is not called the theory of recursive
definitions. My impression is that recursive definitions are most often
spoken of when an explicit well-founded relation is involved. All inductive
definitions can be cast in the form of recursion on a well-founded relation,
but there is usually no reason to do so. Consider for example the inductive
definition of "hereditarily countable set":
The empty set is hereditarily countable.
If A is countable and every member of A is hereditarily countable,
A is hereditarily countable.
(The "extremal clause" is left implicit.) This inductive definition goes
with a corresponding principle of induction for proving statements of
the form "for every hereditarily countable A, F(A)". |
|
|
| Back to top |
|
| Mitch Harris |
| Posted: Thu Jan 08, 2004 4:27 am |
|
|
|
Guest
|
Torkel Franzen wrote:
Quote: David C. Ullrich <ullrich@math.okstate.edu> wrote:
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_.
There are, however, somewhat systematic differences in usage. For example,
the theory of inductive definitions is not called the theory of recursive
definitions. My impression is that recursive definitions are most often
spoken of when an explicit well-founded relation is involved.
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. So, for example,
the defintion of the Collatz function would be more likely called
recursive rather than inductive.
Quote: All inductive
definitions can be cast in the form of recursion on a well-founded relation,
but there is usually no reason to do so. Consider for example the inductive
definition of "hereditarily countable set":
The empty set is hereditarily countable.
If A is countable and every member of A is hereditarily countable,
A is hereditarily countable.
(The "extremal clause" is left implicit.) This inductive definition goes
with a corresponding principle of induction for proving statements of
the form "for every hereditarily countable A, F(A)".
where "hereditary" is practically a synonym for inductive!!
Mitch Harris |
|
|
| Back to top |
|
| mx |
| Posted: Thu Jan 08, 2004 10:03 am |
|
|
|
Guest
|
hi again,
i doubt if surveying people's linguistic intuitions is at all useful
in math. even if majority of native speakers don't distinguish them,
they might still be wrong.
for the benefit of the community i post the answer i've just got from
the other source prof. Melvin Fitting :
"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."
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: Thu Jan 08, 2004 10:10 am |
|
|
|
Guest
|
Mitch Harris <harrisq@tcs.inf.tu-dresden.de> wrote in message news:<btj7qv$7tcpu$1@uni-berlin.de>...
Quote: 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? Definitions of e.g.
primitive recursive functions are not usually called "inductive", so
I don't know what you have in mind by saying that "definitions that
involve well-foundedness" are called inductive.
Quote: where "hereditary" is practically a synonym for inductive!!
No it isn't. |
|
|
| Back to top |
|
| Mitch Harris |
| Posted: Thu Jan 08, 2004 3:59 pm |
|
|
|
Guest
|
mx <mx@is23dt.com> wrote:
Quote:
i doubt if surveying people's linguistic intuitions is at all useful
in math. even if majority of native speakers don't distinguish them,
they might still be wrong.
Yes, I agree, such a survey can have the feel of an opinion poll. But I
think the original poster was specifically talking about usage. Though the
words are not the same as the concepts they represent (in math or
anything), discussing the nuances of usage can help both native and
nonnative speakers with precision (especially when the usage has
connotations contrary or orthogonal to the concept).
Mitch Harris |
|
|
| Back to top |
|
| |
Page 1 of 2 Goto page 1, 2 Next
All times are GMT - 5 Hours
The time now is Fri Oct 10, 2008 11:28 pm
|
|