This is the website I use to type all of the mathy type stuff like ∀∃⇔∈⊆ℕℚℝℤ∅: it makes blogging so much easier.

# Monthly Archives: March 2013

# Class Review: Class Equivalencies

So today in class we went through this whole concept of class equivalencies. It basically twists the whole idea of sets, elements, and how they’re related. The whole class I was just sitting there like –

But I think I understand everything. Let’s see if I actually do or if I’m just bs’ing here.

An *equivalence relation* on a set S is a subset SxS satisfying the following R (relation):

- Reflexive property: (∀x∈S)((x,x)∈R). This means that every element relates to itself in some way.
- Symmetric property: (∀x,y∈S)((x,y)∈R ⇒ (y,x)∈R). This property guarantees that the relation between x and y, also relates y to x. Casey used the example of brothers. If I have a brother, I’m related to him and he’s related to me (thank god I don’t have a brother)
- Transitive property: (∀x,y,z∈S)([(x,y)+(y,z)∈R] ⇒ (x,z)∈R). The transitive property is like the symmetric property, but with three elements, sort of. It’s like saying my brother has a brother. I’m obviously related to both brothers (again thank god this is not true)

We can talk about this same relation in terms of *wiggling*.

A *wiggle* relates pairs of elements in S, such that:

- Reflective: (∀x∈S)(x~x)

- Symmetric: (∀x,y∈S)(x~y ⇒ y~x)
- Transitive: (∀x,y,z∈S)(x~y + y~z ⇒ x~z)

There’s even more notation!

*The equivalence class containing x. *

Given an equivalence notation, ~, for some set, S:

[x] = {s∈S: x~s}. This is basically saying that in the set of [x], the elements signify the relation between x and elements in S.

Yeah, there’s EVEN MORE.

There’s this weird notation: S/~, which is defined as {[x]:x∈S}. This notation concerns sets of different equivalence classes.

This example in class helped me figure it out. We talked about groups earlier in the class, so we brought it back once again. Say the set S that we’re talking about is all the integers. The wiggle that relates x and y (x~y) is: x-y∈ nℤ. In this case, let’s say n=8.

ℤ/~ = {[x]: x∈ℤ} = {[0],[1],[2],[3],[4],[5],[6],[7]}.

The set of [0] is all multiples of 8. When these number are divided by eight, there is no remainder, which is why you can designate it as 0. This is just a representative number for the set though and a very straightforward one at that. Any multiple of 8 can be chosen to represent this wiggle set, like -64, 8, 16, whatever.

The set of [1] includes all multiples of 8 that have a remainder 1. Numbers in this set include 17 (17/8 = 2 R1), 9 (9/8 = 1 R1), and 25 (25/8 = 3 R1), along with infinitely many more.

This is how all these sets are related to the integers.

We also went over another example that ended up giving us a donut, but we’ll go over that later.

# FOM Book: 5.1 (Induction)

This section is all about defining induction through set notation, exploring the relationship between natural numbers and inductive sets, and finally looking at cardinality of power sets.

**Definition 5.1 :** a set of numbers is called *inductive* if (∀t)(t∈S⇒t+1∈S) AKA closed under adding one.

**GYHD1**

Two inductive sets:

{1/2,3/2,5/2,7/2,9/2…}

{-4,-3,-2,-1,0,1…}

Two non-inductive sets:

{-3,-1,1,3,5,7,9…}

{1,2,3,4}

*Are there any finite inductive sets?* Thinking about it, the only possible way that could happen is if the last number in the set looped to some other number in the set. There’s no way this is possible because there will always be a biggest number in a finite set, and the biggest number + 1 will not be included in the set.

*What about the empty set?* The empty set contains no element, so the first part of the inductive definition (∀t)(t∈S) cannot be true, because once there is an element in set S, it is no longer the empty set. So since the hypothesis is false, does that make the empty set vacuously inductive?

**Natural Numbers**

ℕ is the smallest inductive set containing 1.

**Axiom 5.1(Principle of Induction):** Any set which contains 1 and which is inductive must contain all natural numbers. Therefore, for any set S, if 1∈S and S is inductive, ℕ⊆S. For any open statement p(n), if “p(1)“ and “(∀t∈ℕ)(p(t)⇒p(t+1)“ are both true, then “(∀n∈ℕ)(p(n))“ is true.

**Theorem 5.2:** If n is a natural number, then n<2^{n}. This can be rephrased in quantifier notation as (∀n∈ℕ)(n<2^{n}). To prove this for all natural numbers, we need to also prove (∀t)(t∈P⇒t+1∈P), where P is the truth set of n<2^{n}.

^{n}(for the universe = ℕ).

^{1}. This statement is true, so 1∈P.

^{t+1}is true.

^{t. }

^{t}.

^{t}= 2

^{(t+1)}

^{(t+1)}

^{(t+1).}

**Theorem 5.3:**For any n∈ℕ,

^{3}+ 2

^{3}+ 3

^{3}+…+ n

^{3}= ((n(n+1))/2)²

**Theorem 5.5:**Generalized theorem of induction for any set S and any k∈ℤ, if k∈S and S is inductive, then ℕ

_{[k,∞]}⊆ S.

_{[1,∞] }= ℕ

_{[0,∞]}= Whole numbers.

**Theorem 5.6:**For n∈ℕ, n≥6, (n+1)²≤2

^{n}.

^{n}for universe ℕ

_{[6,∞]}, and let P be it’s truth set.

_{[6,∞]}: (n+1)²≤2

^{n}}

^{6 }which is true.

^{t},we need to prove that ((t+1)+1)² ≤ 2

^{t }× 2

^{1}, which simplifies to (t+2)² ≤ 2

^{t }× 2

^{1}. Using

**Lemma 5.7**, for t∈ℤ, if t≥6, then (t+2)² < 2(t+1)². From this, we then get (t+2)² ≤ 2(t+1)² < 2

^{t }× 2

^{1 = }2

^{(t+1)}, which, simplified is what we are trying to prove.

^{(t+1)}.

**Theorem 5.9′:**for any n∈W. If |A| = n, then |

*P*(A)| = 2

^{n. }

# Class Review: Pentagonal Numbers

Class confused me today, but my favorite part had to be when we talked about pentagonal numbers. I didn’t even know those were a thing. Basically you start with 1 (just go with it). The next pentagonal number comes from drawing a pentagon, so you get five points, therefore 5 is the next pentagonal number. For the next number, you extend that first pentagon, and draw another bigger pentagon around it, using three dots as the base instead of only two. The next number of dots you get is 12! Then 22, 35, and so on! One of the equations for pentagonal numbers is [n(3n-1)]/2.

The FOMy connection would be that, once you have the equation for pentagonal numbers, you can prove it by induction. Induction is a wonderfully simple proof device, as long as your already have the answer. That is, proof by induction revolves around the fact that you already have a claim to prove. It does not help you to explore the actual problem to figure out a claim.

But in this case, we have an equation!!

First off, we’d start with the base case, we’ll use one. If we plug 1 into the equation, we get one! Meaning that the first pentagonal number is 1. So the base case of one works.

Next is the induction step. We’ll assume that [k(3k-1)]/2 is true. Now we just need to connect the k case to the [{k+1}(3{k+1}-1)]/2 case.

Does anyone have any ideas on this? The usual method would be to take out something from the k+1 equation, so that you have a k case, which was can assume that part is true, and then usually the base case or something similar, but I can’t think of how to pull this equation apart.

# Class Review: I did my homework wrong

I learned a lot in class today that I’d been mixing up. Who knew I was actually this clueless?

First of all, contrapositive takes an if, then statement (P⇒Q), and makes it into ~Q⇒~P, NOT ~P⇒~Q (this is the inverse).

I also did 9.B.iii. on the homework pretty wrong. The question wants us to prove that if =A ≤ =B and C is any set, then =A ∪ =C ≤ =B ∪ =C. I tried to intuitively prove this by saying that A will map to B, and C will map to itself. But someone else in class brought up the counterexample that if C has a lot more in common with B than with A. That would make the union of B and C smaller than the union of A and B, so there is no one-to-one function that can map from A∪C to B∪C.

Someone else really smart in my class helped me figure out 4.1 #7. I was really confused how to use an injective function and surjective function to prove a third is surjective, but she explained that you can use g∘f being surjective to make g∘f(a) = g(b), because g is injective (which relates the B in g and the B in f), so f(a) = b.

Finally, the POW #8 did not go as I thought it would. S≅ℤ_{2}×ℤ_{2} does not really mean that these sets are equal, it means that there is a bijective function that makes from S to ℤ_{2}×ℤ_{2} where they map the same way. This is called an isomorphic relationship. I think I touched on this in my first answer, but didn’t fully explain it. They also have this property where if you add (0,1) and (0,1), you get (0,0), which is similar to taking a contrapositive twice and having it turn the statement back to what it was originally. _{
}

And what the heck is with this Kick Hug thing?

# Homework Struggles

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.

# FOM Book: 4.2

Again, it’s a Friday afternoon, so this is the lightning speed round of some essential 4.2 definitions that struck my fancy so I can be done !

### Contrapositive

If you have a statement *if p(x), then q(x)*,* *the contrapositive is *if ~p(x), then ~q(x).*

So, say we have the statement *if it’s friday, kate is probably crying over all the homework she has for the weekend,* the contrapositive would be *if it’s not friday, then kate is probably not crying over all the homework she has for the weekend. *

Fun fact! They logically mean the same thing.

If we have an implication statement *p(x)⇒q(x)*, the contrapositive is *~p(x)⇒~q(x). *So if we have an implication statement like *kate drinking coffee in class implies a snarky kate, *the contrapositive of this is *kate not drinking coffee in class implies a non-snarky kate. *

**Theorem 4.13:** ~[p(x) and q(x)] is logically equivalent to “~p(x) or ~q(x)”.

**Theorem 4.14:** ~[p(x) or q(x)] is logically equivalent to “~p(x) and ~q(x)”.

### Converse

If you have a statement *if p(x), then q(x)*,* *the converse is *if q(x), then p(x).*

So, say we have the statement *if it’s friday, kate is probably crying over all the homework she has for the weekend,* the converse would be *if kate is crying over all the homework she has for the weekend, then it’s friday.*

If we have an implication statement *p(x)⇒q(x)*, the converse is q*(x)⇒p(x). *So if we have an implication statement like *kate drinking coffee in class implies a snarky kate, *the converse of this is *a snarky kate implies a kate drinking coffee in class.*

# Class Review: Proof by Induction

Wednesday was cool because we went over how to prove by induction, which wasn’t completely overwhelming or anything.

Proving by induction is super simple. First, you have a **base case**, where you prove that the statement in question works at some (preferably small) level. Next, you prove that the statement works for some variable. In class, we used ** k.** After k, work it for

**k+1**too. The proof is concluded by relating k and k+1, so that basically no matter what value you plug in for k, the case will work for that number, and the one after it, and the one after it, into infinity and beyond!

Once we turn our homework in, I’ll post how to prove #9 by induction! It’ll take me 5 minutes to type out, tops. That’s how simple it is.

# FOM Book: 4.1

I think it’s safe to say this has been the weirdest week I’ve had at SMCM in a while. I got the deadly stomach virus, found out I have three exams next week, got accepted into Cal State, Chico for an exchange program, and have to now pick classes at Chico that may or may not transfer back over or count for anything, among other things.

Too much information? Whatever.

ANYWAY, this has also been a weird week for FOM. I missed class on Monday (due to puking), Wednesday was a lot of awkward silence, and Friday was a lot of the same with some group work. I think the one thing I learned this week is that proof by induction is REALLY easy, and that I really need to get back on track with reading the book.

So, it’s almost 4PM on a sunny Friday afternoon, and I’m challenging myself to plug out the essential parts 4.1 that will help me prove things in the future.

### The challenge starts now.

# 4.1 Exploration and Proof with Quantifiers

### Order Can Be Everything

Changing the order of quantifiers can make a true statement false. In the book, they use the statements: (∃c∈ℕ)(∀a,b∈ℕ)(a|c and b|c) and (∀a,b∈ℕ)(∃c∈ℕ)(a|c and b|c). Looking at them, they look the exact same. BUT, (∀a,b∈ℕ)(∃c∈ℕ)(a|c and b|c) is true and (∃c∈ℕ)(∀a,b∈ℕ)(a|c and b|c) is false.

Why?

We can prove that the statement (∀a,b∈ℕ)(∃c∈ℕ)(a|c and b|c) is true by assuming the universal statement is true and finding some a and b that exist to make this true as well. Since we’re trying to prove the existential part, it’s simple because we need to find some instance where the open statement works.

But when we try to prove (∃c∈ℕ)(∀a,b∈ℕ)(a|c and b|c), we are trying to find a c that makes the universal statement true, which is a very subtle difference. When switched around this way, the statement says that every positive integer a and every positive integer b is a divisor of c. When looking at this, no matter what you choose for c, you can find a’s and b’s that are not divisors of c. So we can’t prove this.

### ∀ in the Hypothesis

When ∀ is in the hypothesis, we use the term specialization, which Casey doesn’t like for some reason, so I’ll try and explain this a different way. From what I understand, ∀ in a hypothesis is a huge perk for proving a specific value later, since all values are guaranteed in what we are assuming is true. (This seems rather intuitive).

### ∃ in the Hypothesis

When ∃ is in the hypothesis and conclusion, you use two steps to prove (which is really nice time-wise). ∃ is really just saying that there’s something out there that exists, so first step is name that something that exists, and then use it to prove the statement in question.

This is a *very* short summary of what 4.1 goes over. The rest of the section goes over specific definitions and theorems that use quantifiers in the hypothesis, which I’ll talk about later!

# POW: Awkward Pictures and Theorems and Such

Okay so first of all, this is the most awkward picture I’ve ever taken with anyone ever. I’ve talked to Grace about twice in my life, but she’s taken FOM so we made small talk about that before the picture was taken.

Anyways, my favorite theorem from Calc 1 was Rolle’s Theorem. It’s really intuitive, and basically just states that if you have two points where f(a) = f (b), then at some point, the slope of the tangent line has to be zero, meaning that the line has to change directions to have it hit the same y-point twice. It’s a special case of the Mean Value Theorem.

I don’t really know why it’s my favorite, except the fact that it sounds like Rolo, and I love those candies, and candy in general.

Also, discussing how hard you’ve worked this semester is a pretty awkward question to answer I feel like, just because you almost have to brag about yourself, which I really don’t like doing. I’ll settle with saying I’ve put forth a good amount of effort into this class, and it’s one of the only ones I’ve ever taken where, when I sit down to do work for it, I don’t put a time limit on it. I’ll do FOM for however long it takes. AND obviously the blog is my favorite part.

Have a great break, ya’ll!