Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Induction proof on list

  1. Sep 16, 2011 #1
    1. The problem statement, all variables and given/known data

    Prove by finite list induction

    ∀xs:: [a]. map (\x -> x) xs = xs

    2. Relevant equations

    map f [ ] = [ ]
    map f (x : xs) = (f x) : map f xs

    3. The attempt at a solution

    The list induction principle to prove a finite lists of type a is

    [P([ ])^
    ∀x :: a. ∀xs :: [a]. P(xs) => P(x : xs)
    => ∀ys :: [a].P(ys)

    So, to show ∀ys :: [a]. P(ys) we need to show two things
    i.) P([ ])
    ii.) ∀x :: a. ∀xs :: [a]. P(xs) => P(x : xs)

    the i) part is really easy, it's just a base case but I am totally stomped on how to even go about proving the ii) part. I would like a guidance on this. Do I assume an arbitrary k of a newly list (that is previously constructed) and try to do an inductive proof? I don't know, I'm really lost.
  2. jcsd
  3. Sep 19, 2011 #2
    Bump :(
  4. Sep 21, 2011 #3
    Did I finally break the experts here with an unsolvable question?

  5. Sep 21, 2011 #4


    User Avatar
    Science Advisor
    Homework Helper

    Probably not unsolvable, but I can't make heads or tails of your notation. I was hoping somebody would come along who could. So you probably have succeeded in writing something nobody understands. Is this some kind of formal logic course?? Or abstract computer science?
  6. Sep 21, 2011 #5
    The class is known as Advanced Discrete Structures, crosslisted with Mathematics and Computer Science. Apparently we cover topics of both formal logic and abstract computer science.

    This is the notes we got from the professor. Maybe this would be of help?

    http://www.mediafire.com/?jasbcwfxycy5hmk [Broken]
    Last edited by a moderator: May 5, 2017
  7. Sep 24, 2011 #6
    You might consider taking a look at the Haskell community or other language theoretic sites like lambda the ultimate as this is really more of a computer science/type theory question.

    The following might help, you already have some of these steps but just to be explicit:
    1) Write out exactly what your predicate is (P = ?).
    2) Show "P []" holds.
    3) Assume "[itex]\forall[/itex] xs . P xs" and show "[itex]\forall[/itex] x . P (x :: xs)".
    Does this help at all?

    My category theory is not great by any measure but List is an endofunctor over the category of sets. To my knowledge :: is a Haskellism for type-of (presumably because they used up : for the list construction function) but I imagine it could have roots that go further back.
    Again I'm no expert but I think for notation "∀xs:: [a]" is universal quantification over the set produced from the functor List applied to the object "a" in the category of sets. The "map" is Haskell-lingo for a functor's action on arrows. The "(\x -> x)" is Haskell-lingo for a lambda term.
    Last edited: Sep 24, 2011
  8. Sep 24, 2011 #7


    User Avatar
    Science Advisor
    Homework Helper

    I am more than willing to take your word for it. This is definitely not my field.
  9. Sep 25, 2011 #8
    Looking over what I've said I'm not sure I really addressed your question very well so I'll be a bit more specific.

    All you know about the term "xs" is that it's a list of a's. We could perform case analysis and then have the two cases x:[] and x:x':xs', however we're stuck in the same situation with xs' as we were with xs. This is the intuition behind our use of induction to solve the problem. Our induction hypothesis tells us something about xs, can you state what that is?

    It will also be helpful to write out what you're trying to prove in its full form. What is P (x:xs)?
    Last edited: Sep 25, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook