0
$\begingroup$

I am learning about predicates and am somewhat a beginner in proofs. I would like your help on proving why statement 2 is false. These are the two statements:

$ \text{statement 1: }(\exists x_1 \in \mathbb{N}, x_1|165) \wedge(\exists x_2 \in \mathbb{N}, 7|x_2)\\ \\ \text{statement 2: }\exists x \in \mathbb{N}, x|165 \wedge 7|x \\ \text{Note: a|b is read as a divides b, and is defined as: } \exists k \in \mathbb{Z}, a.k = b\\ \text{I believe statement 1 is true, since, there exists a natural number that divides 165 (165 itself),}\\ \text{and there exists another number that is divisible by 7 (7 itself). So statement 1 is true.}\\ \text{Statement 2 is false, but I'm not sure why, and how can we prove it to be false?}\\ \text{So I started by trying to prove its negation to be true, i.e:}\\ \forall x \in \mathbb{N}, x \nmid165 \vee 7 \nmid x \\ \Leftrightarrow \forall x\in \mathbb{N} , x|165 \implies 7\nmid x $ Some discussion(using what I've learnt so far about proofs): $\text{Let x be a natural number, and assume x|165 , i.e } \\\exists k1 \in \mathbb{Z},x.k1 = 165 \text{ . Let k1 be this number.} \\ \text{I want to show } 7 \nmid x, \text{i.e } \neg(\exists k_2 \in \mathbb{Z}, 7.k2 = x) \Leftrightarrow (\forall k_2 \in \mathbb{Z}, 7.k_2 \neq x).... \\ \text{Now, how can I use my assumption to reach what I want to show? Thank you for your directions.} $

$\endgroup$
  • $\begingroup$ Do you have the fundamental theorem of arithmetic? $\endgroup$ – Eric Towers Apr 13 '18 at 23:26
  • $\begingroup$ In the first case, there exists $x_1 = 55$ such that $x_1\mid 165$, and there exists $x_2 = 49$ such that $7\mid x_2$. True. The second statement specifies the existence of some particular x such that both $x\mid 165$, and $7\mid x$. There is no such one $x$. $165 = 3\cdot 5\cdot 11$, which is divisible 1, 3, 5, 11, 15, 33, 55, 165$. None of these divisors is divisible by 7. $\endgroup$ – Namaste Apr 13 '18 at 23:33
1
$\begingroup$

We cannot find a number which simultaneously divides 165 and is divided by 7.

Proof Perhaps this is not a particularly elegant proof but the the numbers that divide 165 isn't all that big of a set: {1, 3, 5, 11, 15, 33, 55, 165} and indeed not one of them is a number which 7 divides.

Two proofs for the price of one: If a number was divided by 7 we would know that it is 7x for some x in the naturals. Then we would want this 7x to divide 165 but that would mean that 7 would divide 165. And that's a contradiction.

The first proof is just exhausts all the possibilities.

The second proof requires the fact that when ab divides c this implies that both a divides c and b divides c. I think this fact is the one to exploit for your proof.

$\endgroup$
3
$\begingroup$

Note that

$$7|x \text { and } x|165 \implies 7|165$$

We know that $7$ dose not divide $165$.

Thus statement $(2)$ is false.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.