Thread: induction problem on set of propositions

hi

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

Show that



is a tautology whenever are propositions, whenever


Here is the proof I attempted.

Base Case:

let be arbitrary propositions.Now consider



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

Induction case: Let be arbitrary. Also suppose
. To prove , take arbitrary
propositions . We have to prove
that



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



and we also suppose that



It follows that, in particular,



and



So by modus ponens, we have



which proves

Since n is arbitrary, result holds generally.

Is it correct reasoning ?

Thanks

Originally Posted by issacnewton

Show that



is a tautology whenever are propositions, whenever

This is quite an understatement because already



is a tautology. Indeed, given , we conclude in turn using implications.

Originally Posted by issacnewton

We have to prove
that



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



and we also suppose that

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.

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.

makarov, can you please comment on my post ?

thanks

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.