Statement neg

• Aug 27th 2011, 11:09 AM
terrorsquid
Statement neg
I was just wanting to make sure I had treated everything correctly when negating this statement. I wasn't 100% on how to treat the bracket between the existential quantifiers and whether or not I should change the predicates inside the brackets.

Negate:

$\exists x \in \mathbb{Z}\left(\exists y \in \mathbb{Z}\left(\left((x+1)^2>y^2\right) \rightarrow (x\neq y)\right)\right)$

First of all am I correct in thinking it reads "There exists an x that is an integer such that there exists a y that is an integer such that blah blah implies blah"?

My negation:

$\forall x \in \mathbb{Z} \left(\forall y \in \mathbb{Z} \neg \left(\left((x+1)^2>y^2)\rightarrow (x\neq y)\right)\right)$

$\equiv \forall x \in \mathbb{Z} \left(\forall y \in \mathbb{Z}\neg \left(\neg \left((x+1)^2>y^2)\vee (x\neq y)\right)\right)$

$\equiv \forall x \in \mathbb{Z} \left(\forall y \in \mathbb{Z} \left( \left((x+1)^2>y^2)\wedge\neg (x\neq y)\right)\right)$

$\equiv \forall x \in \mathbb{Z} \left(\forall y \in \mathbb{Z} \left( \left((x+1)^2>y^2)\wedge (x = y)\right)\right)$

How do I determine which statements are true/false. I see it all as one statement is the problem how do I separate them?

Thanks.
• Aug 27th 2011, 01:50 PM
emakarov
Re: Statement neg
Your negated statement is constructed correctly. It is obviously false since it says in particular that every two integers are equal.
• Aug 27th 2011, 07:49 PM
terrorsquid
Re: Statement neg
Ok, thanks. So I should always leave the brackets between the quantifiers? Would it be wrong if I wrote $\forall x \in \mathbb{Z}~\forall y\in \mathBB{Z}(...)$? does the bracket still act as a "such that" term? i.e., is $\exists x \forall y(...)$ the same as $\exists x(\forall y (...))$

My question asks which, if any, of the two statements is true? Where are the two separate statements? I guess it is the "x=y" and "X^2 + 1 = y^2" ? so both false.
• Aug 28th 2011, 06:18 AM
emakarov
Re: Statement neg
Whether each subformula has to be surrounded by parentheses depends on the definition of well-formed formulas. For example, the definition may have clauses like:

If A and B are formulas, then so are (¬A), (A → B), (A /\ B) and (A \/ B)
If A is a formula, then so are (∀x (A)) and (∃x (B))

So strictly speaking, one has to write parentheses everywhere. However, in practice, people agree on the precedence and associativity of connectives, which allows omitting most parentheses. Typically, the order of precedence is ¬, /\, \/, →, ↔. The quantifiers can be between ¬ and /\, between \/ and →, or at the end, depending on the convention. Also, /\ and \/ are usually left-associative (though this does not matter since they are associative), while → is right-associative.

When there are two quantifiers in a row, there is never need to enclose the inner one in parentheses since there is no ambiguity. Also, things that are involved in building atomic formulas bind stronger than logical connectives, so there is no need to surround atomic formulas with parentheses.

So,

$\exists x \in \mathbb{Z}\left(\exists y \in \mathbb{Z}\left(\left((x+1)^2>y^2\right) \rightarrow (x\neq y)\right)\right)$

can be written as

$\exists x\in\mathbb{Z}\;\exists y\in\mathbb{Z}\;\big((x+1)^2>y^2\rightarrow x\neq y\big)$

I personally like the convention where the scope of a quantifier followed by a period extends as far to the right as possible, so the formula would be

$\exists x\in\mathbb{Z}\;\exists y\in\mathbb{Z}.\;(x+1)^2>y^2\rightarrow x\neq y$

Quote:

My question asks which, if any, of the two statements is true? Where are the two separate statements? I guess it is the "x=y" and "X^2 + 1 = y^2" ? so both false.
"x = y" is not a proposition because its truth value depends on the values of x and y. Probably the two formulas are the formula above and its negation. As I said, the negation is false, so the original formula has to be true.
• Aug 28th 2011, 07:02 AM
terrorsquid
Re: Statement neg
Thanks so much; that cleared up a lot :D