MHB Is the Statement True or False?

  • Thread starter Thread starter skate_nerd
  • Start date Start date
  • Tags Tags
    Standard
AI Thread Summary
The discussion centers on two mathematical statements involving real numbers and their truth values. The first statement, asserting that for every real number \(x\), there exists a real number \(y\) such that \(x+y>0\), is deemed true, with the reasoning that choosing \(y=|x|+1\) satisfies the condition. The second statement, which claims there exists a real number \(x\) such that for all real numbers \(y\), \(x+y>0\), is considered false, as no single \(x\) can satisfy the inequality for every possible \(y\). The importance of the order of quantifiers in logical statements is emphasized, illustrating how the first statement allows for flexibility in choosing \(y\) based on \(x\), while the second requires a fixed \(x\) that must work universally for all \(y\). This highlights the complexity of quantifier interactions in mathematical logic.
skate_nerd
Messages
174
Reaction score
0
Studying for my proofs final right now...there's a problem on the study guide:
True or False. Assume standard properties of real numbers. Support your answers.

(a) For all \(x\) in the real numbers, there exists a \(y\) in the real numbers such that \(x+y>0\).
The answer: True. Given an \(x\), take \(y=|x|+1\).

(b) There exists some \(x\) in the real numbers such that for all \(y\) in the real numbers, \(x+y>0\).
The answer: False. There is no single \(x\) that can "accommodate" all \(y\)'s.

I understand how the first answer makes sense, because taking \(y=|x|+1\) would give you \(x+|x|+1>0\). For any \(x<0\), we would have \(1>0\). Any \(x>0\) would clearly give something more than 1.
However when looking at part (b), I feel like it is exactly the same thing as part (a), except the variable \(x\) is now the constant and the constant \(y\) is now the variable. So why would it not be valid to say:
"True: Given a \(y\), take \(x=|y|+1\)"?
 
Physics news on Phys.org
You have to take the order of quantifiers into account. That this order matters should be clear from the difference between "Every person has a friend" and "There is a person who is everyone's friend". Indeed, let $F(x,y)$ mean that $x$ and $y$ are friends. We can even assume that $F$ is symmetric, just like $x+y>0$ is, though this is not important. Then the first statement says
\[
\forall x\exists y\,F(x,y)\tag{1}
\]
while the second one says
\[
\exists x\forall y\,F(x,y)\tag{2}
\]
It is clear that (1) is usually true; at least it is easy to find a group of people ("the universe of discourse") where it is true. In contrast, (2) is less likely to be true for large groups of people, and it is easy to find a counterexample, such as a circle of people where only neighbors are friends. You can probably figure out that (2) implies (1) for any symmetric $F$, but the converse is not true, as we have just shown.

The gist lies in the order of choices that are made during the interpretation of a statement with quantifiers. This interpretation can be viewed as a construction game between two players $A$ and $E$: the forces of nature (or chaos) and a constructive agent (or a human). Player $A$ throws at $E$ all kinds of circumstances, and $E$ has to take them into account while building the desires structure. Then in general who has the winning strategy depends crucially on who makes the first move. For example, consider building and maintaining a highway. For every local damage that is done by weather or wildlife, humans are able to reverse it by fixing that damage. So, if the goal of the game is to have a highway in good order, humans have a winning strategy in the game where they move second. However, it is probably unrealistic to construct a highway that nature cannot damage in some way..

Why is making the second move easier for player $E$? Because $E$ knows the result of the first move by $A$ and can respond correspondingly. What does this have to do with first-order logic? By definition, a formula $\forall x\,A(x)$ is true if $A(a)$ is true for every possible element $a$ of the universe of discourse. Similarly, $\exists y\,E(y)$ is true if there exists an element $e$ in the universe such that $E(e)$ is true. So, $\forall x\exists y\,C(x,y)$ is true if for every $a$, $\exists y\,C(a,y)$ is true. Player $A$ chooses some particular $a$ as the first move. At this point, player $E$ has to choose an $e$ that works for that particular formula $\exists y\,C(a,y)$. For each particular $a$ there may be its own $e$ that makes $C(a,e)$ true. Contrast this with $\exists y\forall x\,C(x,y)$. It is true if $E$ can find an $e$ such that $\forall x\,C(x,e)$ is true. But after the choice of $e$ is made, $A$ can substitute any $a$ for $x$ to get $C(a,e)$. Clearly, coming up with such universal $e$ is harder.

Back to real numbers. You are right that $\forall x\exists y\,x+y>0$ is true because $E$ can choose $y=|x|+1$. But to make $\exists x\forall y\,x+y>0$ true, $E$ has to find an $e$ such that $\forall y\,e+y>0$ is true. Now $A$ can take the result of $E$'s move into account and substitute $-|e|-1$ for $y$. The result $e+(-|e|-1)$, which is negative. This shows how to formally prove that $\exists x\forall y\,x+y>0$ is false: we do it by contradiction, assuming that it is true.

Sorry if this is too long.
 
Last edited:
Thank you evgeny. That helped a lot. It's always really useful to get new techniques/points of view for things like this.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top