0
$\begingroup$

Suppose $Pxy$ is a $2$-ary predicate and $\phi$ is just some fixed arbitrary predicate form.

  1. $\forall x [ (\exists y Pxy) \longrightarrow \phi ]$

  2. $\forall x \exists y [Pxy \longrightarrow \phi]$

Is the only difference between 1. and 2. in the case where $\exists y$ is not true? i.e. We may be in an interpretation $\mathcal{I}$ where the universe/domain of discourse may be empty, so does that then make 1. true and 2. false?

So it seems to me that if we restrict ourselves to interpretations $\mathcal{I}$ whose domain of discourse is not empty then 1. and 2. are logically equivalent$^1$.


Remarks: $^1$I'm thinking of the interpretations in the context of first-order logic, but what about second-order logic or other higher orders of logic? (Though I have not studied anything beyond first order logic, but maybe someone can say something about this? But this probably is another question in its own right)

$\endgroup$
1

2 Answers 2

3
$\begingroup$

Hint

The two are not equivalent.

Consider an interpretation with domain $\mathbb N$ and let $\phi := (0=1)$ (or any other formulas which is False).

Then interpret $Pxy$ with $x < y$.

In this interpretation, 1. will be $∀x[∃y(x < y) ⟶ (0=1)]$, which is False, while 2. is $∀x∃y[(x < y) ⟶ (0=1)]$, which is True.

$\endgroup$
1
  • $\begingroup$ Thanks for this! I just realised after reading your hint that what I wrote above is vacuously true for both 1. and 2 and because of that, after thinking about these predicate forms I happen to have another question in relation to them. See math.stackexchange.com/questions/4143026/… if interested. $\endgroup$
    – tcmtan
    May 18, 2021 at 11:12
0
$\begingroup$

Another way of understanding the difference between the two formulas is to translate them into natural language. Its easier to see the difference if you drop the "for any x" part for a moment. The first formula is saying "if there is a y such that P(x,y) then phi" vs. the second formula is "there is a y, such that if P(x,y) then phi"

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .