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