SUNY Geneseo Department of Mathematics
Wednesday, March 3
Math 239 03
Spring 2021
Prof. Doug Baldwin
Next Monday I will be helping run a virtual conference all afternoon. This course will have some asynchronous online activity that day instead of an in-person class — watch the announcements for details.
(No.)
Based loosely on section 2.4 in the textbook and the second part of the advanced quantifiers discussion.
How would you prove “there exists an integer greater than 10”?
Give an example, e.g., 11.
How about “there exists a real number, x, such that 3x2 + 1 = 13”?
Use algebra to find x = 2 as an example.
We wrote this as a formal proof in LaTeX. You can download the LaTeX source and view the output document through Canvas.
Generalizing what we did for these proofs, many statements of the form (∃ x ∈ U) P(x) can be proven simply by showing an example. Sometimes there are plentiful examples, but other times there are only one or two and they can be hard to find. (And sometimes you have a so-called “nonconstructive proof,” in which you show that an example must exist without specifically finding it.)
How would you prove “every even integer is of the form n + 2 where n is another even integer”?
This ended up being very much like previous proofs, in that we assumed that we had an even integer, and showed that it had to be of the right form. This proof is the second one in the same LaTeX source document and output that holds the example proof for an existentially quantified statement.
The general pattern for proving universally quantified statements, i.e., statements of the form (∀ x ∈ U) P(x), is to assume x is an element of U (and assume nothing else about x), and show that P(x) must hold. Because you used nothing about x except that its in U, the argument must hold for every member of U.
We wrote formal versions of some of today’s proofs in LaTeX, and encountered some new LaTeX features as well as some new guidelines for writing proofs while doing so. In particular, we saw…
Mathematicians actually favor the use of English sentences over dense mathematical expressions for clarity. Thus, for example, even though we were writing theorems and proofs involving quantifiers, there isn’t a single quantifier symbol in our results. There are, however, plenty of uses of such English phrases as “there exists,” “every,” etc.
Similarly, mathematical style insists that sentences should start with words, not variable names or symbols.
We’re starting to see opening sentences of proofs that not only say what is about to be proved, but also hint at how. For example, “We will show that there exists … by solving for it.” This signaling of proof strategy will become more common as we get a larger set of techniques for doing proofs.
In LaTeX, the align* environment lets you write a series of lines of text in such a way that they have some character or position aligned as you read down the page. Typically the lines of text are equations, and they align the “=” signs or some similar character. Within align*, use & to mark the place you want aligned in each line, and \\ to indicate the end of each line (except the last).
We also saw a handful of new LaTeX commands, including \ldots to generate an ellipsis (3 dots), \rightarrow to generate a rightward pointing arrow or “implies” symbol, and \pm to generate a plus-or-minus symbol.
Finally, I recommend writing numbers in LaTeX in math mode. This matters if the numbers are negative, where math mode will tell LaTeX to put a minus symbol before the number, rather than a hypen (they’re different lengths).
Problem set 4, on quantifiers and sets, is now available. Work on it during the rest of this week or first part of next, and grade it between next Wednesday and the Wednesday after.
We’ll start looking at many common proof techniques, material that is the real heart of this course. But first I want to look at some new properties of integers — divisibility and congruence — that provide some additional contexts in which to do proofs.
So please read “Beginning Activity 1 (Definition of Divides, Divisor, Multiple),” “Beginning Activity 2 (Calendars and Clocks),” and “Congruence” in section 3.1.
I strongly recommend at least glancing over the rest of section 3.1 for some examples of proofs involving divisibility and congruence, some new tips on writing proofs, and some review of what we’ve done so far with respect to proofs.
Finally, please contribute to this discussion of divisibility and congruence.