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.

 

The 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{Z_+}}\) by \(a \, R \, b\) if and only if \( 2 \mid a^2+b,\) for \(a,b \in {\mathbb{Z_+}}.\) 

Answer

Proof of Reflexivity:

Let \(a \in \mathbb{Z}_+\). We must show that \(a R a\), which means \(2 \mid (a^2 + a)\). 
    Factoring the expression gives \(a^2 + a = a(a + 1)\). Since \(a\) and \(a + 1\) are consecutive integers, one of them must be even. Therefore, \(a(a + 1) = 2m\) for some \(m \in \mathbb{Z}_+\), which implies \(2 \mid (a^2 + a)\). Thus, \(R\) is reflexive.

Proof of Symmetric:

Let\(a, b \in \mathbb{Z}_+\)such that \(a R b\). By definition,\(a^2 + b = 2m\) for some\(m \in \mathbb{Z}_+\). We must show that\(b R a\), meaning\(2 \mid (b^2 + a)\). 

Method I:   

Observe that we can express \(b^2 + a\)a s:
    \(
    b^2 + a = (a^2 + b) + (b^2 +-b) - (a^2 - a)
    \)
    Since \(a\) and \(a-1\) are consecutive integers, \(b^2 - b = 2q\) and \(a^2 - a = 2p\) for some \(p, q \in \mathbb{Z}_+\). Substituting these into the identity yields:
    \(
    b^2 + a = 2m + 2q - 2p = 2(m + q - p).
    \)
    Since \(k = m + q - p \in \mathbb{Z}\) , it follows that \(2 \mid (b^2 + a)\), so\(b R a\). Thus,\(R\)is symmetric.

Method II: 

Let s.t. .

We will show that .

Since

,  .

Thus 

.

Since a(a+1) is even, 

is even.

Antisymmetric: 

Caution: \( 0 \notin \mathbb{Z_+}\).

To show \(R\) is not antisymmetric, we present a counterexample. Let \(a = 1\) and \(b = 3\), where \(1, 3 \in \mathbb{Z}_+\):
Note that,  \(1 R 3\) because \(1^2 + 3 = 4 = 2(2)\), so \(2 \mid (1^2 + 3)\).
Also,  \(3 R 1\) because \(3^2 + 1 = 10 = 2(5)\), so \(2 \mid (3^2 + 1)\).

However, \(1 \neq 3\). Therefore, \(R\) is not antisymmetric on \(\mathbb{Z}_+\).

Proof of Transitivity:

Let \(a, b, c \in \mathbb{Z}_+\) such that \(a R b\) and \(b R c\). Then \(a^2 + b = 2m\) and \(b^2 + c = 2n\)  for some \(m, n \in \mathbb{Z}_+\). We must show that \(a R c\), meaning \(2 \mid (a^2 + c)\).
    Summing the two equations gives:
    \(
    (a^2 + b) + (b^2 + c) = 2m + 2n \implies a^2 + c = 2(m + n) - (b^2 + b)
    \)
    By reflexivity, \(b^2 + b = 2q\) for some \(q \in \mathbb{Z}_+\). Substituting this yields:
    \(
    a^2 + c = 2(m + n) - 2q = 2(m + n - q).
    \)
    Since \((m + n - q) \in \mathbb{Z}, 2 \mid (a^2 + c)\), so \(a R c\). Thus, \(R\) is transitive.

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

 The equivalence class of an element \(a \in \mathbb{Z}_+\) is defined by \([a] = \{x \in \mathbb{Z}_+ : x R a\}\). Note that since \(x^2 + a \equiv x + a \pmod 2 \), x R a\) holds if and only if \(x\) and \(a\) have the same parity (i.e., both are either even or odd).

Let \(a \in \mathbb{Z_+} \), then \([a]=\{x\in \mathbb{Z_+}:x\sim a\} \). Caution: \( 0 \notin \mathbb{Z_+}\). Then there are only 2 different equivalence classes. They are:

\(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_+}\} \)

  \(=\{1,  3, \cdots \} \). (Set of all positive odd integers)

\(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_+}\} \)

  \(=\{   2,  4, \cdots \} \). (Set of all positive even integers)

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 + c^2 = a_1^2 + c_1^2\).

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

Thus, \(a^2 + c^2 = a_2^2 + c_2^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,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 \}\), for \(r \in \mathbb{R}.\) 

In general, the equivalence class \([(a, b)]\) consists of all points at distance \(r = \sqrt{a^2 + b^2}\) from the origin. The partition is the family of concentric circles centered at \((0, 0)\).

 

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 .◻