3
$\begingroup$

At first English is not my native language if something is not perfectly formulated or described I'm sorry.

Could somebody please tell me what the generally valid statement of this is?

$$ \forall x(\exists y(A(x))) $$

I personally believe that it could mean something like

Forall x there is one y that I get when i put x into A(x)

$\endgroup$
6
  • 1
    $\begingroup$ Contrarily to some of the answers below, I don't think this is strange at all. Consider $f\colon \mathbb R^2\to \mathbb R, (x,y)\mapsto x$ and let $A(x)$ be the predicate $f(x,y)=0$, or equivalently $x=0$. Then the statement says that for every first coordinate, you can find a second coordinate such that the ordered pair formed by them is a zero of the function. There is no zero of $f$ if you don't have an ordered pair. And of course what I said isn't completely right because $f(x,y)=0$ and $x=0$ are different predicates, but hopefully this examples provides some peace of mind. $\endgroup$
    – Git Gud
    Commented Feb 11, 2015 at 9:44
  • 3
    $\begingroup$ @GitGud: it's just the notation that's strange, to write $A(x)$ as a replacement for a formula that has $y$ free. And then because it says $\exists y$ instead of $\forall y$ we're sort of led to assume the value of $y$ is going to be significant somehow, which in your example it is not. That said, strange statements sometimes appear in the middle of proofs because we need the $\exists y$ in order to apply some rule or theorem. Perhaps $y$ is important in the general case but not to our specific case :-) $\endgroup$ Commented Feb 11, 2015 at 10:25
  • 1
    $\begingroup$ @SteveJessop - The notation is not "strange" at all... we can agree that it is "useless" in any "reasonable" context, but you have to think to the formal specification. First, we define formula (i.e. we have the recursive syntactical specification of a "well formed" expression) and then we can define what means for a variable $x$ to occur free in a formula. If we want to restrict the definition of formula only to the case of "not empty" quantification, we have have already the definition of free occurrence of a variable, and I think that it can be quite hard to do ... $\endgroup$ Commented Feb 11, 2015 at 10:32
  • 2
    $\begingroup$ @MauroALLEGRANZA: this may just be a use of language thing, but I think it would be strange to do something that's useless in any reasonable context. Unless you're in an unreasonable context of course, then suddenly all becomes clear, but the questioner doesn't state the context which is why it looks strange to people. I'm not saying it's required that $A(x)$ be used only when $x$ is the only variable free in the formula thereby represented. I'm saying that the cases where that's not true are strange. $\endgroup$ Commented Feb 11, 2015 at 10:42
  • 2
    $\begingroup$ ... on the strangeness spectrum, consider also $\forall x \exists y A$. Now we have no idea what (if any) variables are free in $A$, but at least we know that we don't know, the notation isn't leading us anywhere :-) $\endgroup$ Commented Feb 11, 2015 at 10:44

3 Answers 3

7
$\begingroup$

For all $x$, there exist an $y$ such that the property $A$ is true on $x$. But this is strange since $y$ is not used... Maybe the statement should be: $$\forall x, \exists y, A(x,y).$$

which means: for all $x$, there exist an $y$ such that the property $A$ is true on the pair $(x,y)$.

For example, if your property is $A(x,y) \Leftrightarrow x+y = 0$, then the statement $\forall x, \exists y, A(x,y)$ is true. Indeed, for all $x$, choosing $y = -x$ makes $A(x,y)$ true.

$\endgroup$
4
  • 2
    $\begingroup$ I think your propably right I will talk to my teach propably he made an error because there is an "," in the A(x) but nothing behind it. Do you maybe also know what A^2 means if A is a set? $\endgroup$
    – Akkyen
    Commented Feb 11, 2015 at 8:56
  • 1
    $\begingroup$ If $A$ is a set $A^2$ is the set $\{(a,b)|a\in A, b\in A\}$. $\endgroup$ Commented Feb 11, 2015 at 9:11
  • 1
    $\begingroup$ @Henrik: See this: math.stackexchange.com/questions/1143284/… $\endgroup$
    – idm
    Commented Feb 11, 2015 at 9:32
  • $\begingroup$ @Akkyen I will be very, very surprised if there's a typo. This kind of formula is very common exactly because its purpose is to show that it can be done. $\endgroup$
    – Git Gud
    Commented Feb 11, 2015 at 9:32
5
$\begingroup$

The way your statement is written now, it simply means:

For all values of $x$, there exists such a value of $y$ that $A(x)$ is true.

This is a strange, but technically completely correct statement, which is always equivalent to the statement

$$\forall x: A(x)$$

$\endgroup$
6
  • $\begingroup$ $\forall x \exists y: A(x) \iff \forall x: A(x)$ $\endgroup$ Commented Feb 11, 2015 at 13:06
  • $\begingroup$ @heinrich5991 Not if the statement $\exists y:\top$ isn't true... $\endgroup$
    – 5xum
    Commented Feb 11, 2015 at 13:07
  • $\begingroup$ Right. (min character per comment) $\endgroup$ Commented Feb 11, 2015 at 13:27
  • $\begingroup$ For this to be so you need to define the existential quantifier extensionally (like a generalized quantifier). $\endgroup$ Commented Feb 11, 2015 at 15:08
  • 3
    $\begingroup$ @heinrich is correct: $\forall x \exists y: A(x) \iff \forall x: A(x)$, because for each $x$ we may always choose $y = x$. (If the universe is empty, so that $\exists y: \top$ is not true, then every universally quantified statement is vacuously true anyway.) $\endgroup$ Commented Feb 11, 2015 at 16:24
3
$\begingroup$

The details may vary according to the syntactical specifications of the language but, in general, nothing forbid to have $\exists y A(x)$ when $y$ is not free in $A(x)$; the usual recursive definition of formula in FOL is :

(i) if $t_1,\ldots,t_n$ are terms and $P^n$ is an $n$-ary predicate symbol, then $t_1=t_2$ and $P^n(t_1,\ldots,t_n)$ are atomic formulae;

(ii) if $\varphi$ is a formula, then $\lnot \varphi$ is a formula;

[...]

(iv) if $\varphi$ is a formula, then $\forall x \varphi$ and $\exists x \varphi$ are formulae.


Intuitively, if $y$ is not free in $\alpha$, then $\forall y \alpha$ and $\exists y \alpha$ have the "same meaning" of $\alpha$.

We can prove it "formally" showing that :

if $y$ is not free in $\alpha$, then $\vDash \alpha \leftrightarrow \forall y \alpha$,

i.e. $\alpha$ and $\forall y \alpha$ are logically equivalent, and the same for $\exists y \alpha$.


We can apply the above result to : $∀x(∃y(A(x)))$ and we get that it is equivalent to : $∀x(A(x))$.

The semantical specifications for the quantifiers are [according to Herbert Enderton, A Mathematical Introduction to Logic (2nd - 2001)), page 83-84] :

We say that a structure $\mathcal A$ satisfy a formula $\varphi$ with an assignment function $s$, in symbols : $\mathcal A \vDash \varphi [s]$, when :

[...]

$\mathcal A \vDash \forall x \varphi[s]$ iff for every $d \in |\mathcal A|$, we have $\mathcal A \vDash \varphi[s(x|d)]$

and :

$\mathcal A \vDash \exists x \varphi[s]$ iff for some $d \in |\mathcal A|$, we have $\mathcal A \vDash \varphi[s(x|d)]$.

Thus, consider a structure $\mathcal A$ and a function $s$ and apply the above definition; $\mathcal A$ satisfies $\forall x (\exists y A(x))$ with $s$ if

$\mathcal A \vDash \exists y A(x)[s(x|d)]$, for every $d \in |\mathcal A|$.

And this, in turn, means :

$\mathcal A \vDash A(x)[s(x|d)(y|e)]$, for every $d \in |\mathcal A|$ and some $e \in |\mathcal A|$.

But the variable $y$ does not occurr free in $A(x)$ and thus it does not matter what is the "denotation" that $s(x|d)$ assign to it. So we can discard $e$ and we have :

$\mathcal A \vDash A(x)[s(x|d)]$, for every $d \in |\mathcal A|$,

and this amounts to : $\mathcal A \vDash \forall x A(x)[s]$.

$\endgroup$

You must log in to answer this question.

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