4
$\begingroup$

Prove:
If no two sets of P,Q,R are disjoint, then three of them cannot be mutually disjoint
is true or false.

I understand that proving an implication is true can be done through methods such as direct case, proving contrapositive, splitting into cases etc. But what about a wrong implication? Can I prove that it is wrong by simply giving a case where it does not hold, such as:

P : {1,2} Q : {2,3} R : {1,3}

or drawing a venn diagram perhaps?

$\endgroup$
  • $\begingroup$ Define disjoint. $\endgroup$ – Kenny Lau Oct 1 '17 at 17:31
  • $\begingroup$ @KennyLau en.wikipedia.org/wiki/Disjoint_sets $\endgroup$ – Xuan Oct 1 '17 at 17:33
  • 2
    $\begingroup$ A counterexample is a perfectly valid way of proving an assertion false. $\endgroup$ – Steven Stadnicki Oct 1 '17 at 17:33
  • 2
    $\begingroup$ The Wiki page you've linked defines disjoint for a pair of sets. For a family of sets, it defines mutually disjoint to mean every pair of sets in the family is disjoint. In which case if no two sets of P, Q, R are disjoint, then the three are mutually disjoint by definition $\endgroup$ – manofbear Oct 1 '17 at 17:39
  • 1
    $\begingroup$ That said, I'm not sure what "not two sets P,Q,R are disjoint" means exactly or what "mutually disjoint" in this case and that should be spelled out. $\endgroup$ – fleablood Oct 1 '17 at 17:57
3
$\begingroup$

Disproving a statement is as simple as providing one case for which the statement does not hold.

There is no difference between proving and disproving statements if you do not know what their truth values are beforehand. For example, supercomputers are actively looking for a counterexample to the Riemann hypothesis while mathematicians are trying to prove it.

$\endgroup$
3
$\begingroup$

But what about a wrong implication? Can I prove that it is wrong by simply giving a case where it does not hold?

Of course! If the statement is false and you can demonstrate it... then it's false.

Prove or disprove: All perfect square are odd.

(Dis)Proof: Well, since $36$ is a perfect square that isn't odd, the statement can not be true.

That's valid and irrefutable.

P : {1,2} Q : {2,3} R : {1,3}

Excellent counter-example. That proves the statement is false.

====

Oh, I should add. A single counter example disproves a statement. But one, two, or infinite confirming examples can never prove a statement (unless you do all possible examples).

To pre-empt a very common error... A proof by contradiction can go: Assume premise is false; prove that that implies something that is known to be false. Therefore is not true that the premise is false. So the premise must be true.

That is valid. (....Unless you are a constructivist who doesn't believe in the law of the excluded middle.... but let's not get into that.)

But a proof by confirmation is not: Assume the result is true; prove that that implies something that is known to be true. Therefore the premise is not false. Therefore the premise is true.

That is NOT valid. We have only confirmed that the premise COULD be true and we have failed to prove conclusively it is false. That doesn't mean that it isn't false. Just that it might be true.

=====

BTW. "No two pairs of sets are disjoint" or "not pairwise disjoint" means $P$ and $Q$ are not disjoint. $Q$ and $R$ are not disjoint. And $P$ and $R$ are not disjoint.

"Mutually disjoint" (which seems like clunky phrase) probably means "the intersection of all three is empty" or "there is no element in all three sets" or "$P\cap Q\cap R = \{x|x \in P; x\in Q; y\in R\} = \emptyset$." I say "probably" because... well, I don't like it. It's not immediately clear to me what it means.

It may be worth noting the notation, $P\cap Q\cap R = \{x|x \in P; x\in Q; y\in R\}$, is acceptable and unambiguous as it can be shown that: $(P\cap Q)\cap R = P\cap (Q\cap R) = \{x|x \in P; x\in Q; y\in R\}$.

$\endgroup$
2
$\begingroup$

I leave aside your example because it is not clear what definitions you use. I show my examples where the domain of discourse is natural numbers.

But what about a wrong implication? Can I prove that it is wrong by simply giving a case where it does not hold

You mix different logical notions: implication and universal quantifier. In your example, a universal quantifier is omitted; it should begin with a phrase “For all sets $P$, $Q$, and $R$ such that …”

It is legal to prove $\lnot\forall x\phi$ by showing a value of $x$ such that $\phi$ is absurd (false). I suppose this is what you mean by “a case where an implication does not hold”. Example. Suppose that $\forall x(0<x)$. Then $0<0$ (I let the value of $x$ be $0$). But this is absurd. Hence $\lnot\forall x(0<x)$. Notice that there is no implication in this example.

It is legal to prove $\lnot(\phi\implies\psi)$ by showing that $\phi$ holds and $\psi$ does not. Such theorems are rare because an implication naturally occurs under a universal quantifier. For example, $\forall x\forall y(x\leq y\implies x\leq y+1)$. So I consider an example of $\lnot\forall x(\phi\implies\psi)$. We can prove it by showing a value of $x$ such that $\phi\implies\psi$ is absurd, and we can prove that $\phi\implies\psi$ is absurd by showing that $\phi$ holds and $\psi$ does not. Example. Suppose that $\forall x\forall y(x+x=y\implies x<y)$. Then $0+0=0\implies 0<0$ (I let the value of $x$ be $0$ and the value of $y$ be $0$). $0+0=0$ holds, but $0<0$ does not. Hence $\lnot\forall x\forall y(x+x=y\implies x<y)$.

$\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.