Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Assume that in a formal proof I have

$T \cup \{ \varphi \} \vdash \varphi$

$T \cup \{ \varphi \} \vdash \lnot \varphi$

Question 1: can I then deduce $T \cup \{ \varphi \} \vdash \lnot \varphi \land \varphi$? I think there should be a rule of deduction that tells me that I can do that but there is no such rule in my lecture notes. What I do have is the following:

$\{ \psi , \varphi \} \vdash \psi \land \varphi$

So I guess my question boils down to the following:

If I have $T \vdash \varphi$, can I do $T \cup \{ \varphi \}\vdash $?

Question 2: is similar. If I have

$T \cup \{ \varphi \} \vdash \varphi \land \lnot \varphi$ ,can I deduce $T \cup \{ \varphi \} \vdash \lnot \varphi$?

Many thanks for your help.

share|cite|improve this question
You should provide us with your axioms and deduction rules since there exist many deduction systems. If your axioms only have $\to$ remember that $\lnot\phi\land\phi$ is an abbreviation of $\lnot(\lnot\phi\to\lnot\phi)$. – Apostolos Oct 24 '11 at 8:36
up vote 4 down vote accepted

Firstly, $\{\varphi\}\vdash\varphi$ regardless to anything. Simply because there is a proof "$\varphi$".

If you have $T\cup\{\varphi\}\vdash\lnot\varphi$ then you have a contradiction. Simply you can write a proof for $\lnot\varphi$, write $\varphi$ and use the fact that if $\alpha$ and $\beta$ appear in your proof then you can write $\alpha\land\beta$.

From the same idea you can have that if $T\vdash\varphi$, and $T\cup\{\varphi\}\vdash\psi$ then $T\vdash\psi$. Simply by writing the proof for $\varphi$ and then using it later on in your proof of $\psi$.

In the second question you have that $T\cup\{\varphi\}$ proves a contradiction. Using explosion principle you can prove anything you want from it, $\lnot\varphi$ included (and by this xkcd strip even certain phone numbers...)

share|cite|improve this answer
Thanks! And what about $T \vdash \varphi$ and then $T \cup \varphi \vdash$? – Rudy the Reindeer Oct 24 '11 at 8:48
@Matt, if $T\vdash\phi$ then $T\cup\phi$ proves exactly what $T$ proves. – Apostolos Oct 24 '11 at 8:50
@Apostolos: Thanks, I just added that to my answer as well :-) – Asaf Karagila Oct 24 '11 at 8:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.