1

Let $\Sigma_1, \Sigma_2$ be two finite sets of statements in propositional calculus s.t $\Sigma_1\cup\Sigma_2$ has a contradiction. Prove that there is a statement A s.t $$\Sigma_1\vdash{A}\ and\ \Sigma_2\vdash{\neg{A}}$$

is it still true with infinite $\Sigma_1,\Sigma_2$?

My attempt:

in case one of the sets is $\phi$ or one of the sets has a contradiction its obvious... So, we left with the case where both aren't empty and both without contradiction.

I didn't manage to prove this... Any kind of help will be appreciated Thanks!

dave
  • 705
  • 4
  • 16

2 Answers2

2

Let $A_1,\ldots,A_n\in\Sigma_1$ and $B_1,\ldots,B_m\in\Sigma_2$ the sentences that generate the contradiction.

Let $A=A_1\wedge\ldots\wedge A_n$. It is clear that $A_1\wedge\ldots\wedge A_n\vdash A$. Since propositional calculus is sound, $A\wedge(B_1\wedge\ldots\wedge B_m)$ must be false in $\Sigma_2$, or, equivalently, $(B_1\wedge\ldots\wedge B_m)\to\neg A$ must be true. Since propositional calculus is complete, $(B_1\wedge\ldots\wedge B_m)\vdash\neg A$.

For the infinite sets case, I have been thinking, but no result so far.

ajotatxe
  • 65,084
  • why $A∧(B1∧…∧Bm)$ must be false? – dave May 24 '14 at 13:24
  • 2
    What's the difference for the infinite case? You still only need finitely many sentences in each set to generate a contradiction. – user21820 May 24 '14 at 13:24
  • @dave: By definition if they generate a contradiction then the conjunction must be false. – user21820 May 24 '14 at 13:24
  • The definition i know is that Σ has a contradiction if Σ⊢A and Σ⊢¬A ok got it, there is no Model for Σ1∪Σ2 – dave May 24 '14 at 13:26
  • @dave: ... for some $A$. Then $Σ ⊢ A \wedge \neg A$ and we can pick a finite subset of $Σ$ that derives the contradiction. – user21820 May 24 '14 at 13:28
  • @dave: And by the way you should always say "if and only if" for definitions, because "if" means the wrong thing. – user21820 May 24 '14 at 13:30
  • 1
    definitions are implicitly iff – dave May 24 '14 at 13:35
  • @dave: No. I've seen some that really mean "if" and would be wrong if it is changed to "iff", and vice versa. Besides, it would be very inconsistent to use "if" to mean two different things in different places. – user21820 May 24 '14 at 13:37
  • 3
    I think the key here is that proofs are always finite, so that if for infinite $\Sigma$ we have $\Sigma\vdash\phi$ then there's a finite $\xi\subset\Sigma$ with $\xi\vdash\phi$. So it really comes back to how it works in the finite case, I believe. – Malice Vidrine May 24 '14 at 13:38
  • @MaliceVidrine: Yup exactly my point in my first comment. – user21820 May 24 '14 at 13:39
  • Yeah, I'd've skipped the comment if yours had been visible when I started typing. Dumb cell phone browser ;p – Malice Vidrine May 24 '14 at 13:44
  • '+1' but with a comment ... I personally would prefer not to mix provability with true/false. $\Gamma$ is inconsistent iff $\Gamma \vdash \bot$. Let $\alpha := A_1 \land ... \land A_n$ and $\beta := B_1 \land ... \land B_M$. Thus, having $\alpha, \beta \vdash \bot$ - with the "simple" corollary : if $\Gamma, \varphi \vdash \bot$, then $\Gamma \vdash \lnot \varphi$ - we conclude : $\beta \vdash \lnot \alpha$. – Mauro ALLEGRANZA May 24 '14 at 14:49
-2

There are a couple of problems with your puzzle.

  • the idea that $\Sigma_1, \Sigma_2$ be two finite sets of statements is in itself allready a contradiction, if they are closed onder modus ponens and so they are infinite sets , there are just an infinite number of theorems that belong to both sets.

  • If contradiction of a set means that $ (\Sigma_1\cup\Sigma_2\vdash {A} $ and $ \Sigma_1\cup\Sigma_2\vdash{\neg{A}}$ you cannot tell which if $ A$ is from $\Sigma_1 $ or from $ \Sigma_2$ so how can you proof that $\Sigma_1\vdash {A} $?

Willemien
  • 6,582
  • They don't have to be closed under modus ponens... and its ture by contradiction i mean that. – dave May 24 '14 at 13:18
  • Also downvoting for the reason that they needn't be closed under m.p., and because the second point misunderstands the question. – Malice Vidrine May 24 '14 at 13:30