Solve Nested Quantifiers Problem #5 - Professor's Handout

[Kingyou123]

Homework Statement

Problem #5,

Homework 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))

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?

 

[andrewkirk]

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))

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$?

 

[Kingyou123]

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$?

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.

 

[Kingyou123]

Would this be correct?

 

[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 realize 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.

 

[Kingyou123]

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 realize 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.

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?

 

[andrewkirk]

So basically I just had to prove when (y^2<x+1) is false,correct?

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)?

 

[haruspex]

that's not correct

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.

 

[andrewkirk]

It looks right to me.

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.

 

[haruspex]

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.

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