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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s