EECS 203: Discrete Mathematics
Fall 2024
Homework 4
Definition Reminders
• R is the set of real numbers, R
+ is the set of positive real numbers (which does not include 0), Z is the set of integers, Z
+ is the set of positive integers, N is the set of natural numbers (same as Z
+ ∪ {0}).
• For real numbers a and b with a ≤ b, we write [a, b] for the interval of all real numbers between a and b, including a and b themselves. We write (a, b) for the same interval, but not including a or b. We can also mix these brackets, e.g., [a, b) is the interval including a, but not including b.
• Given a set X, the power set of X, denoted P(X), is the set of all subsets of X.
• A function f : X → Y is onto if for all y ∈ Y , there exists x ∈ X with f(x) = y. It is one-to-one if for all x1, x2 ∈ X, if f(x1) = f(x2), then x1 = x2. It is a bijection if it is both onto and one-to-one.
• A set X is countable if |X| ≤ |N|.
• The floor of a real number x, written ⌊x⌋, is the largest integer that is less than or equal to x. For example, ⌊0.5⌋ = 0, ⌊203⌋ = 203, ⌊−1.1⌋ = −2.
• The notation for a function defined piecewise is an open bracket with a specification of each part at the end of the line. For example, the function f : Z → Z that doubles even integers and triples odd integers would be written
Legal Assumptions
• The sets Z, Z+, Z+ × Z+, N, Q are countable. The sets [0, 1], R, R+ are uncountable. Any other sets proved countable/uncountable in lecture may be assumed without re-proof.
• Between any two distinct real numbers, there exists a rational number.
Mechanical Problems
1. Functions are Fun(ctions) [16 points]
For each of the following functions, prove or disprove (i) that it is onto and (ii) that it is one-to-one.
(a) f : R → R, f(x) = x2
(b) f : R+ → R+, f(x) = x/1
(c) f : R → Z, f(x) = ⌊x + 7⌋
(d) f : Z → R, f(x) = ⌊x + 7⌋
2. Absolute Units [16 points]
For each of the following sets A, prove that |A| = |[0, 1]| by defining explicit function(s) between A and [0, 1]. State the relevant properties that your function(s) satisfy (one-to-one, onto, or bijective), but you do not need to prove or justify these properties.
(a) A = [−1, 2]
(b) A = [1, 2] ∪ [3, 4]
(c) A = (0, 1)
(d) A = R
3. A More Perfect Union [12 points]
Prove that for all countable sets X and Y , X ∪ Y is countable.
Note: A correct proof must construct function(s) between X ∪ Y and some set known to be countable, state whatever properties of these function(s) are needed to show that X ∪ Y is countable, and then prove these properties.
4. Trend Lines [8 points]
A function f : R → R is strictly increasing if for all x, y ∈ R with x < y, we have f(x) < f(y).
A function f : R → R is strictly decreasing if for all x, y ∈ R with x < y, we have f(x) > f(y).
(a) Prove or disprove: Every function f : R → R that is a bijection is either strictly increasing or strictly decreasing.
(b) Prove or disprove: Every function f : R → R that is either strictly increasing or strictly decreasing is a bijection.
In either part, if you name a specific function f, you may state its properties (i.e., whether or not it is strictly increasing, strictly decreasing, one-to-one, onto, or a bijection) without proving or justifying them.
Bad Proofs
Each of the following propositions may or may not be true, but we have given an incorrect “proof” that attempts to show that it is true. Identify the specific logical error made in each proof by citing a sentence, equation, step, or missing part of the argument, and briefly explain why it is wrong.
5. All For One And One For All [8 points]
Proposition. The function f : Z → Z, f(x) = x2 − x is one-to-one.
Incorrect Proof. Let a, b ∈ Z with f(a) = f(b). We have:
f(a) = f(b) assumed
a2 − a = b
2 − b definition of f
a2 − a + ab = b
2 − b + ab add ab to both sides
a(a − 1 + b) = b(b − 1 + a). factor each side
In order to prove that f is one-to-one, we need to prove that a = b. Then since a = b, a + b is even, so a + b − 1 is odd, so a + b − 1 ≠ 0 (since 0 is even). Thus we can safely divide a + b − 1 from each side, leaving us with a = b, which completes the proof.
6. Law and Order [8 points]
Proposition. The set [0, 1) is countable.
Incorrect Proof. First, we define a new way to put the elements of [0, 1) in order (different from the usual ordering <, by value). We will call our new ordering ≺. Given a, b ∈ [0, 1), we order a ≺ b if:
• a can be written with fewer decimal places than b, or
• a and b use the same number of decimal places (possibly both infinity), and if we look at the first decimal position on which a and b are different, the digit for a is less than the digit for b.
Notice that any two elements in [0, 1) can be compared by ≺; that is, we have either a ≺ b or b ≺ a. Thus the elements of [0, 1) are completely ordered by ≺.
Now let f : N → [0, 1) be the function where f(i) is the i
th element in [0, 1), under the ordering ≺. For example, the leading values of f are:
f(0) = 0, f(1) = 0.1, f(2) = 0.2, f(3) = 0.3 . . .
f(9) = 0.9, f(10) = 0.01, f(11) = 0.02, f(12) = 0.03 . . .
f(18) = 0.09, f(19) = 0.11, f(20) = 0.12, f(21) = 0.13 . . .
f(27) = 0.19, f(28) = 0.21, f(29) = 0.22, f(30) = 0.23 . . .
As previously discussed, the elements of [0, 1) are completely ordered by ≺, and thus every element in [0, 1) is eventually mapped to by f since it will eventually appear in the ordering. So f is an onto function, which means |N| ≥ |[0, 1)|, and so |[0, 1)| is countable.
Discovery Problems
7. Sydney’s Sorting [16 points]
Given a deck D of cards stacked on top of each other, a cut is formed by splitting the deck into two nonempty parts D1, D2, where all the cards in D1 are stacked above all the cards in D2.
Sydney has an infinitely large deck of cards, where the cards are labeled with all possible pairs of positive integers (x, y), and no two cards have the same label.
(a) Sydney sorts the deck such that cards with a smaller value of x · y are stacked above cards with a larger value of x · y (with ties broken arbitrarily). Are there countably or uncountably many ways for Sydney to cut the deck? Prove your answer.
(b) Sydney re-sorts the deck such that cards with a smaller value of x/y are stacked above cards with a larger value of x/y (with ties broken arbitrarily). Are there countably or uncountably many ways for Sydney to cut the deck? Prove your answer.
Hints: Your proofs should define a function f that relates the set of all possible cuts to a set that you already know to be countable/uncountable. You should prove any properties that you claim f to have. It is not a logically correct solution to say that the deck itself is countable, and therefore there are countably many cuts.
8. Magic Makers [16 points]
A maker game is a type of two-player game defined by a set U called the universe, and a set W ⊆ P(U) whose elements are called the winning sets. The players take turns claiming the elements of U. A player wins as soon as they have all the elements of any winning set, and the game ends in a tie if all the elements of U are claimed with neither player having all the elements of a winning set. For example, Tic-Tac-Toe is a maker game, where U is the set of nine squares and the winning sets are each subset of three squares in a row.
(a) What does it mean for two different maker games to be “the same” (up to renaming of universe elements)? When mathematicians say two objects are “the same,” they say the objects are isomorphic. Formalize this notion for maker games by completing the definition with a precise logical statement:
Definition 1. Two maker games (U1, W1) and (U2, W2) are isomorphic if there exists a function f : U1 → U2 such that .
It may simplify your solution to use image notation: in particular, for a set w ∈ W1, you may write f(w) as a shorthand for the set {f(u) | u ∈ w}.
(b) Twelve is another example of a maker game, where the universe is the integers U = {0, 1, 2, . . . , 8}, and the winning sets are any subset of exactly three integers from U whose sum is 12. Show that Twelve is isomorphic to Tic-Tac-Toe by describing a function and briefly explaining how it fits your definition from the previous part.