Question

1. Define lemma?
2. What is Proof by Contraposition?
3. Define Proof?

Answer 1

LEMMA

A less important theorem that is helpful in the proof of other results is called a lemma (plural lemmas or lemmata). Complicated proofs are usually easier to understand when they are proved using a series of lemmas, where each lemma is proved individually.statements that were proved already; the difference between a theorem and a lemma is whether it is intended as a final result or an intermediate tool

PROOF

A proof is a valid argument that establishes the truth of a mathematical statement. A proof can use the hypotheses of the theorem, if any, axioms assumed to be true, and previously proven

theorems. Using these ingredients and rules of inference, the final step of the proof establishes the truth of the statement being proved.

A proof is a way to derive statements from other statements. It starts with axioms (statements that are assumed in the current context always to be true), theorems or lemmas (statements that were proved already; the difference between a theorem and a lemma is whether it is intended as a final result or an intermediate tool), and premises P (assumptions we are making for the purpose of seeing what consequences they have), and uses inference rules to derive Q. The axioms, theorems, and premises are in a sense the starting position of a game whose rules are given by the inference rules. The goal of the game is to apply the inference rules until Q pops out. We refer to anything that isn’t proved in the proof itself (i.e., an axiom, theorem, lemma, or premise) as a hypothesis; the result Q is the conclusion.

When a proof exists of Q from some premises P1, P2, . . . , we say that Q is deducible or provable from P1, P2, . . . , which is written as

P1,P2,... ⊢ Q.
If we can prove Q directly from our inference rules without making any assumptions, we may write

⊢Q

The turnstile symbol ⊢ has the specific meaning that we can derive the conclusion Q by applying inference rules to the premises. This is not quite the same thing as saying P → Q. If our inference rules are particularly weak, it may be that P → Q is true but we can’t prove Q starting with P. Conversely, if our inference rules are too strong (maybe they can prove anything, even things that aren’t true) we might have P ⊢ Q but P → Q is false.

For propositions, most of the time we will use inference rules that are just right, meaning that P ⊢ Q implies that P → Q is a tautology, (soundness) and P → Q being a tautology implies that P ⊢ Q (completeness). Here the distinction between ⊢ and → is whether we want to talk about the existence of a proof (the first case) or about the logical relation between two statements (the second).

Things get a little more complicated with statements involving predicates. For predicate logic, there are incompleteness theorems that say that if our system of axioms is powerful enough (basically capable of representing arithmetic), then there are are statements P such that neither of P or ¬P are provable unless the theory is inconsistent.

Proof by Contraposition

Proof by contraposition is a method of proving theorms.Direct proofs lead from the premises of a theorem to the conclusion. They begin with the premises, continue with a sequence of deductions, and end with the conclusion. However, we will see that attempts at direct proofs often reach dead ends. We need other methods of proving theorems of the form ∀x(P (x) → Q(x)). Proofs of theorems of this type that are not direct proofs, that is, that do not start with the premises and end with the conclusion, are called indirect proofs.

An extremely useful type of indirect proof is known as proof by contraposition. Proofs by contraposition make use of the fact that the conditional statement p → q is equivalent to its contrapositive, ¬q → ¬p. This means that the conditional statement p → q can be proved by showing that its contrapositive, ¬q → ¬p, is true. In a proof by contraposition of p → q, we take ¬q as a premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that ¬p must follow.