2

Apparently, it is a common mistake to write $\forall x[R(x) \rightarrow P(x)]$ instead of $\forall x[R(x)\wedge P(x)]$ in some cases, however I can't seem to find the difference between the two.

I did some research in ProofWiki and a Discrete Mathematics book, but I couldn't find this specific difference explained.

Could you please explain it to me and give some examples on when to use one and when to use the other?

Thank you for your time.

Shaun
  • 44,997
borg123
  • 275
  • Try using the tableau method. It's handy for this sort of thing. – Shaun Nov 02 '13 at 18:38
  • $p\rightarrow q$ is equivalent to $\neg p\vee q$ that is: $p$ is not true or $q$ is true. $p\wedge q$ is: $p$ is true and $q$ is true. I should say that a difference between them is obvious. – drhab Nov 02 '13 at 18:43
  • 1
    In the first case, if $R$ is true then also $P$ is true. But it is possible to have $P$ true without $R$. But in the second case, you must have both true to have the statement true. – Sigur Nov 02 '13 at 18:43
  • This mistake may be because in English, one sometimes says "this and that" to mean this causes that. – Neal Nov 02 '13 at 18:45
  • “If I am the best then I am the best” is true but does not imply that I am the best. – Carsten S Nov 02 '13 at 20:00
  • In fact, have you tried $P=R$? – Martin Brandenburg Nov 03 '13 at 10:38

3 Answers3

6

It's the difference between

  1. "anyone who gets a perfect score on the quiz will receive a cookie," and

  2. "everyone gets a perfect score on the quiz and will receive a cookie."

It's a bit tricky to translate number 1 from colloquial language into first-order logic, but when you do, it says $\forall x\,(Q(x) \to C(x))$ where $Q(x)$ means "$x$ gets a perfect score on the quiz" and $C(x)$ means "$x$ will receive a cookie."

Trevor Wilson
  • 16,989
5

Try with the following basic, intuitive definitions:

$$x\in\Bbb Z=\text{the set of integer numbers}\;,\;\;R(x):=x\;\text{is a prime number}\;,\;$$

$$P(x):=x\;\text{not divisible by}\;4$$

Then you try to explain the difference between "For any integer $\;x\;$ , if $\;x\;$ is a prime number then is is undivisible by four" and "For any integer $\;x\;$ , $\;x\;$ is both prime and undivisible by four".

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
3

Assume $[\forall x[Rx\to Px]]\leftrightarrow [\forall x[Rx\wedge Px]]$ and suppose $ \forall x[Rx\to Px] $. Then $ \forall x[Rx\wedge Px] $. Instantiate with $a$ for $x$. Now $Ra\to Pa$ and $Ra$, $Pa$. But then $\neg Ra$ is an option, a contradiction.

You can see these things clearly with tableaux.

Tableau

Shaun
  • 44,997
  • @borg123: I recommend S.G. Simpson's Mathematical Logic lecture notes for learning how to construct tableaux. – Shaun Nov 03 '13 at 10:23