Countable Sets

Return to List of Lectures

Previous Lecture

Misc

GROW STEM

Speaker Thursday (April 27), 5:15, Newton 214

Prof. Reginald Byron, Southwestern University and Geneseo alum

“Implicit Bias, Microaggressions, and the March Toward More Inclusive Pedagogies”

SOFIs

You get paid for doing SOFIs (in the form of $1/SOFI added to your printing balance).

Thank you to anyone who has already filled out the SOFI for this course.

Questions?

Countable Sets

Section 9.2

Infinite Sets

Progress check 9.11 parts 1 and 3 (prove that ℤ, ℚ, and ℝ are infinite; prove that E⁺, the set of even natural numbers, is infinite).

Relevant ideas or questions from reading:

• Definition of infinite set: if set A is equivalent to one its proper subsets, then A is infinite. For example, the set of natural numbers, the open interval (0,1).
• A countably infinite set is a set with cardinality ℵ_0, e.g., card(ℕ) = ℵ₀.
• The book gives, or at least outlines, proofs that various sets of numbers are countably infinite, e.g., the integers, the positive rationals, the rationals.
• Theorem: every subset of a countable set is countable.
• If infinite set A is a subset of B, then B is infinite.

Solutions:

• E⁺ is an infinite set: consider f : ℕ → E⁺ defined by f(n) = 2n. So E⁺ is equivalent to ℕ, i.e., E⁺ is infinite.
• ℤ is infinite: Problem set 12 problem 3 has a bijection from ℕ to ℤ.
• ℕ is a subset of ℚ, and of ℝ, so ℚ and ℝare infinite.

Comments:

• An infinite set is simply one that’s not finite.
• There are a number of ways to prove that a set is infinite, including proving that it’s equivalent to one of its proper subsets, proving that it’s equivalent to a set already known to be infinite, or proving that one of its subsets is infinite.
• Recognizing infinite sets is prerequisite to talking about different kinds of infinite set.

Countable Sets

Progress check 9.12 part 3 (prove that the set of natural numbers that are perfect squares is countably infinite).

Relevant ideas or questions from the reading:

• What’s the difference between countably infinite and uncountable?
  • Countably infinite means there’s a bijection to or from the naturals. This in turn means you can talk about a 1st member, a 2nd member, etc. If a set isn’t countable it doesn’t make sense to enumerate its elements this way. But note that we don’t officially know whether there are such things as uncountable sets yet.
• The reading has lots of different examples of proofs that something is countably infinite, but it isn’t clear how to apply them.
  
  • The common strategy in most of those examples is to find a bijection to/from the naturals. Even the diagram in the proof that the set of positive rationals is countably infinite is showing how to order the positive rationals so there’s a first one, a second one, etc., i.e., how to visually construct the bijection to the naturals.

Solutions:

• Here’s a bijection from ℕ to the perfect squares: f(n) = n².

Comments:

• Showing a bijection from a set to the naturals or vice versa is the fundamental way of proving that that set is countably infinite.

The countably infinite hotel

Imagine that you own a hotel, a very special hotel with a countably infinite number of rooms. On the one hand, this is nice because you never run out of space no matter how many guests you have, but on the other hand it gets a bit depressing at times, because the hotel is always nearly empty. But one day luck strikes: a countably infinite tour bus pulls up, loaded with a countably infinite number of tourists looking for a place to stay. For the first time ever, the Countably Infinite Hotel is full! But then... disaster! The Countably Infinite Political Party’s convention comes to town, with a countably infinite number of delegates wanting room in the Hotel. What can you do?

• This sounds a lot like the book’s theorem that the union of 2 countably infinite sets is countably infinite — you should have enough room to house the union of the countably infinite set of tourists and the countably infinite set of politicians.
• And in fact, you can borrow an idea from the proof of that theorem: move all the tourists to even numbered rooms, and put the politicians in the odd numbered rooms.

Comments:

• This is an important example of how infinite cardinalities behave differently from finite numbers, and why I think it’s best to think of “infinity” as not really being a number.

Next

Cross products of countably infinite sets.

Uncountably infinite sets.

Read textbook section 9.3

Next Lecture