Results 1 to 9 of 9
Like Tree4Thanks
  • 2 Post By HallsofIvy
  • 2 Post By Deveno

Math Help - Question about successor functions.

  1. #1
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Question about successor functions.

    I am not sure where these questions belongs, beginning or advanced algebra … with regard to Peano’s axioms:

    1) Must a successor function be written in a “recursive” format?

    2) A successor function is certainly a one-to-one function but is that sufficient and if not is there another property that a successor function must possess?

    3) Given

    “a” is a real number,

    “n” is a natural number and the recursive definition:

    a1 = a, and an+1 = an a, it can be proved that this recursive definition is true for all n.

    Does that mean that the here stated recursive definition is itself proved to be a “successor function”? If yes, does this mean all recursive functions proved true for all “n” are successor functions?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,707
    Thanks
    1470

    Re: Question about successor functions.

    Quote Originally Posted by Ray1234 View Post
    I am not sure where these questions belongs, beginning or advanced algebra … with regard to Peano’s axioms:

    1) Must a successor function be written in a “recursive” format?

    A "successor function" could also be written as s(x)= x+ 1 but since, in Peano's axioms, addition is defined in terms of the "successor fuction" this would be "circular". (For any x, x+ 1 is defined as s(x). If b is not 1, then there exist c such that s(c)= b. In that case a+ b is defined as s(a+ c).)

    2) A successor function is certainly a one-to-one function but is that sufficient and if not is there another property that a successor function must possess?
    It must also have the property that there exist a unique member of N (typically called "1") such that the successor function is "onto" N-{1}.

    3) Given

    “a” is a real number,

    “n” is a natural number and the recursive definition:

    a1 = a, and an+1 = an a, it can be proved that this recursive definition is true for all n.

    Does that mean that the here stated recursive definition is itself proved to be a “successor function”? If yes, does this mean all recursive functions proved true for all “n” are successor functions?
    I don't know what "true" means in regard to a definition. You can determine whether or not is "well defined"- that is, whether it defines a unique object, a^n for every real number a and every positive integer, n. You seem to have a very vague idea of what a "successor function" is. No, it does not mean that any recursive function is a successor function- a successor function is exactly what I said and what was probably given in your text: It is a one-to-one function from N onto N-{1}.

    To prove that the given definition is "well defined" you must show that you can apply it to any positive integer n. (a is a real number and we are only concerned with integers here so we accept it.) As usual with the natural numbers, which are, with Peano's axioms, defined "inductively", we use "proof by induction". Let "S" be the set of all natural numbers such that a^n is defined.
    (i) a^1 is defined to be 1 so 1 is in S.

    (ii) Suppose n is in S. Then a^{n+1}= (a^n)(a). Since n is in S, a^n is defined and multiplication of two members of N is defined so (a^n)(a) is defined. That is, a^{n+1} is defined so a is in S.

    By induction then, S= N so a^n is defined for all N.


    Thanks.
    Thanks from topsquark and Ray1234
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Question about successor functions.

    The logic trap here is this:

    The successor function is recursively defined, and the successor function is used to define recursive functions. This is my preferred way "out of this trap":

    We start with an infinite set N (Can we do this? Do we know for certain anything infinite even exists? Gee, I don't know, but since the arithmetic system we'd LIKE to make is going to turn out to be infinite, we're going to have to assume we CAN do this).

    We pick a "special member" of this set, I will call it $u$ (for "unit"). So we want a bijection:

    $s: N \to N - \{u\}$ (this is why we need an infinite set, such a bijection isn't possible on a finite set, because the "target" set has one less element).

    What other properties do we want $s$ to have? Well, just one, but it's a doozy. Here it is:

    If $f:X \to X$ is any function (ANY function? yes, any function) from a set $X$ to itself, and $a \in X$, we want there to be a UNIQUE function (uniqueness is important, here) $g:N \to X$, with:

    $g(u) = a$
    $g(s(u)) = f(g(u))$.

    Now, this might seem like gobblty-gook, so let's look at an example:

    Suppose $X = \Bbb R$, the real numbers, and $f:\Bbb R \to \Bbb R$ is the function defined by $f(x) = 2x$.

    The function $g$ we are trying to define here is $g(n) = 2^n$, and the above says there is NO OTHER FUNCTION $N \to \Bbb R$ such that:

    $g(u) = 2$ (2 is a real number, no problem, there, what we are thinking here is $g(1) = 2$).
    $g(s(n)) = 2\cdot g(n)$ <---in other words: $2^{n+1} = 2\cdot 2^n$.

    So, for example, to calculate $g(5)$, we do this:

    $g(5) = 2\cdot g(4) = 2\cdot(2 \cdot g(3)) = 2\cdot(2\cdot(2\cdot g(2))) = 2\cdot(2\cdot(2\cdot(2\cdot g(1)))) = 2\cdot(2\cdot(2\cdot(2 \cdot 2)))$

    $= 2\cdot(2\cdot(2\cdot 4)) = 2\cdot(2\cdot 8) = 2\cdot 16 = 32$

    In other words, powers of 2 are recursively defined by multiplying by 2 recursively. If you think about it, this is just what you were taught to do in your early years in school.
    Thanks from topsquark and Ray1234
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Re: Question about successor functions.

    Thank you HallsofIvy, sir, your response helped. I had responded earlier in more detail but I must not have pressed the submit button (?)!

    Deveno, sir, thank you ... processing, hope I am not stuck in a recursive loop. Must let this cook a couple of days.
    Last edited by Ray1234; July 8th 2014 at 03:43 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Cooked.

    In reading this post now, a couple of weeks later (always instructive), I can appreciate the difficulty that an experienced mathematician has in responding to questions in this forum. In this instance for example, I was using incorrect nomenclature.

    In reading a pdf on ZFC I seemed to understand that the set of Natural numbers and its properties were generalized to the concept of an “Inductive set”, which is any set which can be defined in terms of Peano’s axioms (I was thinking).

    In my mind this was equating an inductive set with a recursive function defined over N so that the characteristic function of a recursion would then be a “successor function” for that recursion. In other words I thought that generalizing the Natural numbers to the concept of an inductive set also generalized “successor function” to the concept of a “recurssor function” (is there even such a word), i.e the characteristic function of a recursive algorithm.

    This was all wrong, the “Inductive set” (as defined by ZFC) is just another name for a Peano’s axioms and adds no generalization.

    Apologizes, for what turned out to be a knuckle ball.

    BUT … even so answers were supplied:

    HallsofIvy:

    “No, it does not mean that any recursive function is a successor function- a successor function is exactly … a one-to-one function from N onto N-{1}”.

    Underlining mine.

    It was also helpful to have a meaning attached to “well defined” which consequently sent me to Wolfram for the full definition.

    Finally, the succinct use of induction to prove an as being ‘well defined’ serves well as a micro case for appreciating what it means to use induction as a means of definition. (I am looking at the different ways induction can be used, establishing a definition vs proving a proposition for example but haven’t gotten there yet.)

    Deveno.

    Now, finally getting back to Deveno’s post disentangling the definition of a successor function from that of recursive function.

    ----
    The logic trap here is this:

    The successor function is recursively defined, and the successor function is used to define recursive functions. This is my preferred way "out of this trap":

    We start with an infinite set N (Can we do this? Do we know for certain anything infinite even exists? Gee, I don't know, but since the arithmetic system we'd LIKE to make is going to turn out to be infinite, we're going to have to assume we CAN do this).

    I can so assume.

    We pick a "special member" of this set, I will call it u (for "unit").

    OK

    So we want a bijection:

    s:N→N−{u} (this is why we need an infinite set, such a bijection isn't possible on a finite set, because the "target" set has one less element).

    I can see that … “Hilberts Hotel”.

    What other properties do we want s to have? Well, just one, but it's a doozy. Here it is:

    If f:X→X is any function (ANY function? yes, any function) from a set X to itself, and a∈X, we want there to be a UNIQUE function (uniqueness is important, here) g:N→X, with:

    g(u)=a
    g(s(u))=f(g(u)).

    Now, this might seem like gobblty-gook ...

    At this point I will try to “read” the gobblty-gook, something I could not even attempt two weeks ago.

    After much, much, much consideration the heart of matter now appears simple.

    Given f, there is only one g such that when the image of that g, g(u), is applied to f as the domain set of the composition (f o g), the returned image set, f(g(u)) is identical to the domain set, g(u), except offset by one count.

    For example if f(n) = 2n and g(n) = 2n,

    the first four image elements of g are: 2, 4, 8, 16, 32, …

    Applying those element to (f o g) yields: 4, 8, 16, 32, 64, … ,

    the same sequence except offset by one count. If g was any other function for the given f, this could not happen.

    Looking at the situation from a different point view:

    If not given f but given,

    g:N-->N, g(n) = ANY characteristic function

    then there exists a unique f such that g can be defined recursively. That is to say, given g as defined above and g defined recursively as:

    g:N-->N, where g(u) = a, g(s(u)) = f(g(u))

    then both definitions of g will produce the same set of output pairs (u, g(u)).

    For example let

    g:N-->N , g(n) = 2n

    the first four pairs defined by g (the non-recursive definition) are: (1,2),(2,4),(3,8),(4,16), …

    Now, if one knows that f(n) = 2n is the correct f to use, then g can be defined recursively as:

    g:N-->N, g(1) = 2, g(n+1) = f(g(n)) = 2(g(n)) = 2(2n) = 2n+1

    whose definition, now defined recursively, again returns: (1,2),(2,4),(3,8),(4,16), …

    Wow! I am quite happy with this understanding of recursion, and the elements needed to create one … others might shrug … like … obvious (me too, NOW), but still … REVELATION!!!.

    Returning to the whole point of this exercise, understanding the relationship of Peano’s recursive function “s” to every other recursive function.

    The above explanation already connects the given f to a unique g(u) that is the characteristic function of a recursively defined g.

    The last point is to define u in terms of s and then take stock.

    Let’s say there exists the set N of natural numbers. I picture them displayed on a number line at unit intervals.

    Let’s also say that g is defined over the domain set N-{u} and whose image is a subset of N:

    g:N-{u}-->N, that is, each point on the N number line, excluding elements to the left of “u”, has a unique correspondence in the codomain N.

    By Peano’s axioms each element of N-{u} can be replaced by {u} or some nested successor of {u}.

    For example if u = 4 then

    4 = {4}
    5 = {s(4)}
    6 = {s(5)} = {s(s(4))}
    7 = {s(6)} = {s(s(s(4)))}
    8 = {s(7)} = {s(s(s(s(4))))} …

    or, generally,

    s:N-->N-{u}, n = u, s(n) = the next mark on the natural number line or the number symbol following u.

    This then is a recursive definition defining each element of g’s domain set in terms of u or s(u) thus allowing one to write:

    g(u)=a
    g(s(u))=f(g(u)) the precursor of

    g(u)=a
    g(u+1)=f(g(u)), which will be used once addition is defined.

    In toto then, I see that the successor function "s" establishes the ability to define and essentially “drive” every other recursive function, and that s is the only recursive function that delivers N as its image set.

    I think that what I have written is overall correct although my attempts to use mathematical language might be flawed, particularly in distinguishing “u” as the specified first element of U and its use as the “variable” u … but, you know, I might be terribly wrong.

    ------

    Finally I attach a story that I wrote as a means of coming to the understanding I now have. It was the only way to stay focused and follow my path of reasoning. I add it for any necessary correction on one hand or as a possible seed of thought for others dealing with the same issues as I am.

    The story of Matt

    One evening Matt the budding mathematician is playing with a function f:N-->N defined by f(n) = 2n.
    Doing the usual high school thing he pumps the first four natural numbers through f(n) to get:

    F ={(1,2), (2, 4), (3,6), (4,8) …}

    but then gets bored and thinks “What if I take f and pump it’s output back to its input … doing so

    F={(1,2), (2, 4), (3,6), (4,8) …} becomes:

    G={(1,2), (2,4), (4,8), (8,16) …} where the image of each preceding pair becomes the domain element of the next pair.”

    “Wow!” he exclaims, “A new funky function is born!” … funky because its domain seems to be missing a lot of elements, like 3, 5, 6, 7 …

    In a moment of minor inspiration Matt decided to take the image sequence of G, … 2,4,8,16 … and pair it’s elements with the number of “pumps” it took to pump each element of the sequence through f, i.e., one pump produced 2, the second pump produced 4, the 3rd 8, etc. so,

    G={(1,2), (2,4), (4,8), (8,16) …} becomes:

    H={(1,2), (2,4), (3,8), (4,16) …}

    Serendipitously Matt recognizes that this sequence of pairs is the same sequence as produced by the expression 2n over N.

    so that,

    h:N-->N, h(n)= {(1,2), (2,4), (3,8), (4,16) …} becomes

    h:N-->N, h(n)= 2n

    But hold the phone! (Matt's adrenalin and endorphin levels rise exponentially.)

    This means that there are two different functions, i.e. f(n) = 2n and h(n) = 2n that can generate the same set of pairs! ...... This means that f and h are identities of one another albeit each function must be evaluated using a different algorithm! Calming down, Matt decides it might be more accurate to say that f(n) and h(n) uniquely define one another by the common property of producing the same set of pairs although by different procedures ... maybe.

    Upon reflection Matt decides that the key points to remember are (1) that the recursive algorithm generates two sequences, the output sequence and the feedback sequence and that they are identical except the output sequence is delayed by one pump. (2) The output sequence is the input sequence fed through the pumping function f(n).

    Mat realizes that his ideas are not mathematically formulated but feels that his understanding of recursion is greatly enhanced and goes to sleep feeling that tomorrow he will be able to better interpret the gobblty-gook of formal definitions. He crosses his fingers and conks out.

    End of story.
    Last edited by Ray1234; August 6th 2014 at 09:06 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jul 2014
    From
    Ca, USA
    Posts
    47
    Thanks
    4

    Re: Cooked.

    Nuts, too late to edit the above post, h(n) = 2n, not h(n) = 2n. And how many times did I review what I had written ... sheeesh!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Question about successor functions.

    That's about the size of it: the successor function allows recursive definition. That's what the "gobblety-gook" means.

    So if you have an infinite set, with an injective (and surjective onto all but one element, the "root" of the set) function, and you can leverage this function into defining functions on all of your set, we may as well call it "THE" successor function.

    For example we could think of X as the set: {true,false} and g(k) as the function "evaluate the statement P applied to k", and f:X → X as the identity function, with a = true.

    Then our two rules say:

    P(u) is true.

    P(s(k)) is true, when P(k) is true.

    This, of course, is just a re-statement of the principle of mathematical induction.

    Which after all, was the point; to create a structure for which induction would automatically be valid.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,707
    Thanks
    1470

    Re: Question about successor functions.

    We start with an infinite set N (Can we do this? Do we know for certain anything infinite even exists? Gee, I don't know, but since the arithmetic system we'd LIKE to make is going to turn out to be infinite, we're going to have to assume we CAN do this).
    One way of doing that, 'prior' to Peano's axioms is this: define "0" to be the empty set. (Are you going to argue about whether that can exist?) Define "1" to be the set whose only member is the empty set- that is the set whose only member is "0". Define "2" to be the set whose only members are "0" and "1". In general, given any "number" n, which is now a set of objects, define its successor to be the set whose members are n and all members of n: n+ 1= {n}\cup n.

    That will be our set N and the "successor function" in Peano's axioms.
    (This includes "0" in N as Peano initially did. Of course, we would get exactly the same result defining "1" to be the empty set and continuing from there.)
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,392
    Thanks
    759

    Re: Question about successor functions.

    Quote Originally Posted by HallsofIvy View Post
    One way of doing that, 'prior' to Peano's axioms is this: define "0" to be the empty set. (Are you going to argue about whether that can exist?) Define "1" to be the set whose only member is the empty set- that is the set whose only member is "0". Define "2" to be the set whose only members are "0" and "1". In general, given any "number" n, which is now a set of objects, define its successor to be the set whose members are n and all members of n: n+ 1= \{n\} \cup n.

    That will be our set N and the "successor function" in Peano's axioms.
    (This includes "0" in N as Peano initially did. Of course, we would get exactly the same result defining "1" to be the empty set and continuing from there.)
    Indeed that is one way of showing we can obtain any given natural number as a set. The question then becomes: is this collection "small enough" to be a set (for example, if the "collection of all sets" was countable, so that we could identify any given set with its position in a list, it then becomes a thorny question as to where on the list, we put the name of the list itself)? You can also look at it from the other end: CAN sets be infinite? SHOULD they be infinite?

    This all boils down to the sense that we feel "something" ought to be infinite, because we see no reason why counting should ever terminate. We can't prove this from the other ZF axioms, though, so we add it as an extra assumption.

    Properly defined, however, the construction you suggest (along with some other niceties regarding addition and multiplication) serves as a MODEL for the Peano axioms (known as, unsurprisingly, the "standard model"). It is interesting to note this isn't the ONLY model, one can also define the natural numbers as:

    $0 = \emptyset$
    $1 = \{\emptyset\}$ (so far, they're the same)
    $2 = \{1\} = \{\{\emptyset\}\}$
    .....
    $s(n) = \{n\}$

    Another way to model the natural numbers is as the free monoid (or free semi-group, if one wants to start with 1) on a singleton set ("one letter"). While the machinery necessary to formalize this is formidable, it does correspond nicely to how we actually ideate about number: when we count things, the "things" we're counting (dollars, sheep, marks on a paper, oranges) aren't the important thing. This model gives us addition "for free", but showing it is inductive isn't nearly as "clean" as inductive definitions of natural numbers.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Regular Infinite Successor Cardinals
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: May 19th 2013, 02:31 PM
  2. Replies: 18
    Last Post: May 8th 2012, 12:33 PM
  3. Replies: 6
    Last Post: October 17th 2009, 07:16 PM
  4. Functions question
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: March 12th 2009, 06:09 AM
  5. Question about functions and a identity Question
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: September 8th 2008, 10:03 PM

Search Tags


/mathhelpforum @mathhelpforum