SUNY Geneseo Department of Mathematics
Tuesday, May 11
Math 239 03
Spring 2021
Prof. Doug Baldwin
Can we talk about how to get started on the questions in problem set 11?
Since f is a bijection, f-1 is a function. What is (f-1)-1? It’s f, which is a function. But that means f-1 must be a bijection, since a function’s inverse is a function if and only if the function is a bijection (Theorem 6.25).
See if the given function, f, is an injection.
“Injection” means one-to-one, i.e., every element of the domain has a unique element in the codomain. Commonly checked by showing that f(a) = f(b) implies a = b. So see if you can show this by plugging variables a and b into the definition of f, setting the resulting expressions equal to each other, and seeing if you can then show that a = b.
Some helpful thoughts for dealing with the (-1)n term in f:
(-1)n is negative if and only if n is odd, and positive if and only if n is even.
So if n is odd, the numerator in f becomes 1 - (2n-1) = 1 - 2n + 1 = 2 - 2n, which is less than or equal to 0 for all natural numbers n.
If n is even, the numerator becomes 1 + (2n - 1) = 2n > 0 for all natural numbers n.
Use these ideas to deal with (-1)n in the injection proof.
Then see if f is a surjection.
Surjection means “onto,” i.e., every element of the codomain is the image of some element of the domain.
So assume x is an arbitrary integer, and show that there’s some natural n such that f(n) = x.
The relationship between n being odd or even and the sign of f(n) will be helpful again.
Being an equivalence relation means a relation is reflexive, symmetric, and transitive. So to show that ~ is an equivalence relation, show that it has these 3 properties.
Reflexive: Let n be an integer, show that n ~ n, i.e., 2 divides n+n, i.e., n+n = 2k for some integer k. But n+n = 2n which is 2 times an integer, i.e., k = n.
Symmetric: Show that if a ~ b then b ~ a.
Transitive: Show that if a ~ b and b ~ c, then a ~ c.
“The equivalence class of 1” means the numbers equivalent to 1, i.e., n such that n + 1 is divisible by 2. But you don’t have to do this as part of proving that ~ is an equivalence relation, it’s a separate question.
Once again, check to see if the given relation is reflexive, symmetric, and transitive. But you don’t need a formal proof in this question.
Based on the first part of section 9.3 in the textbook and this “dodge ball” discussion.
Try playing it.
Here’s a sketch of a game we played, where empty squares indicate places where the chosen symbols didn’t really matter.
Red can always win, by picking as the symbol for box i the opposite of the symbol Blue picked for box i in row i. (In fact, whichever team goes first can win: if Blue goes first, they should match Red’s choice for boxes 1 through i in row i.)
What does “dodge ball” have to do with the real numbers?
Suppose someone claims that there are a countably infinite number of real numbers between 0 and 1, and a dodge ball expert wants to show otherwise.
If this set of reals is countably infinite, we can assign each real a natural number, and then write down the reals in order of the assigned naturals, i.e., n1, n2, n3, etc. Each number in this list can be written as a countably infinite sequence of digits. So the list of real numbers looks like a table of digits, like so:
Now a dodge ball expert can create a real number that isn’t anywhere in the list, by picking digits that differ from the digits in the list. Specifically, pick a first digit that’s different from the first digit of the first number, a second digit that’s different from the second digit of the second number, and so forth. Just as this is a winning strategy for Red in dodge ball, it’s also a strategy that will produce the decimal representation of a real number that can’t appear anywhere in the list:
This is sometimes called a “diagonalization” or “diagonal” argument, because it focuses on digits along the diagonal of the table in order to create a number different from every number in the table.
(No Next Lecture)