First Order Logic: Prove that this equivalence is valid

Printable View

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

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.
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
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