Equivalent Cardinalities

Return to Course Outline

Previous Lecture

End-of-Semester Announcements

Class schedule for next week:

• Monday (May 10) is an “honorary Tuesday,” i.e., classes meet according to the Tuesday schedule. We don’t have class.
• Tuesday (May 11) is an honorary Wednesday. We do have class, at the usual time and place (12:30, Welles 140).
• Wednesday (May 12) is an honorary Thursday. We don’t have class.

SOFIs are currently under way. I do read and consider what you have to say; it has been valuable in the past in affecting what I do (e.g., individual meetings for grading) or don’t (e.g., daily use of a “random names” list) do in classes. So please fill out a SOFI for this class, it might have on impact on future classes you or friends take from me.

Anything You Want to Talk About?

Quantifiers and Set Operations

Problem set 10, question 2, about using quantifiers to express what a union or intersection over the members of a family of sets means.

I suggest first describing in words how you would determine whether a value is a member of such a union or intersection. For example…

So informally, x being in a union means that some set contains x. “Some” corresponds to an existential (“there exists”) quantifier, so using quantifiers you could say…

You do not need to write formal proofs for this question.

Inverse Functions

Problem set 10, question 4.

This question asks you to think about whether the inverse of an apparent function satisfies the requirements for being a function, i.e., that it maps each input value (i.e., domain value) to exactly one value in the range.

For instance, the first example is f(x) = 2, so its inverse has to “map” 2 to every real number. That’s clearly not “exactly one value,” so the inverse in this part is not a function.

If you like to think about the inverse graphically, you can use the vertical line test, i.e., does every vertical line drawn up and down from the x axis intersect the graph of the inverse in exactly one place? For instance, this looks like so for the second function in the problem set, whose inverse is g^-1(y) = y/2:

You can even take a shortcut here, and realize that taking a function’s inverse swaps the roles of horizontal and vertical axes in graphs, so just using a horizontal line test on the original function (i.e., does every horizontal line drawn left and right from the y axis intersect the plot at exactly one point) will also tell you whether the inverse is a function:

Equivalence of Cardinalities

Based on section 9.1 of the textbook and this equivalent cardinalities discussion.

A Finite Example

How would you show that the sets {1, 2, 4, 8, 16} and {a, e, i, o, u} have the same cardinality, without explicitly counting?

Show that you can pair each element of the first set with an element of the second set.

Formally, such a pairing is a bijection between the sets, i.e., it maps each element of the first set to at most 1 element of the second (it’s a function), it never “reuses” a member of the second set to pair with more than 1 element of the first (it’s an injection), and it doesn’t leave any elements of the second set out (it’s a surjection).

Using this idea to show that small finite sets have the same cardinality is far more complicated than the problem needs, but using it on infinite sets in invaluable. For example…

…An Infinite Example

(From the discussion.)

Show that the set of perfect squares (i.e., the set of integers that are squares of other integers, S = {0, 1, 4, 9, 16, ...}) has the same cardinality as the set of non-negative integers, ℤ*.

Intuitively, we need to line up the perfect squares and non-negative integers so that each of the former is lined up beside one of the latter:

Looking at this line-up, we notice that it matches non-negative integer n with perfect square n². So if we can show that f(n) = n² is a bijection from non-negative integers to perfect squares, we’ll have shown that the two sets have equivalent cardinalities. And it is a bijection, since for any 2 non-negative integers a and b, a² = b² only if a = b, and every perfect square x is the image of some non-negative integer (since if x is a perfect square, than x = n² for some non-negative integer n, i.e., x is the image of n).

Next

A first application of set equivalence to infinite sets: countable sets.

Please read “Beginning Activity 1 (Introduction to Infinite Sets),” “Beginning Activity 2 (A Function from ℕ to ℤ),” “Infinite Sets,” and “Countably Infinite Sets” in section 9.2 in the textbook.

Please also contribute to this discussion of countably infinite sets (or motels) — at least look at the discussion, it’s a fun way of thinking about issues connected with countable sets.

Next Lecture