Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Well, I proved that $\forall b \forall c (b^2 - 4c \geq 0 \rightarrow \exists x(x^2 + bx + c = 0))$. This implies that $\forall b \forall c (\neg \exists x(x^2 + bx + c = 0) \rightarrow b^2 - 4c < 0)$, so $\forall b \forall c \forall x ((x^2 + bx + c \neq 0) \rightarrow b^2 - 4c < 0)$. Applying the last statement to $b=2, c =1$, and $x=0$, we get $1 \neq 0 \rightarrow 0 < 0$. Since $1 \neq 0$, $0 <0$. But this is impossible. How could I express this relationship between $x^2+bx+c$ and discriminant using quantificational logic?

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

You need $(\forall x.\ x^2+2x+1 \neq 0) \to 0 < 0$ which is equivalent to $(\forall x.\ (x+1)^2 \neq 0) \to 0 < 0$ which leads to $\mathtt{false} \to 0 < 0$ which is true.

The problem is that $$\forall b,c,x.\ P(b,c,x) \to Q(b,c)$$ is not equivalent to $$\forall b,c.\ (\forall x.\ P(b,c,x)) \to Q(b,c).$$

I hope this helps $\ddot\smile$

share|improve this answer
    
Yes, your answer helped a lot. Is it true that if $\forall b,c,x.\ P(b,c,x) \to Q(b,c)$ then $\forall b,c.\ (\forall x.\ P(b,c,x)) \to Q(b,c)$? How can we prove that they are not equivalent? Any hint? –  Stavros Aug 24 '13 at 14:18
1  
@Stavros Well, your doubt with this question already provides a nice counterexample, doesn't it? Some other artificial counterexample might be like $(\forall x.\ P(x)) \to (\forall y.\ P(y))\ \not\!\!\!\implies \forall x. P(x) \to (\forall y.\ P(y))$. Set the universe $\Omega = \{\mathtt{a},\mathtt{b}\}$ and $P = \chi_{\{\mathtt{a}\}}$. Now $\forall z.\ P(z)$ is false, because $\neg P(\mathtt{b})$, so the first implication would be $\mathtt{false} \to \mathtt{false}$ (true), but the other one would not work because $P(\mathbb{a}) \to \forall y.\ P(y)$ is $\mathtt{true} \to \mathtt{false}$. –  dtldarek Aug 24 '13 at 14:21
2  
@Stavros For the first question, $\forall x. P(x) \to Q$ does imply $(\forall x. P(x)) \to Q$ if the universe is non-empty (I'm assuming that $x$ is not free in $Q$ so the latter formula makes sense). For the empty universe $\forall x. (whatever)$ is always true, while the latter might be $\mathtt{true} \to \mathtt{false}$ if $Q \equiv \mathtt{false}$. For the non-empty universe, $\forall x.\ P(x)$ implies that $\exists x.\ P(x)$ and using the very first formula we can infer $Q$. –  dtldarek Aug 24 '13 at 14:30
    
Great answers! Thanks, I understand now. –  Stavros Aug 24 '13 at 14:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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