0

I know that when it is a non-contingent contradiction it can be refuted, but for example in this reasoning:

$$P\vdash P\land Q$$

I don't know how to refute it.

EDIT: What I mean is how someone can figure out that for example the fallacy of Affirming the consequent $P\rightarrow Q,Q\vdash P$ is invalid reasoning without making truth tables. A mathematician could use a contingency in his reasoning inadvertently, so how could he be aware of his error?

Here are similar questions but I don't understand the answers.

Propositional logic: Proving contingency without truthtable

Proving Expression is Contingency with Logical Equivalences

Voxywave
  • 25
  • 3
    Natural deduction is a system for proofs, to show that a sequent does not follow you must provide a counterexample so natural deduction is not really useful at that. – Simone Feb 26 '21 at 15:54
  • @Simone Axiomatic propositional calculi are systems for proofs, but that a well-formed formula W is contingent can get shown by demonstrating that adding W to the set of axioms results in a variable as derivable and $\lnot$W also allows a variable to get derived. Counterexamples aren't needed. – Doug Spoonwood Feb 26 '21 at 17:53
  • Please make the body of your question self-contained.It's unhelpful to your readers if you have provided important information in the title of the question that is not in the body text. – Rob Arthan Feb 26 '21 at 21:15
  • 1
    @Simone: that is not true.There are proof-theoretic methods for showing that sequents are unprovable. However, the OP's question is phrased in terms of refutation, so it is unclear how to anser it. – Rob Arthan Feb 26 '21 at 21:20
  • @RobArthan What I mean is how someone can figure out that for example the fallacy of Affirming the consequent $P\rightarrow Q,Q\vdash P$ is invalid reasoning without making truth tables. A mathematician could use a contingency in his reasoning inadvertently, so how could he be aware of his error? – Voxywave Feb 26 '21 at 21:37
  • I am afraid I don't understand what you mean by "contingent". – Rob Arthan Feb 26 '21 at 21:42
  • @RobArthan From what I understand a contingency is not a tautological reasoning but it is not totally contradictory either, but it can sometimes be true or false as the fallacy of the affirmation of the consequent – Voxywave Feb 26 '21 at 21:45
  • @RobArthan I've edited my answer below, you mean something like that? – Simone Feb 27 '21 at 09:28
  • Thanks for the clarification. There are fairly easy rules of thumb that help find refutations: e.g., to refute $\Gamma \vdash \psi$, you must make all the formulas in $\Gamma$ true and $\psi$ false. That leads quickly to a refutation of both the examples you give. To make $\Gamma \vdash \psi$ true, it is sufficient to make $\psi$ true. Again that leads quickly to an interpretation that makes both your examples true. – Rob Arthan Feb 27 '21 at 15:03

1 Answers1

1

Natural deduction offers a system for proving sequents, but to show that $\Gamma\not\vdash \phi$ you need an interpretation for the formulae such that $\Gamma$ is true (or the conjunction of the formulae in $\Gamma$) and $\phi$ is false.

In your example you can just put $P$ as true and $Q$ as false; since $P \land Q$ is therefore false we see that $P \not\vdash P \land Q$.

If you are looking for a more systematic method for finding counterexamples we have truth trees (semantic tableaux).

Edit: a proof theoretic approach using cut-free sequent calculus.

Suppose $\Rightarrow P \to \, (P \land Q)$ were derivable with $P$ and $Q$ as atomic formulae.

The last rule used must have been $R \to$, (introduction of $\to$ on the right). That is, we have:

$$\frac {P \Rightarrow P \land Q} {\Rightarrow P \to (P \,\land \,Q)}$$

And before that we must have had an instance of $R \, \land$ (introduction of $\land$ on the right) :

\begin{align*} \overline{ P \Rightarrow P} \; \;\;\;\; P\Rightarrow Q \\ \hline P \Rightarrow P \land Q \ \ \ \ \ \\ \hline \Rightarrow P \to (P \,\land \,Q) \end{align*}

$P \Rightarrow P$ is axiomatic, which is fine, but there's no rule with which we can derive $Q$ from $P$ as atomic formulae, so the sequent above is underivable.

Simone
  • 620
  • @RobArthan I've edited my answer to provide a proof theoretic approach to the underivability of the sequent in question. You meant something like that in your comment where you mentioned me? – Simone Feb 27 '21 at 09:27
  • 1
    Yes, that's just what I had in mind. Thanks. – Rob Arthan Feb 27 '21 at 15:04