# 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 *C *(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 *S *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]}).

**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:*

**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(ℕ)≤ℝ.

**The Set of All Sets.**

*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.*