0

Working on basic first-order logic for uni, I have been given the answers to an assignment which I don't agree with.

Question: Which of these formulas is equivalent to ∀x∃y(Bx → Cy)?
a) ∃xBx → ∃yCy
b) ∀xBx → ∃yCy

I say a), the answer sheet says b).

My logic is:

∀x∃y(Bx → Cy) = ∀x∃y(¬Bx v Cy)
              = ∀x(∃y¬Bx v ∃yCy)
              = ∀x(¬Bx v ∃yCy)
              = ∀x(¬Bx) v ∃yCy
              = ¬∃xBx v ∃yCy
              = ∃xBx → ∃yCy

Could someone please confirm if I'm right or where my reasoning fails?

user2891462
  • 125

2 Answers2

1

I believe you are right and your derivation is correct.

As a double-check, I am thinking of a model in which the given formula is not equivalent to (b). Let's say:

  • $x$ and $y$ are integers,
  • $Bx$ means something that is true for some, but not all integers, e.g. "$x$ is even", and
  • $Cy$ means something impossible, e.g. "$y^2<0$".

Then:

  • $\forall x\exists y(Bx\to Cy)$ is not satisfied (e.g. $x=0$ does not give any example of $y$ for which $Bx\to Cy$ is satisfied, because $Cy$ is always false)
  • $\forall x Bx \to \exists y Cy$ is satisfied because the antecedent $\forall x Bx$ is not satisfied (not all integers are even).
1

You are right.

See Prenex normal form.

We have that $\exists x(\phi(x) \rightarrow \psi )$ is equivalent to $(\forall x\phi(x))\rightarrow \psi$, where $x$ does not appear free in $\psi$.

But we have that $\exists x(\phi \rightarrow \psi )$ is equivalent to: $\phi \rightarrow (\exists x\psi )$, when $x$ does not appear free in $\phi$.

And we have that $\forall x(\phi \rightarrow \psi )$, is equivalent to: $(\exists x\phi )\rightarrow \psi$, with $x$ not free in $\psi$.

Your formula has $∃y(Bx → Cy)$, that is equivalent to: $(Bx → ∃yCy)$.

And then apply $\forall x$ to get:

$(∃xBx → ∃yCy)$.

Mauro ALLEGRANZA
  • 94,169