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 Feb 11 '15 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$ – Steve Jessop Feb 11 '15 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$ – Mauro ALLEGRANZA Feb 11 '15 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$ – Steve Jessop Feb 11 '15 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$ – Steve Jessop Feb 11 '15 at 10:44
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 Feb 11 '15 at 8:56
  • 1
    $\begingroup$ If $A$ is a set $A^2$ is the set $\{(a,b)|a\in A, b\in A\}$. $\endgroup$ – Henrik supports the community Feb 11 '15 at 9:11
  • 1
    $\begingroup$ @Henrik: See this: math.stackexchange.com/questions/1143284/… $\endgroup$ – idm Feb 11 '15 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 Feb 11 '15 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$ – heinrich5991 Feb 11 '15 at 13:06
  • $\begingroup$ @heinrich5991 Not if the statement $\exists y:\top$ isn't true... $\endgroup$ – 5xum Feb 11 '15 at 13:07
  • $\begingroup$ Right. (min character per comment) $\endgroup$ – heinrich5991 Feb 11 '15 at 13:27
  • $\begingroup$ For this to be so you need to define the existential quantifier extensionally (like a generalized quantifier). $\endgroup$ – Fizz Feb 11 '15 at 15:08
  • 2
    $\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$ – Ilmari Karonen Feb 11 '15 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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.