Set closed under multiplication

Question

I'm struggling with some very basic logic, I guess it is in the simplest question that will probably exist on stack exchange.

Define a set $N_{2,3} = \left\{ n \in \mathbb{Z} : 2 \nmid n \text{ and } 3 \nmid n \right\}$. Then prove it is closed under multiplication.

I was trying to use the contrapositive, and had the following solution;

By considering the contrapositive, we seek elements $n \in \mathbb{Z} : 2\mid n \text{ or } 3\mid n$. So given two elements $a,b \in N_{2,3}$ we seek to prove that $ab\in N_{2,3}$. Suppose then w.l.o.g. that $2\mid a$, then we can say $a=2c$ for some $c\in\mathbb{Z}$. Now $ab = (2c)b = 2(cb)$, and clearly $2\mid ab$, hence $ab \in N_{2,3}$.

Something just doesn't feel right with all of this, but I can't put my finger on it. I was also thinking about just saying that taking two elements $a,b \in N_{2,3}$, neither $3$ nor $2$ divide $n$ or $m$, therefore their product $ab$ is also not divisible by $3$ or $2$, hence the set is closed under multiplication.

Thanks for any help!!

Answer 1

Hints for a direct proof:

• $N_{2,3} = \{ 6k \pm 1 \mid k \in \mathbb{Z}\}$

• if $\,a_1, a_2 \in N_{2,3}\,$ then there exist $\,k_1, k_2 \in \mathbb{Z}\,$ such that $\,a_{1}=6k_{1}\pm 1\,$, $\,a_{2}=6k_{2}\pm 1\,$ and it follows that $\,a_1a_2=(6k_1\pm1)(6k_2\pm1) = 6 \,(\;\ldots\;) \pm 1\in N_{2,3}\,$.

Answer 2

By the set construction: "If $2\nmid ab$ and $3\nmid ab$, then $ab\in N_{2,3}$ ".

The contraposition is that: "If $ab\notin N_{2,3}$, then $2\mid ab$ or $3\mid ab$".

However, as you have shown, for any $a,b$ that are both $\in N_{2,3}$ it will always be so that $2\nmid ab$ and $3\nmid ab$.

So every such $ab$ must be in $N_{2,3}$.

---

tl;dr When considering the contrapositive you do not want to find a case were the consequent holds.   You seek to deny that it ever can (for any product of elements from the set).

Answer 3

This is actually so stupid of a logic problem youll kick yourself a little bit.

This is the list of all numbers that you can write as prime factorizations without using a 2 or 3. All numbers can be written as a prime factorial. Thus any number that is in the set written without 2 or 3 is in the set of multiples.

Lets to 35 as an easy example: not divisible by 2, nor 3... Check (1^1)(5^1)(7^1)=35. 35 not divisible by 3, nor is 1,5, or 7 check.

Now lets say we want to know if 385 is in our set.

well 385 cannot be divided by 3 nor 2 check its also 35*11 = (1^1)(5^1)(7^1)*(11^1)

do you see whats going on yet?

no matter what numbers come after you cannot write the numbers in the set without 2 or 3 as a prime factorization. Thus the resulting manipulation is inconsequential. The set is closed under multiplication because it must be for that prime factorization to exist

Answer 4

The comment from @Dog_69 already told you that you had the right proof in your own post! But let's see what was wrong in your presented "proof by contrapositive".

ERROR #1: What you're proving is not the contrapositive of the given statement. The contrapositive of "$P\to Q$" is "$\neg Q\to\neg P$". In this example:

• The original statement "$\color{blue}{P}\to\color{magenta}{Q}$" is "If $\color{blue}{a\in N_{2,3} \text{ and } b\in N_{2,3}}$, then $\color{magenta}{ab\in N_{2,3}}$".

• Then its contrapositive "$\color{magenta}{\neg Q}\to\color{blue}{\neg P}$" is "If $\color{magenta}{ab\notin N_{2,3}}$, then $\color{blue}{a\notin N_{2,3} \text{ or } b\notin N_{2,3}}$".

You didn't set up this contrapositive statement in the beginning of your "proof". In fact, you didn't state at all what you're attempting to prove. And moreover, contrary to your claim that you're "considering the contrapositive", you're actually trying to prove directly the original statement — according to the second sentence of your "proof" that says "given two elements $a,b\in N_{2,3}$, we seek to prove that $ab\in N_{2,3}$".

ERROR #2: After starting with "given two elements $a,b\in N_{2,3}$ …", you proceed to "suppose then w.l.o.g. that $2\mid a$". But that directly contradicts the definition of the set $N_{2,3}$: if $a\in N_{2,3}$, then $a$ cannot be divisible by $2$. So from the get-go your "proof" doesn't make sense, unfortunately.