Can implication be false despite its left and right operands being true?

Question

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?

Answer 1

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.

Answer 2

• 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.

Answer 3

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.