Assignment 1

Exercise \(\PageIndex{1}\)

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\).

Exercise \(\PageIndex{1}\)

Define a relation \(R\) on \(A={\mathbb Z}\) by

\(a \,R\, b\) if and only if \( 4 \mid (3a+b),\) for \(a,b \in {\mathbb Z}.\)

Answer

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

Proof:

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

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

Consider \(3a+a = 4a \) and \(a \in \mathbb{Z} \).

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

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

 

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

Proof:

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

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

We will show that \(4 \mid 3b+a. \)

Since \(3a+b=4m \), \(-3a-b=-4m \).

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

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

Hence \(4|(3b+a) .\) Hence \(bRa \).

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

 

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

Counterexample:

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

Then \(4|(3(0)+4) \) and \(4|(3(4)+0) \). Thus \(4 R 0\) and \(0 R 4\)

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

 

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

Proof:

Let \(a,b,c \in \mathbb{Z} \) s.t. \(aRb \) and \(bRc \).

Since \(aRb \), \(4|(3a+b) \) and \(bRc \), \(5|(3b+c) \).

We will show that \(aRc \), that is  \(4|(3a+c) \).

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

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

Consider \begin{align*} 3a+c&=(3a+b)+(3b+c)-4b \\ & =4(k)+4(m)-(b)\\ &=5(k+m-b) ,  \end{align*} where \(k+m-b \in \mathbb{Z} .\) 

Hence \(4|3a+c \). Thus  \(aRc \).

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

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

 

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

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}: 4|(3x+(0)) \} \)

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

      \(=\{x \in \mathbb{Z}: 3x=4m, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -8,-4,0,4,8,\ldots\} \).

  

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

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

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

      \(=\{x \in \mathbb{Z}: 3x+1=4m, m\in \mathbb{Z} \} \)

      \(=\{x \in \mathbb{Z}: 3x=4m-1, m\in \mathbb{Z} \} \)

      \(=\{\ldots, -7,-3,1,5,9,\ldots\} \).

  

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

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

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

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

      \(=\{\ldots, -6,-2,2,6,10,\ldots\} \).

 

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

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

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

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

      \(=\{\ldots, -5,-1,3,7,11,\ldots\} \).    

  

Exercise \(\PageIndex{2}\)

Define a relation \(R\) on \(A={\mathbb N}\) by \(a \, R \, b\) if and only if \( 2 \mid a^2+b,\) for \(a,b \in {\mathbb N}.\) 

Answer

Proof of Reflexivity:

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

We shall show that\(a^2+a=2m, m \in \mathbb{Z} \).

We can show this directly or using cases:

Directly:

 Since , and are consecutive integers,

is even. Thus \(R \) is reflexive on \(\mathbb{N} \).

 

Proof of Symmetry:

Let \(a,b \in \mathbb{N} \)  such that \(a R b.\)

That means \(a^2 + b = 2m, m \in \mathbb{Z} \).

We will show that \(b^2+a =2k, k \in \mathbb{Z} \).

Since

,  .

Thus 

.

Since a(a+1) is even,  is even.

Thus \(R \) is symmetric on \(\mathbb{N} \).

Antisymmetry: 

Caution: \( 0 \notin \mathbb{N}\).

Let \(a = 1, b = 3\).

\( 1^{2} + 3 = 2(2), \)  and \( 3^{2} + 1 = 2(5) \)

But \(1 \neq 3\), hence, \(R\) is \textbf{not} antisymmetric on \(\mathbb{N} \).

Proof of Transitivity:

Let\(a,b,c \in \mathbb{N} \) such that \(2|a^2+b \) and\(2|b^2+c \).

We will show that \(2|a^2+c \).

Consider \(a^2+b=2m, m \in \mathbb{Z} \) and \(b^2+c = 2n, n\in \mathbb{Z} \).

Further, consider that \(a^2+c= 2m-b+2n-b^2 =2(m+n)-(b^2+b) \).

Since \(R \) is reflexive on \(\mathbb{N} \), \(b^2+b=2 q, q \in \mathbb{Z} \)

Thus \(a^2+c=2(m+n-q), m, n,q \in \mathbb{Z} \).

Thus \(R \) is transitive on \(\mathbb{N} \).

Having shown that \(R\) is reflexive, symmetric and transitive on \(\mathbb{Z} \),\(R \) is an equivalence relation on \(\mathbb{Z} \).◻

 

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

\(a=1 \):

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

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

   \(=\{x\in \mathbb{Z}: x^2+1=2m, m \in \mathbb{Z}\} \)

  \(=\{\pm1, \pm 3, \cdots \} \).

 

\(a=2 \):

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

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

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

  \(=\{ 0, \pm 2, \pm 4, \cdots \} \). 

Exercise \(\PageIndex{3}\)

Let \(A=\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,\)  for \((x,y),(x_1,y_1) \in \mathbb{R}\times \mathbb{R}\).

Answer

Reflexive

Proof:

Let \((a,b) \in \mathbb{R}\times \mathbb{R}\).

Since \(a^2 + b^2 = a^2 + b^2\), \((a,b) \,R\, (a, b)\)

Thus R is reflexive.

Symmetric:

Proof:

Let \((a,b), (a_1, b_1) \in \mathbb{R}\times \mathbb{R}\), s.t  \((a,b)R (a_1, b_1)\)

Thus \(a^2 + b^2 = a_1^2 + b_1^2\)

We shall show \(b \,R\, a\).

Since \(a^2 + b^2 = a_1^2 + b_1^2\),  \(a_1^2 + b_1^2 = a^2 + b^2\)

Thus \((a_1, b_1) \,R\, (a,b)\), and R is symmetric.

antisymmetric:

Counterexample

let \(a = 1, b = 2, a_1 = 2, b_1 = 1\)

then \( (1)^ + (2)^2 =5= 2^2 + 1^2\)

Thus \((a,b) R (a_1, b_1)\) and  \((a_1, b_1) \,R\, (a,b)\)

But \( (1,2) \neq (2,1)\)

Thus R is not anti-symmetric

Transitive:

Proof:

Let \((a,c), (a_1, c_1), (a_2, c_2) \in \mathbb{R} \times \mathbb{R}\) such that \((a,c) R (a_1, c_1)\) and \((a_1, c_1)R (a_2, c_2)\).

Since \((a,c) R (a_1, c_1)\), \(a^2 + b^2 = a_1^2 + b_1^2\).

Since \((a_1, c_1)R (a_2, c_2)\), \(b^2 + c^2 = b_1^2 + c_1^2\)

Thus, \(a^2 + c^2 = a_1^2 + c_1^2\)

Hence \((a,c) R (a_2, c_2)\) and R is transitive.

 

Since  R is reflexive, symmetric and transitive, R is an equivalence relation on A.

The equivalence classes are 

\([(0,0)] = \{ (x_1,y_1) \in \mathbb{R}\times \mathbb{R} \mid  x_1^2 + y_1^2=0\} \{0\}\)

\([(x, y)] = \{ (x_1,y_1) \in \mathbb{R} \times \mathbb{R} \mid r^2 =x_1^2 + y_1^2= x^2 + y^2 \}\)

 

Exercise \(\PageIndex{2}\)

Consider the function \(f:\mathbb{Z} \to \mathbb{Z}\) define by \(f(n)=n^2+1.\)

Determine whether f is one-to-one and whether \(f\) is onto. If \(f\) is not onto, find the range of \(f.\)

Answer

 

No, \(f\) is not injective.

Counterexample:

Let \( x_1=-2\) and \( x_2=2\).

Then \( f(-2)=(-2)^2+4=8\) and\( f(2)=(2)^2+4=8\).

Thus  \( f(-2)=f(2)\) but\( -2 \ne 2\) .

Therefore \( h\) is not injective.◻

 

No,\( h\) is not surjective.

 

Counterexample:

Let\( A= \mathbb{Z}\) and\( B=\mathbb{Z}\) s.t.\( h:A \rightarrow B\) is defined by\( f(x)=x^2+1\) .

Note that\( 3 \in B\) .

Thus\( 3=x^2+1 \implies x= \pm\sqrt{2} \notin A.\)

Thus, \( f\) is not surjective. Range of \(f = \{ x^2+1 \mid x \in \mathbb{Z} \}=\{ 1, 2, 5, 10, 17, 26 \cdots\}.\)

Exercise \(\PageIndex{3}\)

Suppose \(f: B \to C\) and \(g: A \to B\) are functions.

Prove or disprove the following statements:

1. If \(f \circ g\) is onto then \(g\) is onto.
2. If \(f \circ g\) is onto and \(f\) is one-to-one, then \(g\) is onto.

Answer

1. Let .

Let and . 

Let \(f(x)=1,\) for all \(x\in B\).

We will show that , s.t. .

Note that is surjective since s.t. .

However s.t. .

Thus is not surjective.◻

2. Proof:

Let .

We shall show that .

Since is a function,   by definition of a function.

Since is surjective, s.t. .

Thus .

Since is injective, means that .

Thus s.t  .

Thus .

Since and .◻