Re: Rigorous proof of natural numbers' properties (by Edmund Landau).

From: Leonard Blackburn (blackbur_at_math.umn.edu)
Date: 07/01/04 

Date: 1 Jul 2004 09:28:35 -0700

David C. Ullrich <ullrich@math.okstate.edu> wrote in message news:<r896e0lh340oajqcb6sf9gphckthkprrfo@4ax.com>...

>
> I don't see your point when you say "We cannot define the set
> p_s(n) in terms of a set p_n which we do not know exists
> in the first place. I know that some readers would object to
> this by saying that we are, in the course of our proof by
> induction, _assuming_ that the set p_n exists. But this is
> just an attempt to cleverly disguise a definition by
> induction"

I must correct myself: My criticism was of Professor Jodeit's rewriting
of Landau's theorem and proof. If one insists that addition be a
_function_ then Landau's proof would not be correct. My point is that
if one regards a "sequence" as a function with domain the natural numbers,
then the argument given does not define a sequence, (p_n). If you want
to define a sequence of such sets (which you will want to do if you want
to define an addition _function_), then you will need something like a
recursion theorem.

For example, suppose you want to prove that there exists a function
f with domain the natural numbers such that f(0) = 0 and f(n+1) =
sqrt[2 + f(n)]. Then a correct proof would not be to say: Define
f(0) = 0. Suppose f(n) is defined. Define f(n+1) = sqrt[2 + f(n)]. Then,
by induction, f(n) is defined for all natural numbers n and the above
equations hold.

-Leonard

> [I wish people would talk about definitions
> by "recursion" instead of by "induction", to keep the
> two separate, by the way.]

I agree with you there. I now use "definition by recursion."

Relevant Pages

  • Re: The Demise of Computationalism?
    ... Applying the definition to a reasoning system, ... This reminds me of Marcus Hutter and Solomonoff Induction ... universal induction formally solves the problem of sequence ... situations where no prior information about the system under ...
    (comp.ai.philosophy)
  • Re: Cantor Confusion
    ... the notion of a sequence derives really from an inductive definition ... Since ZFC has no trouble modeling the natural ... But ZFC does have considerable difficulty dealing with infinite ... proof by induction that these "infinite quantities" were also simply ...
    (sci.math)
  • Re: Current wisdom on TOX
    ... share it hear to show how much the 'standard' might be considered to be ... The experts and readers were given 4 possible answers to each ... about an Ace and queen more than minimum ... After each sequence below the first number represents the experts that ...
    (rec.games.bridge)
  • Re: [Discrete Math] Divisibility within subsequences of the Fibonacci Sequence
    ... denotes the kth Fibonacci Number, ... Also, again from prior posts, the topic is "induction", and the goal, ... sequence, but rather, to provide an exercise for the student to apply ... The first result solves most first level problems ...
    (sci.math)
  • Re: approaching a proof
    ... Mitch Harris wrote: ... >> sequence of 'proofs' in that system that APPROACH a proof of the ... > induction (i.e. choose your system to be arithmetic without ... What axioms and rules are you assuming? ...
    (sci.logic)