3

Do the statements $$(∀x∈A)(∃y∈B)(x≤y)$$ and $$(∃y∈B)(∀x∈A)(x≤y)$$ mean the same, even though the first two brackets are reversed?

P.S: Lets say, I have a sentence: There is no number from A, so it would be bigger than all numbers from B.

Ella
  • 89
  • 2
    No, in general, two statements of the form $(\forall x \in A)(\exists y \in B)\phi$ and $(\exists y \in B)(\forall x \in A)\phi$ are not equivalent -- the second is stronger than the first. Compare $\forall x \exists y \phi$ "For every tupperware box there is a lit that fits it" (hopefully true) vs. $\exists y \forall x \phi$ "There is a lid that fits every tupperware box" (unfortunately false). https://math.stackexchange.com/a/3145676/344246 – Natalie Clarius Aug 19 '19 at 10:00
  • 1
    I will check it. thanks – Ella Aug 19 '19 at 10:05
  • 1
    Re. your previous comment: They never mean the same thing, it might just be that they are coincidentally both true or both false in particular instances (for particular formulas $\phi$ in particular structures) -- but as pointed out in the answers, we can find structures such that the first of your formulas is true whereas the second is false, so no, neither in this case are they equivalent. – Natalie Clarius Aug 19 '19 at 10:09

5 Answers5

5

Nope they're not the same. In general, the meaning changes when permuting different quantifiers (however $(\forall x\in A)(\forall y\in B)$ and $(\forall y\in B)(\forall x\in A)$ are the same, and same holds for $\exists$).

To see why the two statements you gave have different meanings, start by translating them to English: the first one says "For every element of $A$ there is an element of $B$ larger than it" while the second says "There is an element of $B$ larger than every element of $A$". Notice that second implies the first, but not the first doesn't imply the second.

Now you should try to find an example of $A$ and $B$ subsets of, say, $\mathbb R$, such that the first statement holds but not the second.

Scientifica
  • 8,781
  • How do you get this kind of translations? – Andrew Svietlichnyy Aug 19 '19 at 18:04
  • @AndrewSvietlichnyy $\forall$ translates to "For every" and $\exists$ translate to "there exists", $\in$ translates to "in", etc.. Of course, in human language, there can be many translations: saying "there is an element of $A$" is the same as saying "some element of $A$". – Scientifica Aug 19 '19 at 21:21
  • My question isn't about that. I wonder how do "for every x there is y" and "there is y for every x" end up being translated so differently. Translation isn't helpful because it's based on understanding the difference. – Andrew Svietlichnyy Aug 20 '19 at 16:35
  • @AndrewSvietlichnyy Sorry I didn't understand your question. Could you please explain more? Looking at the translation I gave, I was kind of "not rigid enough" like when translating $(\exists y\in B) (\forall x\in A) y>x$ to "There is an element of $B$ larger than every element of $A$". I guess translating it to "There is an element $y$ of $B$ such that for every element $x$ of $A$, $x$ is smaller than $y$" is more "automatic". Then English speakers know that saying "for every element $x$ of $A$, $x$ is smaller than $y$" is the same as "every element of $A$ is smaller than $y$", etc.. – Scientifica Aug 20 '19 at 16:40
  • There are certainly issues with human language when it comes to formal logic. However, doing such translations is not only done for describing mathematics using human language, but also to "feel" the notions and "feel" the difference between both statements. – Scientifica Aug 20 '19 at 16:42
4

These two statements do not mean the same thing. Let $A,B = \mathbb{N}$.

The first statement is true: for any $x \in \mathbb{N}$ we can take $y=x+1$.

The second statement is false; there is no upper bound for the natural numbers.

Samuel Bodansky
  • 493
4

Example: let $A=B= \mathbb R$ and $" \le "$ be the usual order on $ \mathbb R.$

If $x \in A$, then $y:=x+1 \in B$ and $x \le y.$

Hence we have $(\forall x \in A)(\exists y \in B)(x \le y)$.

But $(\exists y \in B)(\forall x \in A)(x \le y)$ means that $ \mathbb R$ is bounded from above.

Shervin Sorouri
  • 2,359
Fred
  • 77,394
2

$A=B=(0,1)$ is a counterexample.

Kavi Rama Murthy
  • 311,013
2

As Scientifica mentions in their answer, translating the logical statement to a sentence helps. If you can simplify the sentence towards more natural language, do so. Moreover, it is often instructive to to consider a special case. And even better, combine the two and write sentences about a special case.

If $A=B=\mathbb N$, then the statements are:

  1. $(∀x∈A)(∃y∈B)(x≤y)$ — "for any natural number, there is a number that is at least as big"
  2. $(∃y∈B)(∀x∈A)(x≤y)$ — "there is a biggest natural number"

Written this way, the problem is pretty easy. And that is often hard in math: rewriting a problem so that it becomes easy. That can be hard!

This should also help you get a flavor of what might happen with more general sets $A$ and $B$. Once you have a feel for the phenomenon from an example, more general cases are easier to make sense of.

If you have trouble figuring out why these are correct translations, let me know and I can give details.

You gave this sentence: "There is no number from A, so it would be bigger than all numbers from B." This is literally $\neg(∃x∈A)(∀y∈B)(x>y)$. Using the basic rules of negations and quantifiers, this can be seen to be equivalent with $(∀x∈A)(∃y∈B)(x≤y)$.

Indeed, only the first symbolic logical statement expresses the idea you have written in words. If you end up with two candidates and are unsure like in this question, spelling them both out in natural language helps.

Joonas Ilmavirta
  • 25,809
  • Thank you! Considering the sentence i have given, namely "There is no number from A, so it would be bigger than all numbers from B" only first one expresses that? – Ella Aug 19 '19 at 18:28
  • @Telaa I'm glad to be able to help! I updated the answer; see below the line. – Joonas Ilmavirta Aug 19 '19 at 18:37
  • thanks again! my last question is, if i have that statement you have given: ¬(∃x∈A)(∀y∈B)(x>y), do i not have to close it with another pair of brackets: ¬((∃x∈A)(∀y∈B)(x>y)) so i would get a final result? – Ella Aug 19 '19 at 19:17
  • @Telaa That is a matter of convention. I'd say you don't have to but your textbook might say otherwise. Adding extra parentheses doesn't hurt, so nobody will tell you they're forbidden. To avoid confusion when learning, stick to whatever you're being taught. Time for more relaxed notation comes after mastery of the basics. – Joonas Ilmavirta Aug 19 '19 at 19:23