Reference no: EM13846445

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)) = 3^m9ⁿ 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) ∈ R₁ 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) R₂ (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) ∈ R₃ 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 R₄ 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 R₁, R₂, R₃, R₄ 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 R₁, R₂, R₃, R₄ from problem 4 that is an equivalence relation, describe its equivalence classes.