The task is to prove/disprove the following implications depending on whether they are true or false:

  1. $\exists n(5\vert n) \land \exists n(6\vert n) \implies \exists n(5\vert n \land 6\vert n)$
  2. $\exists n(5\vert n \land 6\vert n) \implies \exists n(5\vert n) \land \exists n(6\vert n)$

The second one seems rather straightforward: If we assume $n=30$ then $5\vert n \land 6\vert n$ is true and $30$ also satisfies the right-hand side. On the other hand, I can't wrap my head around the first one. At first it seems that all individual statements are true, that is $\exists n(5\vert n)$ is true considering $n=5$, $\exists n(6\vert n)$ if $n=6$ and $\exists n(5\vert n \land 6\vert n)$ for $n=30$. So, technically it's $True \implies True$ which is also $True$.

But the implication doesn't sound right. For example, if I said there exists n such that n is prime and there exists n such that n is divisible by 4, it wouldn't mean that there exists n such that n is prime and also n is divisible by 4. Or, more generally, if I understand correctly, $\exists n(\phi(n)) \land \exists n(\psi(n)) \implies \exists n(\phi(n) \land \psi(n))$ isn't always true.

That leads to my question:

Does the fact that both sides of implication are true always mean that the implication is true, even if left hand side isn't enough to prove the right hand side? Or should the first stated implication be considered false and if so, how can it be proved?


3 Answers 3


The second implication is always true. It can be Proved axiomatically in general or even in individual cases like your example. We can not generate a Counter-Example.

$\exists n(5\vert n \land 6\vert n) \implies \exists n(5\vert n) \land \exists n(6\vert n)$
This is somewhat like to $(A \land B \implies A) \land (A \land B \implies B)$

The first implication is not always true & hence must be treated like not true. We can generate Counter-Examples to show that it is not true in general or even in individual Cases like your Example.

Counter Example in Individual Case :
Let the Universe of Discourse be the integers between 3 & 24.

$\exists n(5\vert n) \land \exists n(6\vert n) \implies \exists n(5\vert n \land 6\vert n)$

Here , we see that $5,10,15,20$ satisfy $\exists n(5\vert n)$
More-over , we have that $6,12,18,24$ satisfy $\exists n(6\vert n)$
Yet , there is no $n$ which satisfies $\exists n(5\vert n \land 6\vert n)$

Counter Example in general Case :
$\exists n(P(n)) \land \exists n(Q(n)) \implies \exists n(P(n) \land Q(n))$
This is not true because there may be no $n$ which has both Properties $P$ & $Q$
In worst Case, these two Properties may be Negations :
$\exists n(P(n)) \land \exists n(\lnot P(n)) \implies \exists n(P(n) \land \lnot P(n))$
Naturally , this implication is not true.

  • $\begingroup$ Thank you for the answer; I get now how the general process works. However, it also showed me that I might have omitted an important detail in the question, as originally it was stated "Variables verify through the set of natural numbers". I'm not sure if it would largely change the nature of question and thus be misleading, so I'll leave it as-is, but could you tell me whether it changes the way we approach the problem? Or, to be more specific, could we still assume the Universe of Discourse as you did? $\endgroup$
    – Pharnem
    Nov 11, 2022 at 19:57
  • $\begingroup$ We are still using the Set of Natural Numbers , but limiting to a small subset , hence I think we can make that assumption. In some other subset , that may turn out true. Still the Core Point will be that it is not true in some subset , hence the implication will not be valid inferentially. $\endgroup$
    – Prem
    Nov 11, 2022 at 20:09

In this specific case the first implication is correct. The general case is not correct, as was explained by Prem. But, since it is always the case that there is a number that is divisible by both 5 and 6, any possible antecedent implies that there is such a number.

  • $\begingroup$ This answer is correct on the assumption that $n$ ranges over all natural numbers. This assumption was missing in the original question but was added in the OP's comment on Prem's answer. $\endgroup$ Nov 16, 2022 at 20:08
  • First implication is wrong.

How to disprove it? Give an example of a set, for which the implication is false. That is where there exists number which is divisible by 5 and there exists number which is divisible by 6, but this set doesn't contain number which is divisible both by 5 and 6.

One of the examples could be $\{5, 6\}$.

  • Second implication is correct.

How to prove it? Prove that for every possible set the implication is true. Assume that you have some set $A$, and the following statement is true: $\exists n(5|n \land 6|n), n \in A$ . Then you need to prove $\exists n(5|n),n\in A$ and prove $\exists n(6|n),n\in A$.

To prove $\exists n(5|n),n\in A$ you need to give an example of an element from $A$ for which $5|n$ is true. Similarly for $\exists n(6|n),n\in A$.

From the statement $\exists n(5|n \land 6|n), n \in A$ you have at least one element $n$ with known property to work with.

You can plug it in $\exists n(5|n)$ and show that from $(5|n \land 6|n)$ follows $(5|n)$. Same for $\exists n(6|n)$. Statements proved, hence if $\exists n(5|n \land 6|n), n \in A$ is true, then $n_0,n_1\in A,\exists n_0(5|n_0)\land\exists n_1(6|n_1)$ is also true for all possible sets $A$.

At the end, it turned out that the first one was more straightforward.

Also, you should note that implication can be true for some set, but not correct and you can disprove it if it is false for some other set.

Implication is correct and you can prove it if it is true for every set.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .