Talk:Recursive definition

merge

Isn't this subject already covered by Recursion, though? -- Antaeus Feldspar 18:41, 7 Oct 2004 (UTC)

I wondered that, too, but then I read the recursion article. My article can stand alone, although I wouldn't mind if someone merged the two together. --Uncle Ed 19:08, 7 Oct 2004 (UTC)

These seems to be recursive definitions not recursive functions. Is that a distinction? RJFJR (talk) 16:52, 14 July 2009 (UTC)

Yes, so I oppose the merge. These are distinct notions. An important application in type theory (and thus type systems) is the recursive data type. Pcap ping 07:56, 18 August 2009 (UTC)

Oppose the merge. This article stands by itself; it has multiple uses, one of which is as a sub-page of definition. --Ancheta Wis (talk) 12:16, 19 August 2009 (UTC)

Recursive definitions in hacker culture

removed because as far as I can tell these are circular rather than recursive definitions, since they lack a base case. RJFJR (talk) 16:52, 14 July 2009 (UTC)

The computer language LISP has a similar definition, and some fans of LISP have playfully constructed acronyms which are recursive but with an infinite regress. Hackers seem to find this a source of immense amusement. For example,

• GNU means "GNU's Not Unix".
• WINE means "WINE Is Not an Emulator"

WFFs

Shouldn't the letters be replaced by the actual logic symbols? Dude1818 (talk) 00:11, 21 December 2009 (UTC)

Problems in the proof of the definition by recursion theorem

The proof that recursive definitions are legit needs an overhaul. Right off the bat, the initial supposition that one has both the functions f and g begs the whole question. The function f is the very one whose existence is supposed to be justified by the theorem. What you want to prove (in the simplest case) is that, given ONLY a function g and an object b, there exists a function f on ℕ satisfying f(0) = b and f(n+1) = g(f(n)), for all n∈ℕ. The proof proceeds in two parts. First, by induction (or, equivalently, the least number principle), one shows that, for every n∈ℕ, there is a (finite) function F_n on {0,...,n} such that F_n(0) = b and, for m<n, F_n(m+1)=g(F_n(m)). (The current proof gestures in this direction but the effort is vitiated by the references to the function f whose existence is to be proved.)

In the second part of the proof, one defines the desired function f (now called "F" in the proof) to be "the set theoretic union of all the F_n". However, you can't just take the union of "all" of a bunch of things, as the current proof would have it. You first have to prove that they exist together as the members of a set. That is proved in this case as follows: Every F_n is a subset of ℕxℕ and hence is a member of the powerset ℘(ℕxℕ) of ℕxℕ. Hence, the set M of all of the F_n exists by the axiom of Separation: M = {h ∈ ℘(ℕxℕ) : h is F_n, for some n}. The desired function f given by the recursion can now be proved to exist by the Union axiom: f = ∪M.

I don't have time to gussy this up for the entry at the moment, but it needs to be done. I'll do it eventually if no one else does. TXlogic (talk) 14:40, 24 November 2013 (UTC)

(Aczel 1978:740ff)

What is it? Was here Fractaler (talk • contribs) 08:52, 10 November 2017 (UTC)

Indeed, the inline citation has been added in Special:Diff/310702907. In the same edit a citation '(Aczel 1978:740)' was added, which seems to make more sense as a normal page number. However, a reference added does not agree with both citations, as it gives 1977 as a year of publication instead of 1978.

Anybody willing to clarify the discrepancies? I'm afraid there's no hope the author (CBM) will fix them, as he or she seems inactive for over a year... --CiaPan (talk) 16:36, 4 August 2019 (UTC)

It looks like the year should be 1977 instead of 1978. In that reference, the first page is a table of contents and the material itself starts at page 740, so "740 and the following" really just refers to Aczel's introduction and however much the reader wants to keep going through. XOR'easter (talk) 18:10, 4 August 2019 (UTC)

Error

"Note that this definition assumes that N is contained in a larger set (such as the set of real numbers) — in which the operation + is defined." is not correct. 31.49.9.229 (talk) 22:19, 29 December 2019 (UTC)