1

My professor insists this is possible, I say it isn't. What say you?

Certain theorems and axioms have been established or assumed.

Axiom 1: $p\rightarrow {\sim y}$
Axiom 2: ${\sim q}\rightarrow r$
Theorem 1: $p\rightarrow {\sim z}$
Theorem 2: $x\rightarrow \text{either }q\text{ or }z$
Theorem 3: $r\rightarrow \text{either }x\text{ or }y$

Prove, in outline form, that $p\rightarrow q$.

Frenzy Li
  • 3,685
Dana Hill
  • 715

3 Answers3

12

Yes it is possible. Assume that $p\to q$ is false that is $p\wedge \neg q$ is true.

  1. (hyp) $p\wedge \neg q$.

  2. (1. and Axiom 1) $p\wedge (p\to \neg y)\implies \neg y$

  3. (1. and Axiom 2) $\neg q\wedge (\neg q\to r)\implies r$

  4. (2., 3. and Theorem 3) $r\wedge \neg y\wedge (r\to x \oplus y)\implies x$

  5. (1., 4. and Theorem 2) $x\wedge \neg q \wedge (x\to q \oplus z)\implies z$

  6. (5. and Theorem 1) $z\wedge (z\to \neg p)\implies \neg p$

  7. (1. and 6.) $p\wedge \neg p$ (contradiction)

Hence $p\to q$ is proved.

P.S. $\wedge$ is the AND operator, $\neg$ is the NOT operator and $\oplus$ is the EXCLUSIVE OR operator.

Robert Z
  • 145,942
  • @Dana Hill $\wedge$ is the AND operator So $p\wedge \neg q$ is true means that $p$ is true and $q$ is false (i.e. $p\to q$ does not hold). – Robert Z Jul 13 '17 at 20:12
  • "it could be that "not p and q" is true"" . That's right. Check with the truth table of the implication: http://mathworld.wolfram.com/Implies.html – Robert Z Jul 13 '17 at 20:22
  • @Dana Hill The process from 1 to 7 show that if $p\wedge \neg q$ is true then we have a contradiction. Hence $p\wedge \neg q$ is false. This means that $(p,q)$ could be $(F,T)$, $(F,F)$ or $(T,T)$. Those three couples are precisely the true values of $p\to q$. Is it clear now? – Robert Z Jul 13 '17 at 20:28
  • 3
    This proof continues to work even when $\oplus$ is replaced by $\vee$. – Fabio Somenzi Jul 13 '17 at 21:11
3

Direct proof (that is, not by contradiction) \begin{equation} \begin{split} \textrm{ (1.1) }& \textrm{ for Theorem 2: }& \sim z \rightarrow \sim x \textrm{ or } (x \textrm{ and } q)\\ \textrm{ (1.2) }& \textrm{ for Theorem 1 and (1.1): }& p \rightarrow \sim x \textrm{ or } (x \textrm{ and } q)\\ \textrm{ (2.1) }& \textrm{ for (1.2) and Axiom 1: }& p \rightarrow (\sim x \textrm{ and } \sim y) \textrm{ or } (x \textrm{ and } q \textrm{ and } \sim y) \\ \textrm{ (3.1) }& \textrm{ for Theorem 3: }& \sim x \textrm{ and } \sim y \rightarrow \sim r\\ \textrm{ (3.2) }& \textrm{ }& x \textrm{ and } q \textrm{ and } \sim y \rightarrow q\\ \textrm{ (3.3) }& \textrm{ for (2.1), (3.1), and (3.2): }& p \rightarrow \sim r \textrm{ or }q \\ \textrm{ (4.1) }& \textrm{ for Axiom 2: }& \sim r \rightarrow q \\ \textrm{ (4.2) }& \textrm{ for (3.3) and (4.1): }& p \rightarrow q \\ \end{split} \end{equation}

trying
  • 4,756
  • 1
  • 13
  • 23
1

Assuming that

  1. the axioms are using the arrow and tilde to mean implication and negation respectively and that
  2. the axioms establish four primitive constants $p,\,y,\,q,\,r$ and that
  3. the theorems treat $x$ and $z$ as variables which can take on the values of any of the four primitive constants

then by Theorem 1

  1. $p \rightarrow\neg p$
  2. $p \rightarrow\neg\neg p\rightarrow p$
  3. $p \rightarrow\neg y$
  4. $p \rightarrow\neg\neg y\rightarrow y$
  5. $p \rightarrow\neg r$
  6. $p \rightarrow\neg\neg r\rightarrow r$
  7. $p \rightarrow\neg q$
  8. $p \rightarrow\neg\neg q\rightarrow q$

Of course, only this last implication is needed.

John Wayland Bales
  • 21,814
  • 1
    I don't know that your (3) is right. I'm taking r,p,q,x,y,z to all be separate things. Why would you assume any of them could replace another? – Dana Hill Jul 13 '17 at 20:09
  • 1
    That's my point. There is too much missing context. My list of assumptions was just one possible way to fill in unstated context. – John Wayland Bales Jul 13 '17 at 20:13