# First Order Logic: Prove that this equivalence is valid

• May 9th 2012, 09:54 AM
Zhai
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?

• May 9th 2012, 10:26 AM
emakarov
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 ∃?
• May 9th 2012, 11:24 AM
Zhai
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.
• May 9th 2012, 12:38 PM
emakarov
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 $\bar{a}$ and define the truth of formulas in the extended language where these constants are added.

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

It is important to understand why a similar argument cannot be used to show $\mathfrak{A}\models\forall x\exists y\,\varphi(x,y)\to\exists y\forall x\,\varphi(x,y)$. By definition, $\mathfrak{A}\models\forall x\exists y\,\varphi(x,y)$ means that for every $a\in|\mathfrak{A}|$ there exists (its own) $b\in|\mathfrak{A}|$ such that $\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 $\mathfrak{A}\models\varphi(\bar{a},\bar{b})$ for all a. Therefore, we cannot say $\mathfrak{A}\models\forall x\,\varphi(x,\bar{b})$: there is no such single b; each b exists only when a is given.
• May 9th 2012, 12:52 PM
HallsofIvy
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 $\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.
• May 9th 2012, 01:06 PM
Zhai
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 $\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
• May 9th 2012, 01:09 PM
emakarov
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.
• May 9th 2012, 01:22 PM
Zhai
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

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