Recap/Nostalgia

As per the second to last Monday of the semester, I’m thinking over the past 12 or so weeks, and wondering if I’m any smarter at this math stuff. Casey did say we’d learn how to prove things in his class, but am I there yet?

I’m not going to lie, I really thought I would take this class, and somewhere right in the middle of the semester we’d come up with this universal proof writing formula that could be used for all mathy things, everywhere.

What I’m realizing ties back to the quotes we blogged about at the beginning of the semester (corny I know). Math isn’t all formulas. It requires common sense, and the sense to throw that common sense out the window when necessary (ie thinking about infinity). Math is what you make it, and for me it’s still fun. Here’s what I’ve learned so far:

  • What a hypothesis is. I may have learned about this in all science classes since 3rd grade, but now I finally get it. Really all you need to know about the hypothesis, is that you always assume it true. And if it’s false, your work there is done. (ie if a unicorn runs through the library, I’ll ace college. neither is going to happen, so why worry about it. in math terms, we call it a vacuously true statement).
  • What a conclusion is, and how easy it is to make a proof into proving a very, very small part of a statement. Like with implication statements. You basically assume 75% of the statement is true and just prove the last conclusion. The key here is distinguishing identifying the conclusion and having something be easy to prove. Just because you only have to prove 25% of a statement, doesn’t mean it’s easy.
  • Counterexamples are the holy grail of FOM. Very rare, hard to find, but freaking awesome when found.
  • Implications are straightforward, sometimes. At least you know when you see a little ⇒, you know what you’re dealing with. 
  • Crazy letters can help too. Knowing what ∀ and ∃ mean is usually about 33% of the battle. 
  • Proving sets are equal requires two things: patience, and proving that each is a subset of the other one.
  • Functions are not just functions. If you’re a fan of the good old calculus function, run far way from FOM right now.
  • Injectivity, surjectivity, and bijectivity will help you in ways unimaginable at the beginning of the semester. Just learn what they mean and never forget it. 
  • Sometimes, when you can’t figure out a statement, it helps to turn it around, a lot. (ie converse, contrapositive, etc.)
  • Induction is probably the easiest concept (which isn’t really even that simple). Just think in terms of k, and prove that every other k after that acts the same way. Or, start with k, and prove that all k’s before that are true. Sound good?
  • In the words of Casey Douglas “And when it all comes down to it, all you’re doing is wiggling”. Wiggles are equivalence classes, which are partitions. There is two much notation for all three of these things, so once you understand any of it, stick with one and chug through with it.
  • When you’re proving an equivalence relation, just prove three things: transivity, reflexivity, and symmetry.
  • There are so many different kinds of infinity. Knowing this should make you feel very small (so eat the extra donut if you want to).
  • Just because there are different kinds of infinity, does not mean you can leave infinity be. Match infinite sets up to each other using functions and keep on provin’.
  • Modulo is not spanish for anything, at least not in FOM.
  • And finally, math is only fun when you give yourself time to think about how really awesome it is. 

 

Maybe FOM is making us smarter, even though it feels pretty confusing mostly all of the time. 

Advertisements

FOM Book: 8.1

Cardinality

We’ve just started talking about cardinality in class. The book has some cool things to say about it too!

Definition 8.1: For sets S and T∈U, “S is equivalent to T” (written S = T) means: There exists a bijective function from S to T.

Theorem 8.1: “≈” is an equivalence relation.

Proof: “≈” is reflexive: Identity formula. “≈” is symmetric: Inverse function. “≈” is transitive: g∘f:S→U.

Definition 8.2: For any set S∈U, the cardinality of S (or the cardinal number of S) is the equivalence class S= of S under the relation of set equivalence.

Definition 8.3: For sets S and T, “S≤T” means: There is an injective function from S to T.

Get Your Hands Dirty 1

Prove that if A⊆B, then A≤B.

Assume that A⊆B, which means that all elements in A are included in B. We are trying to prove that A≤B, which means that there is an injective function from A→B. Injective means that every input has a unique output (f(b)=f(a) ⇒ a =b). If all elements of A are included in B,   then all elements in A can be mapped to it’s elements in B. For example, If A = {1,2} and B = {1,2,3,4}, we know that we can always use the identity formula to always map 1 and 2 to themselves, uniquely. This is true for all A subsets of B.

Definition 8.4: For cardinalities κ and λ in C, “κ≤λ” means: For some S∈κ, and T∈λ, S≤T. Put another way, For κ,λ ∈C if κ≤λ, and U∈κ and V∈λ, then U≤V.

From what I understand in this definition, if you’re talking about two sets in (which is the set of all partitions on some other set), in which there exists a one-to-one function between the both of them (which means f(a)=f(b)⇒a=b), any sets on those two sets with that relationship are also guaranteed to have a one-to-one relationship between them as well (as long as you’re talking about two sets from two different partitions). This makes sense intuitively. Just think about sock and shoes. Take the pair of TOMS I’m wearing right now. It’s the set of shoes I’m wearing right now, but I can also partition it into right and left shoes. They share a one-to-one relationship, because I can still pair them up with only each other. Now, if I was wearing socks with my TOMs, (which would be weird), they are an element of my shoes, and I can match them up as well, one-to-one.

Theorem 8.3 – The Cantor-Schroeder-Bernstein Theorem: If and T are sets such that S≤T and T≤S, then S≈T.

Put another way, if κ and λ are cardinalities such that κ≤λ and λ≤κ, then κ = λ.

This reminds me of what we used when trying to prove that two sets equaled each other. To do that, we had to find that one was a subset to the other, and vice versa. Only here, we’re assuming that there is an injective function from one to the other and vice versa, which means that they share an equivalence relation.

Theorem 8.5: For m,n ∈ W, if m≠n, then N[1,m]  N[1,n] and =N[1,m]≠=N[1,n].

Definition 8.5: For a set S,

“S is finite” means: (∃ t∈W)(=S = =N[1,t]).

“S is infinite“ means: S is not finite.
Definition 8.6: For a finite set S, |S| is the (unique) whole number t such that =S = =N[1,t]. 
Theorem 8.7: ℕ≈ℤ.
Proof:
Define g:ℕ→ℤ as follows:
g(x) =
(x-1)/2 if x is odd.
-x/2 if x is even.
Theorem 8.8: ℤ≈ℚ.
Corollary 8.9: ℕ≈ℚ.
Definition 8.7: For a set S, “S is countably infinite” (or denumerable) means: S≈ℕ.
Definition 8.8: For a set S, “S is countable” means: S is finite or countably infinite. A set which is not countable is called uncountable.
Theorem 8.10: ℝ is uncountable. (proven by contradiction)
Theorem 8.12: If S is any set, then =S < =P(S).
Corollary 8.13: P(ℕ) is uncountable.
Theorem 8.14: ℝ≈P(ℕ). To go ahead and prove it, the book uses the inequality ℝ≤P(ℚ)≤P(ℕ)≤ℝ.
It’s weird, because apparently there are different kinds of infinities, but certain sets, and power sets, are the same kind of infinity somehow. I feel like this could only be thought upon in a dark room somewhere with no outside influence for years, to be able to finally prove some kind of infinity is exactly like another.
The Set of All Sets. 
Consider the set “S∉S“, with the truth set T, T = {S∈U: S∉S}.
There are two options. T is in it’s own truth set, in which case, T∉T is true, or T is not in the truth set, which means that “T∉T” and so is T∈T. Which means that T∈T if and only if T∉T. Which just seems wrong on all sorts of levels. 
This breaks math, which means, obviously, that S does not exist, at least not as a set. Group theory people call S with these characteristics a “class”.
In other news, hope everyone had fun at World Carnival, cause it was the bomb.com.
Now this is my only problem in finishing up the semester.

Infinity – It’s weird

We started talking about infinity today. Usually when I think of infinity, I just think of the general, “not stopping idea”, and leave it at that. What else is there to say about infinity? It goes on forever, and that’s it.

Yeah, I was really wrong.

We began by defining cardinality, which I also hadn’t really thought in depth about. Cardinality, apparently, can only be used when comparing sets; it doesn’t make sense to use cardinality to describe one set. That’s like saying “I’m taller than.” Taller than what? It’s an incomplete thought.

We defined cardinality in terms of an equivalence relation (I’m pretty sure Casey is obsessed with them at this point, just saying), by saying that:

A~B if |A| = |B|, which means that there is a bijective function from A to B.

We tested the three properties of ~, so this really is an equivalence relation.

  • Reflexive: f(n) = n
  • Symmetric: inverse property (If f:A→B exists, then f:B→A exists)
  • Transitive: composition property (If f:A→B, and g:B→C, then g∘f: A→B→C)

We all agreed that with finite sets, their cardinality is equal if they have the same amount of elements.

Then Casey brought up infinite sets, and that’s when things got weird. We can prove that sets that are intuitively not equal, are equal. Like |ℤ| = |2ℤ|. It’s true, because there’s a bijective function between these two sets that maps from ℤ to 2ℤ: f(n) = 2n.

Freaky stuff.

We also settled on the concept of uncountable, which I still can’t believe. Apparently, the natural numbers are countable, even though it is an infinite set.

But get this. The real numbers, they are uncountable. This infinite set is so big, that even the set of real numbers between (0,1) is uncountable.

There are different kinds of infinity.

What.

Kickin’ it with Partitions and Such

We started Monday’s class off with talking about the final, which is going to be a scavenger hunt.

Then Casey picked people (let them volunteer) for the POW Kick Hug Challenge, and I didn’t have to do it!

But then I had to watch other people do it, which would affect my grade on it.

But then we totally won and we all got perfects on it (wasn’t even surprised).

But after that adventure, we had to go back inside and think about FOMy things.

But it’s all good, partitions are pretty cool.

We talked about how you can go back and forth from partitions to equivalence relations as long as you know one of them to start out with. It’s really all about using different notations and knowing what they mean.

In the book they use this fancy C looking thing, but I’ll just use C. This C thing is the set of all subsets that S is partitioned into. So, when you’re thinking about say, M&Ms. If you split them up by color to eat them (weird, why would you do that, but no judgement), C would then be all the sets of colors you have split them into.

We then started talking about the other confusing notation in the book, and related it to concepts we’d already learned about.

Ct= {z ∈ S: z~t} = [t] (the set of equivalence classes that in a given set S)

x~y= (∃ u∈C)(x,y∈U) (~c  is always transitive, symmetric and reflexive)

Welp. That’s it.

FOM Book: 6.1 (Partitions & Equivalence Relations)

We’ve been talking about this topic for a while in FOM, so I guess it’s about time to read about it in the book and put some formal definitions out there.

Definition 6.12: For a set, A, a partition of A is a set C of subsets of A (i.e. C ⊆ P(A)) such that:

a) (∀x∈A)(∃U∈C)(x∈C)

b) (∀U∈C)(U ≠ ∅)

c) (∀U,V ∈ C)(U∩V≠∅ ⇒ U = V)

In real life words, this basically means that, based on the a) property, every element in A falls into some set C that A is split into. (Think of one of those little kid plates that have the different sections for foods. A = the whole plate, and every element of food of going to end up in some section of the plate, the sections being the C subsets)

According to the b) property, no partitions of a set are the empty set. (It wouldn’t make sense for a kid’s plate to have an food slot that doesn’t technically exist..). This property just works to avoid any unneccesary complications using an empty set, becuase it adds nothing of important to a partition set.

And the last property just talks about the relationship between U and V as partitions. Using the kid’s plate example again, the c) property states that if you’re looking at two food slots and they have some type of food in common, you’re really only thinking of one food slot. 

When combining a) and c), we can say that each element of A belongs to exactly one of the parts of the partition. It’s also helpful to mention that: U,V⊆A. It’s intuitive in the kid’s plate example, because the slots are what make up the plate.

Definition 6.14: For a set A, an equivalence relation on A is a relation on A which is reflexive, symmetric, and transitive.

Class Problems ⇒ Class Equivalencies

We pretty much spent most of class trying to wrap our heads around this Kick/Hug thing, which is detailed way more clearly than I could ever explain it in Matt’s blog post, then started working on a new worksheet based around equivalence classes.

Here’s #4:

Consider the set S = Prove or disprove x~y ⇔ xy is odd is an equivalence relation on ℝ.

To be an equivalence relation, you must follow the following conditions:

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

If we assume that xy is odd and try to prove that x~y, all reals must relate to themselves in some way. But if xy is odd, even numbers cannot be represented, so this cannot be an equivalence relation, because it is not reflexive.

And #2:

Let S be any set. Prove that equality is an equivalence relation; i.e. that a~b⇔a=b is an equivalence relation.

We’ll assume that a~b⇔a=b is true, and that we’re trying to prove that this equality follows these features:

  • Reflective: (∀a∈S)(a~a)
  • Symmetric: (∀a,b∈S)(a~b ⇒ b~a)
  • Transitive: (∀a,b,c∈S)(a~b + b~c ⇒ a~c)

Which means we’ll try to prove that a=b is reflective, symmetric, and transitive. If a = b, then this can be symmetric, because the order does not matter if a = b. A can also be related to itself because b is the same element. a = b is also transitive, because b~c can be changed to a~c by substitution. Therefore, a=b is an equivalence relation.

I’m confused

I am still a little confused on how to prove equivalence relations, and how ⇔ statements work and are proved. Equivalence relations seem pretty simple to prove, as there are three factors that go into making something an ER, but how do you prove something can wiggle itself? How do you prove something is transitive if only two elements are defined (like in #2)?

How do you go about proving ⇔ statement without getting confused?

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.

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<2n. This can be rephrased in quantifier notation as (∀n∈ℕ)(n<2n). 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<2n.

Proof: Let p(n) be the open statement n<2n (for the universe = ℕ).
We will have to show that: 1∈P, and that P is inductive.
First we need to prove the base case; we’ll use one.
p(1) < 21. This statement is true, so 1∈P.
Next we need to show that P is inductive. To do that, we assume p(t) is true. We need to prove p(t+1) < 2t+1 is true.
Since t∈ℕ, 1≤t.
t+1≤2t.
t∈P, so t<2t. 
If we multiple both sides by two, we get 2t < 2 × 2t.
2×2t = 2(t+1)
t+1≤2t<2(t+1)
t+1<2(t+1).
Theorem 5.3: For any n∈ℕ,

13+ 23+ 33+…+ n3 = ((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)²≤2n.

Proof: Let p(n) = (n+1)²≤2n for universe ℕ[6,∞], and let P be it’s truth set.
P = {n∈ℕ[6,∞]: (n+1)²≤2n}
We need to prove that 6∈P, and that P is inductive.
 (6+1)²≤2which is true.
Assume (t+1)²≤ 2t ,we need to prove that ((t+1)+1)² ≤ 2× 21, which simplifies to (t+2)² ≤ 2× 21. 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× 21 = 2(t+1), which, simplified is what we are trying to prove.

(t+2)² ≤ 2(t+1).
Theorem 5.9′: for any n∈W. If |A| = n, then |P(A)| = 2n. 

This weekend I’m going to try and figure out a way to prove Theorem 5.9′ this weekend that isn’t as confusing as the book does it.
Happy Easter  (or regular) weekend ya’ll!