Turn on thread page Beta
    • Thread Starter
    Offline

    15
    ReputationRep:
    Anyway, a question came up http://www.dpmms.cam.ac.uk/site2002/...-2009/N+S1.pdf 8.(a).

    I quess the base case was the problem. But, lol.

    I was wondering, how do you if induction is valid? Maybe, the problem was with the base case i.e. that x=x is trivial and so shouldn't apply to most inductions. In the above question is the base case actually proven? maybe thats the problem. Although, x=x for all x's, so lol.

    But still, n=1 could be true and n=k implies n=k+1, but the induction could be invalid. Thats weird. I don't know but I get the scary thought that say at n=3 the induction could fail but it could be true that n=1 and n=k implies n=k+1. Will this every happen?

    P.S. You think you know something then bam right in the kisser.
    P.P.S. To please Totally Tom I have edited out the question. Can someone anwser the question about induction i.e. can n=1 be true and n=k imply n=k+1 but the induction false?
    Offline

    16
    ReputationRep:
    (Original post by Simplicity)
    Anyway, a question came up http://www.dpmms.cam.ac.uk/site2002/...-2009/N+S1.pdf 8.(a).

    I quess the base case was the problem. But, lol.

    I was also wondering is this a valid induction.

    If there exist an injection N_m \rightarrow N_n, then m \leq n

    So this is the induction hypothesis. I won't prove the base case.
    \forall m \in Z^{+}( \exist injection N_m \rightarrow N_k \Rightarrow m \leq k)

    So the book constructs a function g:N_{m-1} \rightarrow N_m
    g(i)={( i for i<i_0) and (i+1 for i \geq i_0)

    Now the book goes this. If f(i_0)<k+1 then
    fg: N_{m-1} \rightarrow N_k is cleary an injection so
    m-1 \leq k therefore m \leq k+1. Is this valid? as surely, induction hypothesis is for m not m-1. I guess it is valid because m-1 \in Z^{+}, I think. But if m=1 then m-1 \not \in Z^{+} so does this mean the argument in the book is invalid?

    Then, the other case i.e. f(i_0)=k+1 is prove similarly.

    I was wondering, how do you if induction is valid? Maybe, the problem was with the base case i.e. that x=x is trivial and so shouldn't apply to most inductions. In the above question is the base case actually proven? maybe thats the problem. Although, x=x for all x's, so lol.

    But still, n=1 could be true and n=k implies n=k+1, but the induction could be invalid. Thats weird. I don't know but I get the scary thought that say at n=3 the induction could fail but it could be true that n=1 and n=k implies n=k+1. Will this every happen?

    P.S. You think you know something then bam right in the kisser.
    would you stop harping on about this bloody question. KEEP IT TO ONE FLIPPING THREAD.

    /rant.
    • Thread Starter
    Offline

    15
    ReputationRep:
    (Original post by Totally Tom)
    would you stop harping on about this bloody question. KEEP IT TO ONE FLIPPING THREAD.

    /rant.
    When have I asked about this question?

    This thread isn't even about the question. Okay, if it will make you happy I have edited it out.
    Offline

    16
    ReputationRep:
    (Original post by Simplicity)
    When have I asked about this question?

    This thread isn't even about the question. Okay, if it will make you happy I have edited it out.
    ty.
    Offline

    16
    ReputationRep:
    the induction fails on the first one because nobody cares about the base case with 1 element, it doesn't work for the base case with 2 elements.
    what's the 'definition' of an interesting number? why aren't they all interesting? i don't really see it proving anything unless we define what an interesting number is.
    • Thread Starter
    Offline

    15
    ReputationRep:
    Thanks Totally Tom. I didn't know about interesting number paradox but yeah that explains it.

    I was going to ask what is the well ordering principle but the wikipedia article about interesting number explains what it is. I guess that explain why the book calls it the least criminal and then you have to prove that there is no least criminal.
    Offline

    16
    ReputationRep:
    (Original post by Simplicity)
    Thanks Totally Tom. I didn't know about interesting number paradox but yeah that explains it.

    I was going to ask what is the well ordering principle but the wikipedia article about interesting number explains what it is. I guess that explain why the book calls it the least criminal and then you have to prove that there is no least criminal.
    every non empty subset of the natural numbers has a least element
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by Simplicity)
    I quess the base case was the problem. But, lol.
    I spent a very long time explaining to you why the base case wasn't the problem. In the given problem, n=k only implies n=k+1 for k >= 2; when k = 1, we can't deduce that n=1 implies n=2, so the inductive step fails.
    Offline

    16
    ReputationRep:
    (Original post by generalebriety)
    I spent a very long time explaining to you why the base case wasn't the problem. In the given problem, n=k only implies n=k+1 for k >= 2; when k = 1, we can't deduce that n=1 implies n=2, so the inductive step fails.
    lol, troll'd.
    • Wiki Support Team
    Offline

    14
    ReputationRep:
    Wiki Support Team
    (Original post by Totally Tom)
    lol, troll'd.
    So I see.

    Perhaps I'll steer clear of Simplicity's threads from now on.
    • Thread Starter
    Offline

    15
    ReputationRep:
    (Original post by generalebriety)
    I spent a very long time explaining to you why the base case wasn't the problem. In the given problem, n=k only implies n=k+1 for k >= 2; when k = 1, we can't deduce that n=1 implies n=2, so the inductive step fails.
    Sorry, but that was bad wording. I think wikipedia has the best explanation, is that the argument relies on overlapping sets and this doesn't apply to a set of one element so the base case is really n=2.

    (Original post by Totally Tom)
    lol, troll'd.
    Totally Tom :rolleyes:

    I didn't troll gb.
    Online

    18
    ReputationRep:
    (Original post by Simplicity)
    Sorry, but that was bad wording. I think wikipedia has the best explanation, is that the argument relies on overlapping sets and this doesn't apply to a set of one element so the base case is really n=2.
    No, the base case is n = 1. (And I don't think Wikipedia says what you say it does - at least if you're referring to http://en.wikipedia.org/wiki/Mathema...erent_color.22)
    • Thread Starter
    Offline

    15
    ReputationRep:
    Okay, that was bad wording. I don't know actually how to say it, so yeah it fails for n=2/
 
 
 
Poll
Cats or dogs?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.