Results 1 to 5 of 5

Math Help - induction problem on set of propositions

  1. #1
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    induction problem on set of propositions

    hi

    Here is a problem I am trying to do from Kenneth Rosen's
    "Discrete mathematics..."

    Show that

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_{n-1}\to p_n)]\\ \to  [(p_1\wedge p_2\wedge\cdots\wedge p_{n-1})\to p_n]

    is a tautology whenever p_1,p_2,\cdots ,p_n are propositions, whenever
    n\ge 2

    Here is the proof I attempted.

    Base Case: n=2

    let p_1,p_2 be arbitrary propositions.Now consider

    (p_1\to p_2)\to (p_1\to p_2)

    To prove this, we assume antecedent and since the antecedent is same
    as consequent, it proves the above compound proposition . So
    P(2).

    Induction case: Let n\ge 2 be arbitrary. Also suppose
    P(n). To prove P(n+1), take arbitrary
    propositions p_1,p_2,\cdots,p_n,p_{n+1}. We have to prove
    that

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]\\ \to [(p_1\wedge p_2\wedge\cdots\wedge p_n)\to p_{n+1}]

    is a tautology. In other words, we have to prove it. Since its an implication,
    we suppose

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]

    and we also suppose that

    (p_1\wedge p_2\wedge\cdots\wedge p_n)

    It follows that, in particular,

    p_n

    and

    p_n\to p_{n+1}

    So by modus ponens, we have

    p_{n+1}

    which proves P(n+1)

    Since n is arbitrary, result holds generally.

    Is it correct reasoning ?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: induction problem on set of propositions

    Quote Originally Posted by issacnewton View Post
    Show that

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_{n-1}\to p_n)]\\ \to  [(p_1\wedge p_2\wedge\cdots\wedge p_{n-1})\to p_n]

    is a tautology whenever p_1,p_2,\cdots ,p_n are propositions, whenever
    n\ge 2
    This is quite an understatement because already

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_{n-1}\to p_n)]\to  [p_1\to p_n]

    is a tautology. Indeed, given p_1, we conclude p_2,\dots,p_{n-1},p_n in turn using implications.

    Quote Originally Posted by issacnewton View Post
    We have to prove
    that

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]\\ \to [(p_1\wedge p_2\wedge\cdots\wedge p_n)\to p_{n+1}]

    is a tautology. In other words, we have to prove it. Since its an implication,
    we suppose

    [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]

    and we also suppose that

    (p_1\wedge p_2\wedge\cdots\wedge p_n)
    There is a subtle difference between proving that if 2 > 0, then 2 > 0 and showing that p -> p is a tautology. In the first case, you assume 2 > 0 and (trivially) show the conclusion. In the second case, you need to prove that the truth value of p -> p is T in every interpretation. You consider an interpretation I. It follows from the truth table for implication that for any formulas A and B, I(A -> B) = T iff I(A) = T implies I(B) = T. So, you assume that I(p) = T and (trivially) show that I(p) = T.

    We have a mixture of two languages here. One is a metalanguage, where we say "2 > 0 implies 2 > 0." In proving such statement, we can say, "assume that 2 > 0." The second is an object language, which consists of propositional formulas like p -> p. In proving that p -> p is a tautology, we can't assume p because p is not a metalanguage proposition. However, object language propositions can be mapped to the metalanguage, e.g., p -> q becomes "(in some interpretation,) if p = T, then q = T." The truth tables of propositional connectives are designed so that p is a tautology iff p is mapped into a true statement of the metalanguage. Therefore, instead of showing that a formula of the object language is a tautology by considering interpretations and truth tables, we can prove its conversion to the metalanguage instead. This is called "reasoning inside propositional logic," and that's what you have done in your proof.

    In general, it's useful to signal this transition between the two languages to the reader by saying "assume that p = T" or "assume that p is true" instead of just "assume p." One can also say, "reasoning inside propositional logic, ...".

    Otherwise, you proof is fine.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of propositions

    Hi makarov

    Thanks for response in detail. I am not sure I understand everything. When we prove
    theorems in mathematics , are we not proving that those theorems , which are
    propositions , are tautologies ? Thats why they are called theorems. They are supposed to be true no matter what.

    So in my proof, instead of saying , "assume p" , I should have said "assume p is true",
    is that correct ? So , is the proof offered correct or not ? I was confused by your
    post a bit.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2010
    From
    Mumbai, India
    Posts
    203

    Re: induction problem on set of propositions

    makarov, can you please comment on my post ?

    thanks
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: induction problem on set of propositions

    The important thing to understand is that there is the ordinary language of mathematics, and then there is a set of words in the alphabet {(, ), ∧, ∨,→, , p1, p2, ...}. The words of the alphabet are meaningless until you design the rules to assign them T or F in a given interpretation (a mapping from variables to {T, F}) using truth tables. Even then, these words remain just strings of symbols. In Rosen, a "tautology" is a special kind of these strings that are assigned T in every interpretation. Proven mathematical statements, like 1 + ... + n = n(n + 1) / 2 are not tautologies in this sense; they even use a different alphabet.

    Edit: And yes, your proof is correct.
    Last edited by emakarov; October 15th 2011 at 02:59 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quantified Propositions to English
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 1st 2009, 03:19 AM
  2. Predicate calculus - propositions
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 2nd 2009, 09:50 PM
  3. [SOLVED] Proof of Propositions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 26th 2009, 04:15 AM
  4. propositions and logic help
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 22nd 2009, 05:57 PM
  5. Logic & Propositions & Proofs
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: September 9th 2008, 10:45 AM

/mathhelpforum @mathhelpforum