Infinite Cardinalities

Question 1

Are there more students in a room, or more chairs? How do you know?

Show a function

Answer 1

Question 2

How to show that a function is injective from A to B?

Answer 2

Cardinality from A to B if A>B is injective

Georg Cantor (1845 - 1918) Generalized observation to sets (infinite and finite)

Question 3

Two sets A and B have equal cardinality iff: …

Schroder-Bernstein Theorem

Answer 3

|A| </ |B| and |B| </ |A|

By the Schroder-Bernstein Theorem - there is a bijective function between A and B.

Question 4

What is the Schroder-Bernstein Theorem?

Answer 4

Two sets A and B are said to have equal cardinality iff |A| ≤ |B| and |B| ≤ |A|

There is a bijective function between A and B, so that A > B and B > A.

Thus, A and B are “equipollent” written A ∿ B

Question 5

Definition of a set which has finite or countable infinite cardinality:

Answer 5

1. Set is finite if it is equinumerous with a set {1, 2 …, n} for some number n
2. Set is countably infinite if it equinumerous to N [Has a cardinality ℵ0]

Set is countable or denumerable if it is finite or countably infinite
Therefore, enumerable if infinite

Question 6

Of which number is there more?

Answer 6

E, N, Z, Q can all be mapped onto the natural numbers, so they have a cardinality of ℵ0, so |N| = |E|

Question 7

Show that |N| = |E|:

Show that |N| = |E|:

Answer 7

f(x) = 2x is a bijective function

Question 8

Show that |N| ≤ |Z|:

Show that |N| ≤ |Z|:

Answer 8

f(x)=x is an injective function from N to Z

Question 9

Show that |Z| ≤ |N|:

Answer 9

Find a function such that |Z| = |N|

Question 10

Can we find a bijection between N and Q?

Answer 10

Matching rational number to infinity to N (skip doubles)

Question 11

What is Cardinal Arithmetic?

Answer 11

ℵ0 + 1 = ℵ0 + ℵ0 = ℵ0

Ex: Hilbert’s Hotel

Question 12

How do you show the impossible?

Answer 12

Indirect Proof: Assume it, and derive a contradiction

Question 13

What is a proof for Diagonalization:

Answer 13

1. Assumption
2. Define bijection (contradiction)
3. Table
4. Construct new element
5. Construct element should/cannot be in table
6. Cannot be in table = contradiction
7. Conclusion

Used to show that ℝ is enumerable

Question 14

What is Cantor’s Theorem?

Answer 14

|ℙ(A)| > A
The Cardinality of a power set > set itself

Ex: |ℕ| < |ℙ(ℕ)|

How to prove? Assume |ℙ(A)| = A and derive a contradicition

Question 15

What is the Continuum Hypothesis?

Answer 15

|ℝ| = ℵ1

Question 16

What sets are uncountable?

Answer 16

1. Powerset of ℕ(the set of all subsets of ℕ)
2. Set of function from ℕ to ℕ
3. Real numbers

Question 17

Homework 01

Show that the cardinality of A ⋃ {a} is still ℵ0

Answer 17

To prove this we need to find a bijection from ℕ to A ⋃ {a}.

Since A is countably infinite, there must be a bijection f from ℕ to A. Now, define a bijection g from ℕ to A ⋃ {a} as follows: g(0) = a and g(n) = f(n-1) for all n ∈ ℕ

Question 18

Homework 1

Show that the cardinality of A⋃B is still ℵ0

Answer 18

Question 19

Homework 02

Answer 19

Question 20

Homework 02

Answer 20