First Order Logic: Prove that this equivalence is valid

"Consider the equivalence

∀x∃yφ(x, y) ↔ ∃y∀x φ(x, y)

You can assume that φ has no free variables other than x and y.

Show that one direction of this equivalence is valid (i.e. true in every structure/model). Prove this carefully."

I have found out that the direction to the "left" is valid.

So I am sure that this is valid: ∃y∀x φ(x, y) → ∀x∃yφ(x, y)

Now I have to prove it by showing that it's true in every structure/model.

Can someone show me how this kind of proof is done?

Re: First Order Logic: Prove that this equivalence is valid

It's important to understand the general idea: if one y make φ true for all x, then for every x there exists its own (in this case, that same) y that makes φ true.

The proof depends on the definition of truth of a formula in a structure, which may vary slightly in different sources. Could you write the parts of the definition for formulas starting with ∀ and ∃?

1 Attachment(s)

Re: First Order Logic: Prove that this equivalence is valid

Attachment 23823

I am not sure if this is what you are thinking of (the two last lines in the image).

The weird looking symbol is supposed to be structure/model.

This is from the book "Logic and Structure" by Dirk van Dalen,

the book that is used in my logic course.

Re: First Order Logic: Prove that this equivalence is valid

The weird-looking symbol is the Fraktur letter A.

My guess is that for every element *a* of the model carrier you consider a new constant $\displaystyle \bar{a}$ and define the truth of formulas in the extended language where these constants are added.

Suppose $\displaystyle \mathfrak{A}\models\exists y\forall x\,\varphi(x, y)$. Then by (vii) there exists an $\displaystyle b\in|\mathfrak{A}|$ such that $\displaystyle \mathfrak{A}\models\forall x\,\varphi(x,\bar{b})$. By (vi) this in turn means that for this particular *b* and for all $\displaystyle a\in|\mathfrak{A}|$ we have $\displaystyle \mathfrak{A}\models\varphi(\bar{a},\bar{b})$. Again by (vii) for all $\displaystyle a\in|\mathfrak{A}|$ we have $\displaystyle \mathfrak{A}\models\exists y\,\varphi(\bar{a},y)$ and by (vi) $\displaystyle \mathfrak{A}\models\forall x\exists y\,\varphi(x,y)$.

It is important to understand why a similar argument cannot be used to show $\displaystyle \mathfrak{A}\models\forall x\exists y\,\varphi(x,y)\to\exists y\forall x\,\varphi(x,y)$. By definition, $\displaystyle \mathfrak{A}\models\forall x\exists y\,\varphi(x,y)$ means that for every $\displaystyle a\in|\mathfrak{A}|$ there exists (its own) $\displaystyle b\in|\mathfrak{A}|$ such that $\displaystyle \mathfrak{A}\models\varphi(\bar{a},\bar{b})$. However, we cannot swap meta-level (i.e., natural language) quantifiers to say that there exists a single *b* such that $\displaystyle \mathfrak{A}\models\varphi(\bar{a},\bar{b})$ for all *a*. Therefore, we cannot say $\displaystyle \mathfrak{A}\models\forall x\,\varphi(x,\bar{b})$: there is no such single *b*; each *b* exists only when *a* is given.

Re: First Order Logic: Prove that this equivalence is valid

You **can't** prove it for the very good reason that it is not true. For example, take $\displaystyle \phi(x, y)$ be the statement [itex]x+ y= 0[itex]. Then the left side, that "for any x, there exist y such that x+ y= 0" is true: whatever x is take y= -x. But the right side say "there exist a y such that, for all x, x+ y= 0. But that is NOT true. For any given y, there exist an x such that x+ y= 0 but it is not true for **all** x.

Re: First Order Logic: Prove that this equivalence is valid

Quote:

Originally Posted by

**HallsofIvy** You **can't** prove it for the very good reason that it is not true. For example, take $\displaystyle \phi(x, y)$ be the statement [itex]x+ y= 0[itex]. Then the left side, that "for any x, there exist y such that x+ y= 0" is true: whatever x is take y= -x. But the right side say "there exist a y such that, for all x, x+ y= 0. But that is NOT true. For any given y, there exist an x such that x+ y= 0 but it is not true for **all** x.

What is not true?

This is not true: ∀x∃yφ(x, y) ↔ ∃y∀x φ(x, y)

But this should be a valid statement (the one direction in the statement above):

∃y∀x φ(x, y) → ∀x∃yφ(x, y)

That's what I figured out, and when it's true or valid, it can be proved

Re: First Order Logic: Prove that this equivalence is valid

Yes, ∃y∀x φ(x, y) → ∀x∃yφ(x, y) is valid, but ∀x∃yφ(x, y) → ∃y∀x φ(x, y) is not.

Re: First Order Logic: Prove that this equivalence is valid

Quote:

Originally Posted by

**emakarov** Yes, ∃y∀x φ(x, y) → ∀x∃yφ(x, y) is valid, but ∀x∃yφ(x, y) → ∃y∀x φ(x, y) is not.

Ye, it's actually a b-part of this problem and that is to find

a counterexample for the direction that is not valid, which I have

already completed.

The proof you just wrote looks really familiar with something I had

in the class, but what you wrote is far more understandable, and

that's a good thing! :D