Proof of the question

Question

Prove that { 6x | x ∈ Z}={ 2x | x ∈ Z } ∩ { 3x | x ∈ Z }.

Hint: Try proving set containment in both direction (⊆ and ⊇).

Answer 1

Prove that { 6x | x ∈ Z}={ 2x | x ∈ Z } ∩ { 3x | x ∈ Z }.

Hint: Try proving set containment in both direction (⊆ and ⊇).

Following the hint, let us first go left to right. Suppose g is an arbitrary element of { 6x | x ∈ Z}. So g = 6k for some k in Z. So we can conclude g=6k = 2(3k) where 3k is in Z. Therefore g is an element of { 2x | x ∈ Z }. Similarly g=6k=3(2k) where 2k is in Z, Therefore g is an element of { 3x | x ∈ Z }. Therefore g is in the intersection of the two sets. We have just shown that an arbitrary element of the lefthand set must be an element of the righthand set. And so { 6x | x ∈ Z} ⊆ { 2x | x ∈ Z } ∩ { 3x | x ∈ Z }.

Now lets go in the other direction. This is a little trickier and how you answer depends on what what other results you have at hand. Suppose g is an arbitrary element of { 2x | x ∈ Z } ∩ { 3x | x ∈ Z }. So therefore g=2m for some integer m. Also g= 3n for some integer n. 

The fact we will use is as follows:

If an integer p divides the product q times r and p and q are relatively prime (i.e.e they have no non-trivial common factors) then p divides r. 

So back to our problem….

Since g=2m, then 2 divides g. But g also = 3n. So 2 divides 3n. But since 2 and 3 are relatively prime, 2 must divide n. So n=2s for some integer s.

Now lets put all that together: g = 3n = 3(2s) = 6s. So g is an element of { 6x | x ∈ Z}

So therefore:

 { 6x | x ∈ Z} ⊇ { 2x | x ∈ Z } ∩ { 3x | x ∈ Z }.

 

Now putting the two results together… since i) { 6x | x ∈ Z} ⊆ { 2x | x ∈ Z } ∩ { 3x | x ∈ Z }.

 And { 6x | x ∈ Z} ⊇ { 2x | x ∈ Z } ∩ { 3x | x ∈ Z }. The two sets are equal:

 

{ 6x | x ∈ Z}={ 2x | x ∈ Z } ∩ { 3x | x ∈ Z }.