1

For each of the following claims, state whether it is true or false. If an assertion is true, either give a carefully reasoned argument to show that it is true, or prove it formally. If an assertion is false, give an appropriate counterexample, consisting of an interpretation for predicates that satisfies one formula and falsifies another in a way that violates the assertion.

(a) ∃x (A(x) → B(x)) logically implies ∃x (B(x) → A(x)),

(b) ∃x A(x) → ∃y B(y) is logically equivalent to ∃y ∀x (A(x) → B(y)),

(c) ∃x (A(x) ↔ B(x)) ∧ ∀x B(x) is logically equivalent to ∀x A(x) ∧ ∀x B(x),

I'm having trouble explaining myself, for (a) I believe it is false because if A(x) is False and B(x) is True then the entire statement is false For (b) and (c) I am having issues figuring out it's truth value, also, in general, I'm stuck on proving these claims when it is true. Could you please explain how (b) and (c) are true are false?

Helpsun
  • 43

1 Answers1

0

You're correct by (a), you could choose $A$ and $B$ that doesn't depend on it's variable as you did.

(b) True:

It follows from the fact that $\phi\rightarrow\psi$ is the same as $\neg\phi\lor\psi$ and $\neg\exists x A(x)$ is the same as $\forall x\neg A(x)$ then one could just put that together and get:

$\exists x A(x) \rightarrow \exists y B(y) \Leftrightarrow \neg\exists x A(x) \lor \exists y B(y) \Leftrightarrow \forall x \neg A(x) \lor \exists y B(y) \Leftrightarrow \exists y \forall x (\neg A(x) \lor B(y)) \Leftrightarrow \exists y \forall x (A(x) \rightarrow B(y))$

(c) is false, if $B$ is universally true, but $A$ is only true for a select x (for example $A(x)$ is $x=0$), then there definitely exists an $x=0$ such that $A(x) \leftrightarrow B(x)$ and therefore $\exists x(A(x) \leftrightarrow B(x)) \land \forall x B(x)$, but the right formula is false because $\forall x A(x)$ isn't true.

skyking
  • 16,654