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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 3 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|cite|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? – user21530 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. – user21530 Aug 24 '13 at 14:36

Your Answer

 
discard

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