So I went to this Blogging 101 talk on Friday just to see what it was all about, and Casey was there to give a talk about his mathy blog. He started talking about how blogging gave him the opportunity to hash things out in a low stress situation. Therefore, this is my attempt to work out the homework that’s due tomorrow as I type this, because low-stress sounds good to me right about now.

## 4.1 Homework

**7**. For f:A→B and g:B→C, if g∘f is surjective and g is injective, then f is surjective.

Casey told us in class that to solve a proof you think of two things: what do I have to do, and what can I use?

*What do I have to do?* I have to prove that, given the hypothesis, the function f is surjective, which means that (∀v∈B)(∃u∈A)(f(u)=v).I can do this by using some element in B, we’ll call it b, and proving that there is some other element in A (let’s call it a) that fulfills f(a)=b.

*What can I use?* What can’t I use, really?!

- f:A→B and g:B→C, which means that g∘f: A→C

- g∘f is surjective, which means that (∀c∈C)(∃a∈A)(g∘f(a) = c)
- g is injective, which means that (∀b,d∈B)(g(b) = g(d) ⇒ b=d)

There’s an example in the section on pg. 144-145 that follows a similar structure, and another one that uses injectivity on pg. 139-140, so I’m going to try to combine those two examples to prove this. The problem solves it by drawing similarities between various domains and codomains of the functions involved, and using that to substitute and prove that the element needed exists. The other example on 139 uses injectivity to substitute in elements for various injective function to get to a desired element.

(Sorry for the language but this gif is so appropriate right now)

Let’s look at g∘f. If we put in an a, we get a c. Elements in C are the codomain for g, which means that whenever two codomains (c elements) equal each other, their corresponding b elements are the same as well. B is the codomain for f. To break it down a little simpler, whatever b’s we put into g, two identical outputs will give us one b element as the input.

g∘f(a) →[g(b) = g(d) ⇒ b=d]→ g(b) = c.

But that doesn’t prove anything. I think we can go ahead and prove by contradiction on this one. If f wasn’t surjective, and f(a)≠b, then we would not be able to have the true statement g∘f(a) = c, because f(a) = b is a necessary intermediary step that needs to be true. Δ

**8.** For f:ℝ→ℝ, is f is strictly increasing, then f is injective.

*What do I have to do? *I have to prove that (∀b,d∈ℝ)(g(b) = g(d) ⇒ b=d).

*What can I use?*

- f:ℝ→ℝ

- f is strictly increasing, which means (∀x,y∈ℝ)(x<y ⇒ f(x)<f(y))

In this case, b,d,x and y are all part of the same set of real numbers. The hypothesis states that for every point on the x-axis (x) that is greater than another x-axis point (y), x’s y-axis point is automatically greater than y’s. Intuitively, it makes sense that this function is injective, because of a function is always increasing, no two y-intercept’s can be the same that are attached to two different x-intercepts.

To prove the FOMy way, we assume that x<y ⇒ f(x)<f(y) is true for some elements x,y that are part of the real numbers, and then prove that b and d equal x and y. I think we can prove this by assuming that the hypothesis is true, and then assuming that the hypothesis [ (∀b,d∈ℝ)] of the conclusion is true, to try and prove that g(b) = g(d) ⇒ b=d. If we are assuming true both that (∀x,y∈ℝ) and (∀b,d∈ℝ), we can substitute x and y in for b and d. So the new statement will be:

g(x) = g(y) ⇒ x=y. To break it down even further, suppose g(x) = g(y) is true. Now we are only trying to prove that x = y.

But we’re also assuming that if x<y ⇒ f(x)<f(y). So if what we know is true, when g(x) = g(y), x cannot be less than y, because the function is increasing. x cannot be great than y, because that implies that g(x)>g(y). Therefore, by cases, x must equal y. Δ

**9.** Consider this definition: For sets A and B, “=A<=B” means that there is an injective function f:A→B.

**A.** For =A<=B to be true, this means that conditions for injectivity must be present. For a function to be injective, A must be smaller than or equal to the size of B, as all elements in A need to have a unique output to attach themselves to.

**B. **

**i)** If f:A→B, and f:B→C, then f:A→C.

If f:B→C [c=c’ ⇒ b = b’] and f:A→B [b=b’⇒ a = a’], then through substitution, c = c’ ⇒ a = a’. Through definition of injectivity, this is true.

**ii)**For any set A, =A ≤ =A, meaning there is an injective function f:A→A. This is true, because for any set, you can always use the function f(a) = a to map the function in a one-to-one manner to itself. So this is true.

**iii)** If =A ≤ =B and C is any set, =A ∪ =C ≤ =B∪=C. This is basically saying that if there is an injective function f:A→B, then the union of A and some other set has the same relationship with union of set B and that same set. I think this is true, because if there is at least one injective function from A to B, that function will still exist in the new set of =A ∪ =C → =B∪=C.

**iv)** If =A ≤ =B and C is any set, =A∩ =C ≤ =B∩=C.

I don’t think this is true. Say A = {1,2,3,4}, B = {6,8,10,14} and C = {1,2,3,4,10,14,20,30}.

The injective function from A → B matches: 1→ 6, 2→ 8,3→ 10,4→ 14.

=A∩ =C = {1,2,3,4}

=B∩=C = {10,14}

From part A of this problem, we know =A must be bigger than =B, which is not true in this case.

**v) **If A⊆B, and =B≤=A, then A=B.

If A is a subset of B, we know that A must be smaller than or equal to B. If =B≤=A, we know that B must be smaller than or equal to A. So the only thing that can make both of these conditions true would be for A to equal B.

**13b. **Evaluate this theorem/proof.

Theorem: For x,y∈ℕ, if x|y, then x≤y.

Proof: Assume that x,y∈ℕ, with x|y, so there is an element w ∈ ℤ such that xw = y. We first show that w must be positive. By basic assumption, w must be positive, negative, or zero. If w=0, then xw = 0, so y is zero. If w is negative, then xw < 0, so y is less than zero, even though y is positive (natural number). Since w>0, w≥1, so xw ≥ 1x. It also follows that xw≥x. By substitution, y≥x.

Proof by cases was done right, and the two previous cases were thrown out because they contradict the hypothesis. You can make the jump from w>0 ⇒ w≥1, since w must be an integer, and we already threw all the negatives and zero out. Multiplying both sides by x is fine, and 1x is equivalent to x. Substitution checks out as well to make y≥x. I think this proof is correct, but it goes about a very roundabout way of proving something that doesn’t revolve around what w is. The only thing really wrong is that it doesn’t state what we are trying to prove, that x≤y.

## 4.2 Problems

**8. **Prove “if x²-3x+2>0, then x>2 or x<1” by contrapositive. To prove by contrapositive, the new statement is if if x²-3x+2≤0, then x≤2 or x≥1. To do this, we should factor x²-3x+2. The factors come out to be (x-2) and (x-1). So, for this statement to be equal to zero, x must either be 2 or 1. For the statement to be less than or equal 0, x must be greater than or equal to one (putting in a zero for x give the false statement 2≤0), and less then or equal to two (putting in a 3 for x gives the false statement 2≤0).

**11. **Evaluate proof.

Theorem: If x is a non-zero integer, then x is both positive and negative.

If we were to prove by contradiction, the proper way to contradict the statement would be to say x is either positive or negative, not that neither is true. We can use the same trichotomy principle, which proves that an integer is either 0, >0, or <0, not AND, so the theorem is false because the contradiction of it holds true by the trichotomy principle.

## Worksheet Problems

**3. **To prove (P⇒Q)⇒(R⇒S), we hold that (P⇒Q) is true, and we hold that R is true. We then focus on trying to prove that S is implied by R.

**6. **To prove ∀x∈A ∃y ∈ B P(x,y), we assume that x is in A, and we focus on trying to find a y in B that makes the open statement P(x,y) true.

**9. **Proof by induction of (A_{1 }∪ A_{2 }∪ … ∪ A_{n)}’ = A_{1}’_{ }∪ A_{2}’_{ }∪ … ∪ A_{n}’.

Start with the base case of (A_{1})’ = A_{1}‘, which is true. If this is true, then (A_{1 }∪ A_{2 }∪ … ∪ A_{k)}’ = A_{1}’_{ }∪ A_{2}’_{ }∪ … ∪ A_{k}’ is true. And since that is true, we know that (A_{1 }∪ A_{2 }∪ … ∪ A_{k+1)}’ = A_{1}’_{ }∪ A_{2}’_{ }∪ … ∪ A_{k+1}’ is also true because (A_{1 }∪ A_{2 }∪ … ∪ A_{k)}’ = A_{1}’_{ }∪ A_{2}’_{ }∪ … ∪ A_{k}’ is true, and (A_{k+1})’= A_{k+1}’ is true as proved by the base case.

This took me entirely too long, BUT IT’S DONE.