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.

    Thanks for your lecture!


  2. Eliot I says:

    Oh thank you!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: