2

The specific problem I have is $\forall x\in[0,1), \exists y\in[0,1) \ $ such that $ x<y$. But I think this can be generalized to for all x, there is a y such that Q, where Q is a statement like x

So how would I approach this? I think y needs to be expressed as a limit when y approaches 1. Unfortunately, I do not know how to express this.

Going back to the "generalized" form, what would be the way to approach such a problem? What I mean is if, instead, we have $\exists y\in[0,1), \forall x\in[0,1)\ $, we would just pick a y and easily prove x, so is there some sort of strategy like this for this form?

user2793618
  • 49
  • Generally, $\forall x\exists y$ is less restrictive than $\exists y\forall x$. For the continuation $\ldots x<y$, one is true and the other isn't (at least when $x,y\in[0,1)$). – Arthur Aug 26 '18 at 17:21
  • What do you mean by less restrictive? Any articles I can read? ELI5? – user2793618 Aug 26 '18 at 17:28
  • What actually is this $Q$? You introduce in a sentence without an ending. – Angina Seng Aug 26 '18 at 17:56
  • 1
    1)$\forall x\exists y$ means that for any $x$ you must find a $y$ that works for that single particular $x$. 2)$\exists y\forall x$ means you must find a $y$ then works for every possible $x$. Since for 1) you must only find an $y$ for a specific $x$ and in 2) you must find a $y$ for every possible $x$ 1) is "less restrictive" (and much easier to prove). Consider $Q$ is $x =y$. For all $x$ there is a $y$ so that $x = y$ (that's obviously true; just let $y = x$). There exists a $y$ so that for all $x$ then $x = y$ is obviously false. There's no $y$ that is equal to everything. – fleablood Aug 26 '18 at 20:02
  • I see; I based my assumption on $\exists y \in \mathbb R$ s.t $\forall \in [0,2], x^2+1<y$. In this case, I just picked a very large y. For $\forall x \exists y$, you still need to make x a generic x right? You can't just pick a number, so that means y will likely be an expression right? – user2793618 Aug 27 '18 at 00:33

2 Answers2

2

$\forall x\in[0,1), \exists y\in[0,1) \ $ such that $ x<y$

Hint:   prove that $\, x \lt (x+1)/2 \lt 1\,$ for $\,\forall x\in[0,1)\,$. Intuition here is that $\,(x+1)/2\,$ is the midpoint between $\,x\,$ and $\,1\,$.

if, instead, we have $\exists y\in[0,1), \forall x\in[0,1)\ $

That does not hold true, consider for example $\,x=(y+1)/2\,$.

dxiv
  • 76,497
  • So for $\forall x \in [a,b], \exists y \in [a,b]$ you want to find a formula for y that satisfies the condition Q, e.g, x < y? – user2793618 Aug 27 '18 at 00:19
  • How do I prove the midpoint? – user2793618 Aug 27 '18 at 03:50
  • @user2793618 So for ∀x∈[a,b] ... No, note that the interval $[0,1)$ is open at the right end. That is essential here, otherwise the statement would no longer hold true if you replaced $[0,1)$ with the closed interval $[0,1]$. Think about $x=1$ for example. How do I prove the midpoint One way is to start with $x \lt 1$, then the distance between $x$ and $1$ is $1-x$ and the midpoint is the left end plus half the distance i.e. $x + (1-x)/2 = (x+1)/2,$. – dxiv Aug 27 '18 at 04:28
  • Sorry about the typo. The question was just about in general if you have an universal quantifier binding x followed by a existential quantifier for y, you want to find a formula for y right? – user2793618 Aug 27 '18 at 04:33
  • 1
    @user2793618 Proving something like $\exists y$ doesn't always require finding a formula for $y$, but if you are able to find one then that's always sufficient. – dxiv Aug 27 '18 at 04:35
1

You have it backwards.

$\forall x, \exists Y$ is is usually much easier to prove and you do it by simply " just pick a $y$" and showing it exist.

For instance if $Q$ is $x <y $ then just "pick" $y; x < y < 1$... say $y = \frac {1+x}2$.

Or if for instance $Q$ is $x = y$ then just "pick" $y = x$.

$\exists Y \forall x$ is much harder to prove because you must pick a $y$ that is true for ALL $x$ and not just a single $x$.

If $Q$ is $x < y$ then you can't prove $\exists Y \in [0,1)\forall x \in [0,1)$ because it simply is not true! For any $y$ that you pick, then there will always be an $x; y < x < 1$ and it will NOT be true that $x < y$.

And if $Q$ is $x =y$ that is especially clear that $\exists y\forall x$ that $x = y$. For $x = \frac 14$ and for $x = \frac 12$ there is no possible $y$ so that $y$ is equal to both $\frac 14$ and $\frac 12$.

fleablood
  • 124,253
  • So while you pick a single x for the universal quantifier, you will likely need to express y in terms of a formula/expression right (x needs to represent all x)? – user2793618 Aug 27 '18 at 01:29