SUNY Geneseo Department of Mathematics
Wednesday, March 10
Math 239 03
Spring 2021
Prof. Doug Baldwin
In particular, are there any questions on the discussion of proofs that use the contrapositive?
There were, in particular a request to go over contrapositives and how proofs that use them work.
Also a request to go over some of the questions on problem set 4.
So…
The basic idea is that since P → Q is equivalent to ¬Q → ¬P, you can prove a statement of either form by proving it in the other one if you prefer. In particular, it can be easier to prove a theorem involving a negative hypothesis and conclusion (e.g., “if P is not true, then Q is not true either”) by proving its contrapositive.
For example, consider the following claim: For all real numbers x, and all integers n not equal to 0, if x is irrational, then nx is irrational.
(This says that you can never “scale” an irrational number up to a rational by multiplying by an integer, for instance no integer multiple of π will ever be rational. But there are analogous settings with the opposite behavior, for instance you can “scale” rationals to integers by multiplying them by their denominator.)
The contrapositive of this statement is “for all real numbers x, and all integers n not equal to 0, if nx is rational then x is rational.”
We thought the contrapositive might be easier to prove than the original claim, and so did it formally in LaTeX. Both the source and PDF output documents are available in Canvas.
There were several questions about problem set 4, including…
To prove that X is a subset of Y you need to prove that every element of X is also an element of Y. This is a universally quantified statement. We developed a template for proving universally quantified statements when we talked about proofs and quantifiers; in this case that template suggests assuming that some value, say a, is in X and then showing that it must also satisfy the rules for being in Y.
To find the expressions involving quantifiers, I suggest breaking the English sentences down into pieces, especially pieces that define variables, which are likely to correspond to quantifiers, and pieces that describe relations between variables, which are likely to correspond to predicates.
For example, “if x is an element of ℤ-” defines a variable, and we’ve seen that “if…” statements often correspond to universal quantifiers, so “(∀ x ∈ ℤ-)” is probably a good start to the first statement.
When you think you’re finished with one of the statements, check that it corresponds to both the details of the English sentence and to it’s more intuitive meaning. For example, does your first expression mean “for every negative integer, there is not another negative integer that can be multiplied by the first to give a negative result,” and to the more intuitive “you can never multiply 2 negative integers and get a negative product”?
Once you have both statements written in forms you like, showing that they are equivalent (part C) should be a matter of invoking equivalence rules for quantifiers and their negations to show that one of the statements can be transformed via one or more equivalences into the other.
Problem set 5, involving proofs via the contrapositive and proofs of biconditionals is now available.
Finish it by next Wednesday (March 17), and grade it by the following Wednesday (March 24),
We’ll look at proving biconditionals, as was originally planned for today.
Do (or review) the reading on biconditionals (“Beginning Activity 2 (A Biconditional Statement),” “Proofs of Biconditional Statements,” and “Writing Guidelines” (the second such subsection, about writing proofs of biconditionals) in section 3.2 of the textbook).
Also please start practicing some of the things we’ll talk about in Friday’s class in this discussion of biconditionals.