MATH 2090  Problem Set #5 (Addendum to #4)

York University

Faculties of Pure and Applied Science, Arts, Atkinson MATH 2090. Problem Set #5 (addendum to #4).

Posted November 23, 2003

Due in the Course Box. December 4, 2003

Section A

In your proofs (all informal please) it is imperative to clearly state what tools you use (e.g., WLUS, sWLUS, MP, Leibniz, Monotonicity, Deduction Theorem, Generalization, Auxiliary Variable metatheorem, which axiom(s), etc.)

1. (5 Marks) Prove that R : A → A is transitive iff R^{2} ⊆ R.

2. (5 Marks) Give an example of two equivalence relations R and S on the same set A, such that R ∪ S is not an equivalence relation.

3. (5 Marks) Let F be a partition on a set A and define R on A as in

class:

aRb ≡^{Def.}(∃S ∈ F)(a ∈ S ∧ b ∈ S)

We know from class that R is an equivalence relation.

Prove that the set of all the equivalence classes of R is exactly F. This put in symbols means that you prove two things:

(∀x ∈ A)(∃S ∈ F)[x] = S

and

(∀S ∈ F)(∃x ∈ A)[x] = S

4. (5 Marks) Prove that f : A → B has both a left and a right inverse, iff f is 1-1, onto and total, that is, iff f is a 1-1 correspondence.

NB. Actually, the “only if” was done in class, but do write it down anyway. For the “if” part just prove that f^{−1} : B → A, the inverse

MATH 2090  Problem Set #5 (Addendum to #4)

\underline{relation} is also a function that is total, 1-1 and onto, which moreover satisfies f ∘ f^{−1} = 1_{A} and f^{−1} ∘ f = 1_{B}. Of course, these last two we can also write as f^{−1} • f = 1_{A} and f • f^{−1} = 1_{B} respectively.