1. Feb 2, 2016

Kingyou123

1. The problem statement, all variables and given/known data
Problem #5,

2. Relevant equations
Professor's handout, to show that this false: Show that for some x∈X there is no way to choose y∈Y such that P(x,y) is true. That is showΓ(∃x∃yP(x,y)) whic is equivalent to ∃x∀y(ΓP(x,y))
3. The attempt at a solution
So far I have appilied this definition, but my professor hasn't given me an example to follow to solve this... Would I have to solve the second part?

Last edited by a moderator: Feb 3, 2016
2. Feb 2, 2016

andrewkirk

that's not correct.
The statement we want to show false is $\forall x\exists y(y^2<x+1)$, which is equivalent to $\neg\exists x\neg\Big(\exists y(y^2<x+1)\Big)$.

The negation of that is $\exists x\neg\Big(\exists y(y^2<x+1)\Big)$.

Can you find such an $x$?

3. Feb 2, 2016

Kingyou123

So if we make (y^2<x+1) true than the Γ will make it false, correct? Like if I plug in 1 for x and y.

4. Feb 2, 2016

Kingyou123

Would this be correct?

5. Feb 2, 2016

andrewkirk

No that is not correct. Your step from the first to second line is invalid. In symbolic logic, you should always write the formal justification for each step. If you apply that discipline you will in most cases realise without assistance when you make an invalid step.
Go back to my previous post, look at the last logical proposition, and think about what value of $x$ would satisfy $\neg\Big(\exists y(y^2<x+1)\Big)$ where the domain is the real numbers. It's actually very easy.

6. Feb 3, 2016

Kingyou123

Okay, I already turned it in. So basically I just had to prove when (y^2<x+1) is false,correct? So if I set x to 2 and y to 2, I would get 4<3 therefore making the statement false. The thing that confuses me is the not symbol, so it I made the statement false it would be not false, so true?

7. Feb 3, 2016

andrewkirk

No. What you have to do is find a value of $x$ such that, for all $y$, $y^2$ is not less than $x+1$, ie that $y^2$ is more than or equal to $x+1$. You cannot choose a single $y$. The result has to hold for all $y$.
Can you think of a number that all squares of real numbers are more than or equal to (but, by the way, not all squares of complex numbers)?

8. Feb 3, 2016

haruspex

It looks right to me.
In your last step in post 2 you had ....~∃y(P(x,y)). That converts to ...∀y(~P(x,y)) to get the form in the OP.
Which form is more readily proven is another matter.

9. Feb 3, 2016

andrewkirk

The first step is invalid. It selects specific values for $x$ and $y$, which is only valid if those variables are universally quantified (using the Axiom Schema of Specification). They are existentially quantified.

Last edited: Feb 3, 2016
10. Feb 3, 2016

haruspex

Ok, I thought you were objecting to the last part.
I suspect the erroneous statement was a typo for ∃x(~∃y( etc.