Finiteness

Return to List of Lectures

Previous Lecture

Misc

Problem Set 11 Solution

Problem set 11 solutions are now available in PDF and LaTeX through Canvas (see the “Solutions” folder under “Files,” or just click on the preceding links).

SOFIs

SOFIs have started, you can fill them out through Knightweb.

Please do fill one out for this course, I do read them and they are helpful to me in improving future offerings.

Questions?

Finiteness

Section 9.1

Equivalence

Prove Theorem 9.1 (that ≈ is reflexive, symmetric, and transitive).

Relevant ideas or questions from the reading.

• You’ll need the definitions of reflexive, symmetric, transitive.
• The definition of ≈: A ≈ B if and only if there is a bijection from A to B
• ℕ_k is a “standard set” of size (aka cardinality) k, ℕ_k = { 1, 2, ..., k }

Proof.

• ≈ is reflexive, i.e., for any set A, A ≈ A because f : A → A defined as f = { (x,x) | x ∈ A }, i.e., f(x) = x, is a bijection.
• ≈ is symmetric. If A ≈ B, there is a function f : A → B that is a bijection. Therefore f^-1 : B → A is also a bijection, and so B ≈ A.
• ≈ is transitive. Given sets A, B, C with A ≈ B and B ≈ C, show A ≈ C. Since A ≈ B there exists a bijection f : A → B, similarly there is bijection g : B → C. By theorem 6.20 g ○ f is a bjiection from A to C.

Comments:

• The notion that sets have the same cardinality if and only if there is a bijection between them is the basis for comparing cardinalities of finite and infinite sets.
• The properties proven here are helpful. Transitivity in particular frees you from having to use ℕ_k in every finiteness proof, instead you can prove that A ≈ B for any set B that you already know to be finite.

Finiteness

For each natural number n, let S_n = { x ∈ ℤ | -n ≤ x ≤ n }. Prove that S_n is finite for all natural numbers n.

Relevant ideas or questions from the reading:

• Pigeonhole principle: m pigeons can’t fit one per hole in n pigeonholes if m > n. This is an interesting principle, but not terribly helpful here.
• To prove finiteness, show a bijection from S_n to ∅ or one of the ℕ_k.

Proof:

• Let f : S_n → ℕ_2n+1 be defined by f = { (-n,1), (-n+1,2), ..., (n,2n+1) }, i.e., f(x) = x + n + 1, or f = { (x,x+n+1) | x in S_n }. This is a bijection, so S_n ≈ℕ_2n+1 and so is finite.

Comments:

• A set is finite if and only if it is equivalent to (i.e., has a bijection to) ∅ or one of the ℕ_k.
  
• You can prove finiteness just by finding a bijection.

Overall Comments

Having a bijection between two sets means they are “equivalent,” specifically that they have the same cardinality (i.e., size, for finite sets).

The sets ∅ and ℕ_k = { 1, 2, 3, ..., k } are “reference” finite sets of cardinality 0 (for ∅) and k (for.ℕ_k)

A set is finite if and only if it is equivalent to another finite set, ultimately meaning equivalent to ∅ or one of the ℕ_k.

Next

Countable sets.

Read textbook section 9.2

Next Lecture