0E: Exercises

 

Exercise \(\PageIndex{1}\)

Define \(h : \mathbb{Z} \rightarrow \mathbb{Z} \) by \(h(x) = x^2+4 \).  Determine (with reasons) whether or not \(h \) is  injective (one-to-one ) and whether or not \(h \) is surjective (onto).  

Exercise \(\PageIndex{2}\)

Define \(f:\mathbb Z\to\mathbb Z\) by
\(
f(n)=3n+2.
\)

Determine (with reasons) whether or not \(f \) is one−to−one and whether or not \(f \) is surjective (onto).  

Answer

(a) injective (one-to-one) :

Let \(a,b \in mathbb Z \) such that 
\(
f(a)=f(b).
\)

Then

\begin{align*}
3a+2 &= 3b+2,\\
3a &= 3b,\\
a &= b.
\end{align*}

Therefore \(f\) is injective (one-to-one) .

Let \(y=0\). Then

\(
n=-\frac{2}{3},
\)

which is not an integer.

Therefore, \(0\) is not in the range of \(f\).

Hence \(f\) is not surjective (onto).

Exercise \(\PageIndex{3}\)

Suppose \(f : A \rightarrow B \) and \(g : B \rightarrow C \) are functions.  Prove or disprove the following statements: 

1. If \(g \circ f \) is injective (one-to-one) then \(g \) is injective (one-to-one) . 

2. If \(g\circ f\) is injective (one-to-one) , then \(f\) is injective (one-to-one) .

3. If \(g\circ f\) is surjective (onto), then \(g\) is surjective (onto).

4. If \(f\) is injective (one-to-one) , then \(g\circ f\) is injective (one-to-one) .

5. If \(g\) is surjective (onto), then \(g\circ f\) is surjective (onto).

6. If \(g \circ f \) is injective (one-to-one) and \(f \) is surjective (onto), then \(g \) is injective (one-to-one) .

7.  If \(g \circ f \) is surjective (onto) and  \(g \) is injective (one-to-one) , then  \(f \) is surjective (onto).

8. If both \(f\) and \(g\) are injective (one-to-one) , then
       \(g\circ f\) is injective (one-to-one)

9. If both \(f\) and \(g\) are surjective (onto), then
       \(g\circ f\) is surjective (onto).

Exercise \(\PageIndex{4}\)

Determine whether or not each of the following binary relations \(R \) on the given set \(A \) is reflexive, symmetric, antisymmetric, or transitive.  If a relation has a certain property, prove this is so; otherwise, provide a counterexample to show that it does not.  If \(R \) is an equivalence relation, describe the equivalence classes of \(A \). 

1. Let \(S = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \). Define a relation \(R \) on \(A = S \times S \) by \((a, b) R (c, d) \) if and only if \(10a + b \le 10c + d \). 

2. Let \(A = \mathbb{Z} \backslash \{0\} \). Define a relation \(R \) on \(A \), by \(a R b \) if and only if \( ab > 0 \).

3. Define a relation \(R \) on \(A = \mathbb{Z} \) by \(a R b \) if and only if \(4 | (3a + b) \).

Caution: 

Error analysis: explain what is wrong with these proofs?

Reflexive: \(3a+a=4a,\)
so \(4\mid(3a+a)\). 

Symmetric: if \(4\mid(3a+b)\), then \(3a+b=4m\) for some \(m\in\mathbb{Z}\). Also,
\(3b+a=4(a+b)-(3a+b)=4(a+b-m),\) so \(4\mid(3b+a)\).

Transitive: if \(aRb\) and \(bRc\), then
\(a\equiv b\pmod4 \) and \(b\equiv c\pmod4.\)
Hence \(a\equiv c\pmod4,\) so \(aRc\).

1. Define a relation \(R \) on \(A = \mathbb{Z} \) by \(a R b \) if and only if \(3 | (a^2 - b^2 ) \). 

2. Let \(A = \mathbb{R} \), If \(a,b \in \mathbb{R} \), define \(a R b \) if and only if \(a - b \in \mathbb{Z} \). 

3. Define a relation \(R \) on the set \(\mathbb{Z} \times \mathbb{Z} \) by \((a, b) R (c, d) \) if and only if \(ac = bd \). 

4. Define a relation \(R \) on \(\mathbb{Z} \) by \(a R b \) if and only if \(2 \mid a^2+b\). 

5. Let \(A = \mathbb{R} \), If \(a,b \in \mathbb{R} \), define \(a R b \) if and only if \(a - b \in \mathbb{Q} \).

6. Let \(A=\mathbb{R} \times \mathbb{R} \), If \((x,y),(x_1,y_1) \in \mathbb{R}\times \mathbb{R}\), define \((x,y) \, R \, (x_1,y_1)\) if and only if \( x^2+y^2=x_1^2+y_1^2.\)

7. Define a relation \(R \) on \(\mathbb{Z} \) by \(a R b \) if and only if \(5 | (2a + 3b) \).

Answer

\(R \) is reflexive on \(\mathbb{Z} \).

Proof:

Let \(a \in \mathbb{Z} \).

We shall show that \(a R a \), specifically \(5|(2a+3a) \).

Consider that \(2a+3a = 5a \) and \(a \in \mathbb{Z} \).

Thus \(5|(2a+3a) \),  and \(aRa \).

Therefore \(R \) is reflexive on \(\mathbb{Z} \).◻

 

2. \(R \) is symmetric on \(\mathbb{Z} \).

Proof:

Let \(a,b \in \mathbb{Z} \) s.t. \(5|(2a+3b \).

Thus \(2a+3b=5m \) for some \(m\in \mathbb{Z} \).

We will show that \(3a+2b=5k \) for some \(k \in \mathbb{Z} \).

Consider that \(-2a-3b=-5m \) for some \(m\in \mathbb{Z} \).

Then \(5(a+b) -2a-3b=5(a+b)-5m \).

Thus \(3a+2b=5(a+b-m) \) where \(a+b-m=k \in \mathbb{Z} \).

Hence \(5|(3a+2b) \) and \(bRa \).

Since \(bRa \), \(R \) is symmetric on \(\mathbb{Z} \).

 

3. \(R \) is not antisymmetric on \(\mathbb{Z} \).

Counterexample:

Let \(a=0 \) and \(b=5 \).

Then \(5|(2(0)+3(5)) \) and \(5|(2(5)+3(0) \).

However, since \(0 \ne 5 \) \(R \) is not antisymmetric on \(\mathbb{Z} \).◻

 

4. \(R \) is transitive on \(\mathbb{Z} \).

 

Let \(a,b,c \in \mathbb{Z} \) s.t. \(aRb \), \(5|(2a+3b) \) and \(bRa \), \(5|(2b+3c) \).

We will show that \(aRc \), \(5|(2a+3c) \).

Since \(5|(2a+3b) \), \(2a+3b=5(k) \) for some \(k \in \mathbb{Z} \).

Since \(5|(2b+3c) \), \(2b+3c=5(m) \) for some \(m \in \mathbb{Z} \).

Consider \(2a+3c=(2a+3b)+(2b+3c)-5b \)

       \(=5(k)+5(m)-5(b) \)

       \(=5(k+m-b) \), where \(k+m-b \in \mathbb{Z} \).

Hence \(5|2a+3c \) and \(aRc \).

Hence \(R \) is transitive on \(\mathbb{Z} \).◻

Since \(R \) is reflexive, symmetric and transitive on \(\mathbb{Z} \), \(R \) is an equivalence relation.

 

The equivalence classes of \(aRb \) iff \(5 | (2a + 3b) \) are \([0], [1], [2], [3] \) and \([4] \).

Let \(a \in \mathbb{Z} \), then \([a]=\{a\in \mathbb{Z}:x \sim a\} \).

\([0]=\{x \in \mathbb{Z}: x\sim 0\} \)

      \(=\{x \in \mathbb{Z}: 5|(2x+3(0)) \} \)

      \(=\{x \in \mathbb{Z}: 5|2x \} \)

      \(=\{x \in \mathbb{Z}: 2x=5m, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -10,-5,0,5,10,\ldots\} \).

  

\([1]=\{x \in \mathbb{Z}: x\sim 1\} \)

     \(=\{x \in \mathbb{Z}: 5|(2x+3(1)) \} \)

      \(=\{x \in \mathbb{Z}: 5|(2x+3) \} \)

      \(=\{x \in \mathbb{Z}: 2x+3=5m, m\in \mathbb{Z} \} \)

      \(=\{x \in \mathbb{Z}: 2x=5m-3, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -9,-4,1,6,11,\ldots\} \).

  

\([2]=\{x \in \mathbb{Z}: x\sim 2\} \)

     \(=\{x \in \mathbb{Z}: 5|(2x+3(2)) \} \)

      \(=\{x \in \mathbb{Z}: 5|(2x+6) \} \)

      \(=\{x \in \mathbb{Z}: 2x+6=5m, m\in \mathbb{Z} \} \)

      \(=\{x \in \mathbb{Z}: 2x=5m-6, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -8,-3,2,7,12,\ldots\} \).

 

\([3]=\{x \in \mathbb{Z}: x\sim 3\} \)

     \(=\{x \in \mathbb{Z}: 5|(2x+3(3)) \} \)

      \(=\{x \in \mathbb{Z}: 5|(2x+9) \} \)

      \(=\{x \in \mathbb{Z}: 2x+9=5m, m\in \mathbb{Z} \} \)

      \(=\{x \in \mathbb{Z}: 2x=5m-9, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -7,-2,3,8,13,\ldots\} \).    

  

\([4]=\{x \in \mathbb{Z}: x\sim 4\} \)

     \(=\{x \in \mathbb{Z}: 5|(2x+3(4)) \} \)

      \(=\{x \in \mathbb{Z}: 5|(2x+12) \} \)

      \(=\{x \in \mathbb{Z}: 2x+12=5m, m\in \mathbb{Z} \} \)

      \(=\{x \in \mathbb{Z}: 2x=5m-12, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -6,-1,4,9,14,\ldots\} \)

11. Let \(A, B \in \mathbb{M}_{nn}(\mathbb {C})\). We define the relation \(A R B\) if and only if there exists an invertible matrix \(P \in \mathrm{GL}_n(\mathbb {C})\) such that \(B = P^{-1} A P\). 

Answer

11. Reflexivity: Let \(A \in \mathbb{M}_{nn}(\mathbb {C})\). Then  the identity matrix \(I_n\) is invertible and \(A = I_n^{-1} A I_n\), so \(A R A\).

      Symmetry: Let \(A,B \in \mathbb{M}_{nn}(\mathbb {C})\) such that \(A  R B\). Thus, \(B = P^{-1}AP\) for an invertible matrix \(P\). Multiplying on the left by \(P \) and right by \(P^{-1} \) yields \(A = P B P^{-1} = (P^{-1})^{-1} B (P^{-1}) \) . Setting \(Q = P^{-1} \) ,\(Q \) is invertible, so \(B R A \) .

       Transitivity: Let \(A,B \in \mathbb{M}_{nn}(\mathbb {C})\)  such that (A R B \) and\(B RC \) . Then \(B = P^{-1}AP \) and \(C = Q^{-1}BQ \) for invertible \(P, Q \) . Substituting \(B \) gives \(C = Q^{-1}(P^{-1}AP)Q = (PQ)^{-1} A (PQ) \) . Since \(PQ \) is invertible, \(A RC \) .

 

Exercise \(\PageIndex{5}\)

Let \(f: A \to B\) be a function. Define a relation \(R_f\) on \(A\) by: \[ x R_f y \iff f(x) = f(y) \]

1. Prove that \(R_f\) is an equivalence relation on \(A\).
2.  Express the equivalence class \([x]_{R_f}\) in terms of a pre-image of a set under \(f\).

Answer

1. Reflexive: Let  \(x \in A\). Then \(f(x) = f(x)\), so \(x R_f x\).

Symmetric: Let  \(x ,y \in A\) such that \(x R_f y\), then \(f(x) = f(y) \implies f(y) = f(x) \implies y R_f x\).

Transitive : Let  \(x ,y , z \in A\) such that \(x R_f y\) and \(y R_f z\), then \(f(x) = f(y)\) and \(f(y) = f(z) \implies f(x) = f(z) \implies x R_f z\).

2. \[ [x]_{R_f} = \{y \in A \mid f(y) = f(x)\} = f^{-1}(\{f(x)\}). \]

 

Exercise \(\PageIndex{6}\)

1. Consider the mapping
\(f:\mathbb{R}\to\mathbb{R}\) defined by \( f(x)=\dfrac{1}{x+5}.\)

Is \(f\) well-defined? Justify your answer.

2. Consider the mapping
\( f:\mathbb{Z}_6 \to\mathbb{Z}, \) defined by \( f([x])=x+1.\)

Is \(f\) well-defined? Justify your answer by considering two different representatives of the same equivalence class.

Exercise \(\PageIndex{7}\)

Prove that
\(
A\cap(B\cup C)
=
(A\cap B)\cup(A\cap C)
\)
by proving both set inclusions.