SUNY Geneseo Department of Mathematics
Monday, February 26 - Wednesday, February 28
Math 239 01
Spring 2018
Prof. Doug Baldwin
An Overview of Inverse Problems.
Many mathematical models are essentially functions that take certain inputs and some internal parameters and produce a modeled value for something; this is a “forward” problem. But it’s also common to have a known output, e.g., observed values for a physical system, and want to know what inputs or internal parameters could have produced it; this is the “inverse” problem.
Sedar Ngoma, Geneseo.
Friday, March 2, 2:30, Newton 203.
Extra credit, as usual.
The proof that if n is odd then -n is odd needs detail beyond just saying that -n = -(2x+1). The definition of “odd number” doesn’t allow the negation in -(2x+1), so you have to find some way to show that -(2x+1) is of the form 2y + 1 for some integer y. For example -(2x+1) = -2x - 1 = -2x - 2 + 1 = 2(-x-1) + 1. Then note that because the integers are closed under subtraction and (-x-1) is really 0 - x - 1, this is in the right form to be an odd integer.
Showing that (P ∨ Q) ∧ ¬(P ∧ Q) is equivalent to (P ∧ ¬Q) ∨ (¬P ∧ Q) is easier via truth tables than via equivalences.
The proof-out-of-context in problem set 4 should be a formal proof.
Section 3.4
Flesh preview activity 1 out to a complete proof.
Theorem: If x and y are integers and xy is odd, then x is odd and y is odd.
Proof: We will use cases to prove the contrapositive of the claim that if x and y are integers and xy is odd, then x is odd and y is odd. The contrapositive is if x is even or y is even then xy is even.
For the first case we assume that x is even. We can therefore write x = 2n for some integer n. Then
xy = (2n)y
= 2(ny)
Since integers are closed under multiplication, ny is an integer and so we see that xy has the form of an even integer.
For the second case, we assume y is even. The proof is then similar to the proof for case 1.
Since x is even or y is even are all the cases in the hypothesis of our contrapositive, we have now proven through those cases that if x is even or y is even then xy is even. Since this the contrapositive of the original theorem, we have also proven that if x and y are integers and xy is odd, then x is odd and y is odd. QED.
Notice that this proof uses multiple paragraphs to reflect the structure of the logic, e.g., each case is a separate paragraph. Also notice that the conventions about identifying the proof technique(s) that will be used become more important as you have a richer set of techniques to choose from and combine. Similarly, as proofs get longer, the need for an end-of-proof marker such as “QED” becomes clearer.
You could also set this up as a proof by contradiction with cases, i.e., start with “We will use contradiction to prove that if x and y are integers and xy is odd, then x is odd and y is odd. In particular, we assume that x and y are integers and xy is odd, but x is even or y is even, and derive a contradiction.” You would then use the same cases we did above, in each deriving the contradiction that xy is even instead of odd.
Or, rather than making each case separate, you could combine them into a single general argument using the phrase “without loss of generality,” i.e., “We will use cases to prove the contrapositive of the claim that if x and y are integers and xy is odd, then x is odd and y is odd. The contrapositive is if x is even or y is even then xy is even. There are 2 cases, depending on whether x or y is even. Without loss of generality, let x be the even number. We can therefore write x = 2n for some integer n. The product xy therefore equals (2n)y which in turn equals 2(ny). Since integers are closed under multiplication, ny is an integer and so we see that xy has the form of an even integer....” But be very careful about combining cases like this, as they are harder to readers to follow, and it’s easy for the writer to mistakenly think that two cases combine into one general argument when in fact they don’t.
Prove that the function
f(x) = -(x2) if x < 0 (part A)
f(x) = x2 if x ≥ 0 (part B)
is an increasing function.
Definition: A function f is increasing if and only if for all x and y in the domain of f, x > y implies that f(x) ≥ f(y).
Observation: any value computed through part A will be less than any value from part B
Observation: reasonable cases for a proof seem to be...
Theorem: Function f defined above is increasing.
Proof: We will prove by case analysis that f is increasing. In particular, we assume that x and y are real numbers with x > y, and show that f(x) ≥ f(y) by considering the following cases: x < 0 and y < 0, x ≥ 0 and y ≥ 0, and x ≥ 0 and y < 0.
In the first case, x < 0 and y < 0, we see that x2 < y2 since x > y and both are negative. Thus f(x) = -(x2) ≥ -(y2) = f(y).
In the second case, x ≥ 0 and y ≥ 0, we have x2 > y2. This in turn means f(x) ≥ f(y), since f(x) = x2 and f(y) = y2.
In the final case, x ≥ 0 and y < 0, we see from the definition of f that f(y) < 0 and f(x) ≥ 0, so f(x) ≥ f(y).
We have now shown that in all cases if x > y then f(x) ≥ f(y). We thus conclude that function f defined above is increasing. QED.
Note that you can also do more detailed proofs about the relationship between the squares of x and y. For example, in the case where x and y are both positive, argue that since x > y, we can think of x = y + r for some real r > 0. Then f(y) = y2, f(x) = (y+r)2 = y2 + 2yr + r2 which is greater than y2 because r > 0.
Breaking proofs into cases is a “thing” at all.
The structure of such proofs tends to include an introductory paragraph, paragraphs for each of the cases, and a concluding paragraph.
Sometimes cases come directly from theorems/definitions, but sometimes not.
(Probably for March 2.)
The division algorithm and congruence and their application to case-based proofs.
Read section 3.5.