## 187 – Quizzes 5 and 6

Here is quiz 5 and here is quiz 6.

Problem 1 asks to show that the relation $R$ defined as follows is antisymmetric: Given a set $A,$ the relation $R$ is defined on the subsets of $A$ by setting $x\mathrel{R}y$ for $x,y\subseteq A,$ iff $y\setminus x=\emptyset,$ where $\setminus$ denotes set-theoretic difference of sets.

To show that $R$ is antisymmetric, we need to show that whenever $x,y\subseteq A$ are such that $x\mathrel{R}y$ and $y\mathrel{R}x,$ then $x=y.$ Suppose $x,y$ satisfy these assumptions. We need to show that they are equal as sets, i.e., that they have the same elements.

By definition, $x\mathrel{R}y$ holds iff $y\setminus x=\emptyset,$ and $y\mathrel{R}x$ holds iff $x\setminus y=\emptyset.$ Recall that if $B,C$ are sets, then $B\setminus C=\{a\in B\mid a\notin C\}.$ It follows that $y\setminus x=\emptyset$ iff every element of $y$ is also an element of $x,$ and that $x\setminus y=\emptyset$ iff every element of $x$ is also an element of $y.$ But these two facts together mean precisely that $x$ and $y$ have the same elements, i.e., that $x=y,$ as we needed to show.

Problem 2(a) of quiz 6 asks to consider the relation $R$ defined on ${\mathbb N}$ by setting $x\mathrel{R} y$ for $x,y\in{\mathbb N},$ iff $5|(2^x-2^y),$ and to show that $R$ is an equivalence relation. This means that $R$ is reflexive, symmetric, and transitive. Problem 2(a) of quiz 5 asks to show one of these properties.

To show that $R$ is reflexive, we need to show that for any $x\in{\mathbb N},$ we have that $x\mathrel{R}x,$ i.e., that $5|(2^x-2^x).$ But $2^x-2^x=0$ is certainly divisible by 5.

To show that $R$ is symmetric, we need to show that for any $x,y\in{\mathbb N},$ if it is the case that $x\mathrel{R}y,$ then it is also the case that $y\mathrel{R}x.$ Suppose then that $x\mathrel{R}y.$ This means that $5|(2^x-2^y),$ i.e., there is an integer $a$ such that $5a=2^x-2^y.$ But then $2^y-2^x=-5a=5(-a),$ showing that also $5|(2^y-2^x),$ i.e., $y\mathrel{R}x.$

To show that $R$ is transitive, we need to show that if $x,y,z\in{\mathbb N}$ and both $x\mathrel{R}y$ and $y\mathrel{R}z$ hold, then also $x\mathrel{R}z$ holds. But if $x\mathrel{R}y$ and $y\mathrel{R}z,$ then $5|(2^x-2^y)$ and $5|(2^y-2^z).$ But then it is certainly the case that $5|\bigl((2^x-2^y)+(2^y-2^z)\bigr).$ Since $(2^x-2^y)+(2^y-2^z)=2^x-2^z,$ this proves that, indeed $5|(2^x-2^z),$ or $x\mathrel{R}z,$ as we needed to show.

(If one feels the need to be somewhat more strict: That $5|(2^x-2^y)$ means that there is an integer $a$ such that $5a=2^x-2^y.$ Similarly, $5|(2^y-2^z)$ means that there is an integer $b$ such that $5b=2^y-2^z.$ But then $5(a+b)=5a+5b=(2^x-2^y)+(2^y-2^z)=2^x-2^z,$ showing that there is an integer $c$ such that $5c=2^x-2^z,$ namely, we can take $c=a+b.$)

Problem 2(b) asks to find all natural numbers $n$ such that $3\mathrel{R}n,$ where $R$ is as defined for problem 2(a).

That $3\mathrel{R}n$ means exactly the same that $5|(2^3-2^n).$ Since $2^3=8$ and an integer is a multiple of 5 iff it ends in 5 or 0, we need to find all natural numbers $n$ such that $2^n$ ends in $8$ or $3.$ Since $2^0=1$ and $2^m$ is even for all  naturals $m\ne 0,$ we actually need to find all natural numbers $n$ such that $2^n$ ends in 8. For this, we only need to examine the last digit of the numbers $2^1,2^2,2^3,2^4,2^5,\dots,$ and we find that these last digits form the sequence $2,4,8,6,2,4,8,6,2,4,8,6,\dots$ which is periodic, repeating itself each 4. This means that the numbers $n$ we are looking for are precisely $3,7,11,15,19,\dots,$ i.e., the natural numbers of the form $4k+3$ with $k\in{\mathbb N}.$

### 3 Responses to 187 – Quizzes 5 and 6

1. Eliot I says:

Dr. Caicedo,

I was working with one of students(Josue Gomez) in your class.
From problem 2 (b,)
I guess 5 divides 0 since 5*0 = 0. so need to say n is the form 4k + 3 where k is greater than or equal to 0.
I understand 0 is not natural number. I guess k can be 0 also.

• andrescaicedo says:
2. Eliot I says: