Problem 1: Define f:R x R → R x R by f ((x, y)) = (x + 3,4 - y) for each (x, y) ∈ R x R.
(a) Is f one-to-one? Prove or give a counter-example.
(b) Is f onto? Prove or give a counter-example.
(c) Is f a bijection? If so, find f-1.
(d) Find f 0 f.
Problem 2. Define g : Z+ x Z+ → Z+ by g((m,n)) = 3m9n for each (m, n) ∈ Z+ x Z+.
(a) Is g one-to-one? Prove or give a counter-example.
(b) Is g onto? Prove or give a counter-example.
Problem 3. Let 5Z be the set of all integers that are multiples of 5, so
5Z = {..., -15, -10, -5,0,5,10,15, ...}.
Prove that 5Z is countable.
Problem 4. For each of the following relations, determine whether the relation is: (1) reflexive; (ii) symmetric; (iii) transitive; (iv) anti-symmetric.
For each property either prove that the property holds or give a counter-example (or reason) demonstrating that the property does not hold.
(a) Define a relation R1 on the set of integers as follows: ∀m, n ∈ Z, (m, n) ∈ R1 if and only if every prime factor of m is a prime factor of n.
(b) Define the relation R2 on the set R x R as follows: ∀(a, b), (c, d) ∈ R x R, (a, b) R2 (c, d) if and only if a = c.
(c) Let X be a non-empty set and let P(X) be the power set of X. Let R3 be the relation defined on P(X) as follows: ∀A, B ∈ P(X), (A, B) ∈ R3 if and only if A ≠ B.
(d) Let S be the set of all possible outcomes of 100 Yes/No votes (two examples of elements of S are 80 Yes, 20 No and 5 Yes, 95 No). For each possible outcome, each of the 100 votes is either a yes or a no, there are no spoiled votes or abstentions. Define a relation R4 on S as follows: ∀s, t ∈ S, s R4 t if and only if the number of Yes votes in outcome s is less than or equal to the number of Yes votes in outcome t.
Problem 5.
(a) For each of the four relations R1, R2, R3, R4 from problem 4, state whether or not the relation is:
(i) an equivalence relation, (ii) a partial order, (iii) a total order.
(b) For each of the four relations R1, R2, R3, R4 from problem 4 that is an equivalence relation, describe its equivalence classes.