Linear Algebra/Propositions

Linear Algebra Propositions Appendix Quantifiers propThe point at issue in an argument is the proposition. thmMathematicians usually write the point in full before the proof and label it either Theorem for major points, Corollary for points that follow immediately from a prior one, or Lemma for results chiefly used to prove other results. The statements expressing propositions can be complex, with many subparts. The truth or falsity of the entire proposition depends both on the truth value of the parts, and on the words used to assemble the statement from its parts. Not For example, where is a proposition, "it is not the case that " is true provided that is false. Thus, " is not prime" is true only when is the product of smaller integers. VennWe can picture the "not" operation with a Venn diagram. x200px Where the box encloses all natural numbers, and inside the circle are the primes, the shaded area holds numbers satisfying "not ". To prove that a "not " statement holds, show that is false. And Consider the statement form " and ". For the statement to be true both halves must hold: " is prime and so is " is true, while " is prime and is not" is false. Here is the Venn diagram for " and ". x200px To prove " and ", prove that each half holds. Or A " or " is true when either half holds: " is prime or is prime" is true, while " is not prime or is prime" is false. We take "or" inclusively so that if both halves are true " is prime or is not" then the statement as a whole is true. (In everyday speech, sometimes "or" is meant in an exclusive way— "Eat your vegetables or no dessert" does not intend both halves to hold— but we will not use "or" in that way.) The Venn diagram for "or" includes all of both circles. x200px To prove " or ", show that in all cases at least one half holds (perhaps sometimes one half and sometimes the other, but always at least one). If-then implicationAn "if then " statement (sometimes written " materially implies " or just " implies " or "") is true unless is true while is false. Thus "if is prime then is not" is true while "if is prime then is also prime" is false. (Contrary to its use in casual speech, in mathematics "if then " does not connote that precedes or causes .) vacuousMore subtly, in mathematics "if then " is true when is false: "if is prime then is prime" and "if is prime then is not" are both true statements, sometimes said to be vacuously true. We adopt this convention because we want statements like "if a number is a perfect square then it is not prime" to be true, for instance when the number is or when the number is . The diagram x200px shows that holds whenever does (another phrasing is " is sufficient to give "). Notice again that if does not hold, may or may not be in force. There are two main ways to establish an implication. The first way is direct: assume that is true and, using that assumption, prove . For instance, to show "if a number is divisible by 5 then twice that number is divisible by 10", assume that the number is and deduce that . contrapositiveThe second way is indirect: prove the contrapositive statement: "if is false then is false" (rephrased, " can only be false when is also false"). As an example, to show "if a number is prime then it is not a perfect square", argue that if it were a square then it could be factored where and so wouldn't be prime (of course or don't give but they are nonprime by definition). Note two things about this statement form. First, an "if then " result can sometimes be improved by weakening or strengthening . Thus, "if a number is divisible by then its square is also divisible by " could be upgraded either by relaxing its hypothesis: "if a number is divisible by then its square is divisible by ", or by tightening its conclusion: "if a number is divisible by then its square is divisible by ". Second, after showing "if then ", a good next step is to look into whether there are cases where holds but does not. The idea is to better understand the relationship between and , with an eye toward strengthening the proposition. Equivalence An if-then statement cannot be improved when not only does imply , but also implies . Some ways to say this are: " if and only if ", " iff ", " and are logically equivalent", " is necessary and sufficient to give ", "". For example, "a number is divisible by a prime if and only if that number squared is divisible by the prime squared". The picture here shows that and hold in exactly the same cases. x200px Although in simple arguments a chain like " if and only if , which holds if and only if ..." may be practical, typically we show equivalence by showing the "if then " and "if then " halves separately. Linear Algebra Propositions Appendix Quantifiers