Chapter 1 Logic and foundations 1.1. Material implication The material implication “If A, then B” (or “A implies B”) can be thought of as the assertion “B is at least as true as A” (or equivalently, “A is at most as true as B”). This perspective sheds light on several facts about the material implication: (1) A falsehood implies anything (the principle of explosion). Indeed, any statement B is at least as true as a falsehood. By the same token, if the hypothesis of an implication fails, this reveals nothing about the conclusion. (2) Anything implies a truth. In particular, if the conclusion of an implication is true, this reveals nothing about the hypothesis. (3) Proofs by contradiction. If A is at most as true as a falsehood, then it is false. (4) Taking contrapositives. If B is at least as true as A, then A is at least as false as B. (5) “If and only if” is the same as logical equivalence. “A if and only if B” means that A and B are equally true. (6) Disjunction elimination. Given “If A, then C” and “If B, then C”, we can deduce “If (A or B), then C”, since if C is at least as true as A, and at least as true as B, then it is at least as true as either A or B. (7) The principle of mathematical induction. If P(0) is true, and each P(n + 1) is at least as true as P(n), then all of the P(n) are true. (Note, though, that if one is only 99% certain of each implication 1 http://dx.doi.org/10.1090/mbk/081/01

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.