Would you look at that? Some GYHD and some Happy Face Math, just for you. That’s pretty neat.

4.1 GYHD 2

Prove: If S and T are bounded above, then S U T is bounded above.

Assume that S and T are bounded above. This means (Ǝ x ϵ R)(∀ y ϵ S)(x ≥ y) and (Ǝ a ϵ R)(∀ b ϵ S)(a ≥ b). (We want to show that S U T is bounded above.) This means that x ϵ S U T and b ϵ S U T. This means, since x is an upper bound for S, and b is an upper bound for T, that a or b is an upper bound for S U T. This means that S U T has an upper bound, i.e. it is bounded above, which is what we wanted to show. □

4.2 GYHD 1

What would you need to have a counter to the statement “if A is a subset of B, then the power set of A is a subset of the power set of B”? To have a counter to its contrapositive, “If the power set of A is not a subset of the power set of B, then A is not a subset of B”?

To find a counter example to a statement, we must find an example such that, for p → q, p is true, but q is false. For the original statement, this means we want to find some sets A and B, such that A is a subset of B, but the power set of A is not a subset of the power set of B.

To find a counter example for ~q → ~p, we want to find an example where ~q is true, but ~p is false. For the contrapositive of the original statement, this means we want to find some sets A and B, such that the power set of A is not a subset of the power set of B, but A is a subset of B.

4.2 GYHD 4

State the negation of each of the following:

1)      f is surjective and injective (where f is a function)

~(f is surjective and injevtive) = f is not surjective or not injective

2)      x is even or x ≥ 3 (where x is a positive integer)

~(x is even or x ≥ 3) = x is not even and x < 3 = x is odd and x < 3

Proving That Something EXISTS

For any statement (Ǝ t)(q(t)), how do we prove it? Although there may be infinitely many t, such that q(t), we only need to provide one such t. In actually proving the statement, all that needs to be done is to assume the hypotheses, (Ǝ t), and show that the chosen t works.

Importance of the ORDER of Quantifiers

Does order matter? Are quantifiers “associative”? Let’s look at the statements below for sets S = R and S = R^≥0:

1)      (∀ x ϵ S)(Ǝ y ϵ S)(y ≤ x)

2)      (Ǝ y ϵ S)(∀ x ϵ S)(y ≤ x)

Statement 1) is an open sentence where x is a free variable. It says “there is an element of S which is less than or equal to x,” which is true no matter what set S is. Statement 2) can be simplified to “y is the smallest element of S” or “S has a smallest element.” However, the truth value of this statement depends on S. If S = R, the statement is false, because the set of reals has no smallest value. If S = R^≥0, then the statement is true, because there is a definite smallest element of the set of non-negative reals, i.e. 0.

SPECIALIZATION

The book goes on for about six pages about specialization, but here’s all Casey needs us to know, even if Fendel and Resek want us to memorize all six pages.

If we have a statement that can be expressed as two “if…, then…” statements, i.e. (a → b) → (c → d), the proof should be set up similarly to all other proofs that we have done so far. First, assume the hypothesis to be true. Here, the hypothesis is the entire “if…, then…” statement a → b. So, assume a → b. Next, we want to prove the conclusion, the second “if…, then…” statement, c → d. We do this my assuming c is true. Basically, c → d can be proven to be true, by assuming c is true. 

Proof by CONTRADICTION

A proof by contradiction attempts to prove a statement true, by showing that if it were false, we would have some impossibility as our outcome.

Can’t prove that p → q? Show that ~q → ~p, or prove it by the statement’s contrapositive. A proof by contrapositive is just another special case of a proof by contradiction.