2
$\begingroup$

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and $\chi$ together are equivalent to $\phi$ but neither one on their own implies $\phi$:

$\phi$ $\longleftrightarrow$ ($\psi$ $\land$ $\chi$)

$\lnot$ ($\psi$ $\rightarrow$ $\phi$)

$\lnot$ ($\chi$ $\rightarrow$ $\phi$)

The problem is, when I evaluate the conjunction of all these statements in propositional calculus, it adds up to a contradiction, which seems a bit strange to me. I didn't expect that you couldn't compose a statement of two smaller statements that on their own don't imply $\phi$ but together are equal to it. I expect I'm doing something wrong in my formulation of my problem, or somehow I evaluated the statements wrong.

Say for example $\phi$ is the Axiom of Choice and $\psi$ is the Axiom of Dependent Choice, this implies there's no statement $\chi$ that doesn't fully imply the Axiom of Choice on its own to satisfy the first statement. I feel I must be doing something wrong, because it seems weird that I can't take two weak statements to make a strong statement. It seems so wrong I'm more than a little embarrassed asking this.

I don't think there's any magical translation that lets you turn invalid propositional statements into valid first order statements. Is there something I'm missing here? The conclusion seems surprising, but I feel like I'm forgetting something obvious.

$\endgroup$
  • 1
    $\begingroup$ Doung and Mauro. The OP knows what you've claimed in your answers. I think you're missing the point of the question. $\endgroup$ – Git Gud Jul 2 '14 at 21:16
  • $\begingroup$ @GitGud dezakin says "I expect I'm doing something wrong in my formulation of my problem, or somehow I evaluated the statements wrong [emphasis added]." Mauro's and my answer clarify that he didn't evaluate anything wrong. $\endgroup$ – Doug Spoonwood Jul 2 '14 at 21:17
  • 1
    $\begingroup$ @DougSpoonwood You have a point there. I agree that you're answering the question partially. But in my understanding the main question is "What is wrong with my intuition to think that this could be possible?". $\endgroup$ – Git Gud Jul 2 '14 at 21:19
  • $\begingroup$ You might have missed that the negation of a conditional implies that the antecedent of the conditional holds true, and the consequent is false. Along with conjunction introduction and equivalence elimination this implies that given the two conditionals you've supplied that the equivalence can't hold (my answer basically relies on this idea). $\endgroup$ – Doug Spoonwood Jul 2 '14 at 21:21
  • $\begingroup$ @GitGud I think my comment explains what is missing from the OP's intuition (most probably the OP doesn't understand what the negation of a conditional implies). The answer I supplied basically relies on what the negation of a conditional implies. $\endgroup$ – Doug Spoonwood Jul 2 '14 at 21:23
4
$\begingroup$

I think you are looking for an example of statements here. That is $\phi, \psi, \chi$ s.t. these properties hold. Let $L=\{\cdot\}$. Let $T=\text{group axioms}\cup \text{there are only twelve distinct elements}$. Now Let $\phi$ say that "I'm is abelian and I'm not is not cyclic" (i.e. $\forall a,b, a\cdot b = b\cdot a$ and a fairly long sentence that says $\neg{\exists{x}\forall{b}, x=b \lor x^2=b \lor\ldots }$). Then let $\psi$ say that "I'm abelian " and let $\chi$ say that "I'm not cyclic". Now these have all the properties you want.

EDIT: Based on what you've said, I think the issue arises because you are thinking in terms of provability as opposed to using a specific models to show counter examples. I'm guessing your contradiction arises by way of saying that $\chi, \psi$ have to be true and $\phi$ has to be false for the conditionals to hold. But then the bi-conditional fails. However your formulation of the problem is not correct.

What you want to say is that $(\chi\not\vdash\phi$ or equivalentely $\not\vdash\chi\rightarrow{\phi}$. But this you have taken to say $\vdash\neg(\chi\rightarrow\phi)$. This is just not true as can be seen from the example.

Edit: The formulation as I see it should be:

$\vdash\phi\leftrightarrow{(\psi\wedge\chi)}$, and $\not\vdash\chi\rightarrow{\phi}$ and $\not\vdash\psi\rightarrow{\phi}$

$\endgroup$
  • $\begingroup$ I think that's what I'm after! I was abusing the notion of propositional calculus for things it wasn't intended for, and ended up with this mess. Time to revisit the text to make sure I fully understand this, and can actually formalize the problem in the correct manner. $\endgroup$ – dezakin Jul 2 '14 at 22:53
  • $\begingroup$ By the way, is the first statement still correct? Can I use biconditional for equivalence or do I need to use entailment there also? $\endgroup$ – dezakin Jul 2 '14 at 23:18
  • $\begingroup$ @dezakin: I think my second edit answers your question $\endgroup$ – UserB1234 Jul 3 '14 at 12:05
  • $\begingroup$ Yes, this is exactly what I was looking for. $\endgroup$ – dezakin Jul 3 '14 at 14:23
1
$\begingroup$

If ¬ (ψ → ϕ), then ψ, and ¬ϕ.

If ¬ (χ → ϕ), then χ, and ¬ϕ.

If ψ, and χ, then (ψ ∧ χ).

If (ψ ∧ χ), and ¬ϕ, then ¬[(ψ ∧ χ)→ϕ].

If [ϕ ⟷ (ψ ∧ χ)], then [(ψ ∧ χ)→ϕ]. Thus,

ϕ ⟷ (ψ ∧ χ), ¬ (ψ → ϕ), and ¬ (χ → ϕ) do not simultaneously hold true.

$\endgroup$
1
$\begingroup$

We have that : $\lnot (ψ \rightarrow ϕ)$ is equivalent to : $\lnot (\lnot ψ \lor ϕ)$ i.e. to :

$ψ \land \lnot ϕ$.

And $\lnot (χ \rightarrow ϕ)$ is equivalent to :

$χ \land \lnot ϕ$.

Thus, there is no way to satisfy both formuale together with :

$ϕ \leftrightarrow (ψ \land χ)$.


Comment

The "problem" in your argument is the bi-implication.

If we state only :

$ϕ \rightarrow (ψ \land χ)$

now the three formulae are simultaneously satisfiable : let $v(ψ)=v(χ)=T$ and $v(ϕ)=F$.

In this case, $ϕ \rightarrow (ψ \land χ)$ is $F \rightarrow (T \land T)$, which evaluates to $T$.

In classical logic : $(A \rightarrow B) \lor (B \rightarrow A)$ [Dummett's law] is a tautology.

Thus, it seeme to me, your argument is :

1) assume $\lnot (A \rightarrow B)$

2) by disjunctive syllogism : $(B \rightarrow A)$ follows.

Thus, by the second and third premises in your argument, we have :

$ϕ \rightarrow ψ$ and $ϕ \rightarrow χ$

and from them, obviously : $ϕ \rightarrow (ψ \land χ)$ follows.

What is wrong with the intuition that :

we couldn't compose a statement of two smaller statements that on their own don't imply $ϕ$ but together are equal to it ?

It seems to me that the we can "reverse" the above expectation :

if $ψ$ does not "licence" to assert $ϕ$ nor $χ$ does, why we expect that "composing" them we are licensed to assert $ϕ$ ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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