Description
Problem 1 (27+1 points)
For each relation on R below, state if the relation is reflexive, irreflexive, transitive, symmetric,
anti-symmetric, and/or asymmetric. Proofs are only required for parts (d), (e), and (f).
(Recall that if R1 and R2 are relations, then R2 ◦ R1 is a relation that contains (x, z) iff there
exists y such that xR1y and yR2z. Also, if A and B are sets, then A ⊕ B is a set containing x iff x
is in exactly one of A, B.)
For each symbol ∗ in {<, ≤, >, ≥, =, 6=}, we let R∗ denote the relation {(x, y) : x ∗ y}. For
example, R< = {(x, y) : x < y}. (a) (3 points) R<. (b) (3 points) R< ⊕ R=. (c) (3 points) R6= ◦ R6=. (d) (6 points) R≤ ◦ R>.
(e) (6 points) R> \ R6=.
(f) (6 points) {(x, y) : x − y ∈ Q}.
Problem 2 (30 points)
Recall that if R is a relation on a set A, then there are six properties of R that we often consider:
reflexivity, irreflexivity, transitivity, symmetry, anti-symmetry, asymmetry. Implement the six corresponding functions that test for these properties in your “hw4.py” file; the skeleton file can be found
on the course website as usual. The details of this problem are again found in the skeleton code.
Problem 3 (18+1 points)
For each function f : A → B below, prove/disprove if f is surjective and/or injective.
(a) (6 points) f(x) = 2x
, A = Z, B = R
+.
(b) (6 points) f(x, y) = x − y, A = Z × Z
+, B = Z.
(c) (6 points) f(x) = (
2 − x if x ≤ 1
1/x otherwise
, A = B = R.
Problem 4 (20+2 points)
Let f and g be functions from a finite set X to itself.
(a) (10+1 points) Prove or disprove: if f ◦ g is bijective, then f and g are both bijective.
(b) (10+1 points) Prove or disprove: if X is infinite, then the statement in part (a) is true.
Problem 5 (15+1 points)
Suppose 170 students are standing in a line, all facing to the right, and each student has a unique
birthday. A subsequence is a subset of students selected from the line; a subsequence is increasing
(decreasing) if each student in the subsequence is older (younger) than the previous student in
the subsequence. Prove that there exists a subsequence of length 14 that is either increasing or
decreasing.
(Recall that a subsequence obeys the original order, but is not necessarily contiguous: (1, 4, 5)
is a subsequence of (1, 6, 4, 5, 3), but (6, 1) is not.)
Problem 6 (20+2 points)
Let R be a relation on Z
+ × Z
+ defined as follows: (a, b)R(c, d) if and only if ad = bc.
(a) (10+1 points) Prove that R is an equivalence relation.
(b) (10+1 points) Define a bijection from the set of equivalences classes induced by R to the set
of positive rationals, and prove that this function is indeed bijective.