Logical proposition for “Every positive integer can be written as the sum of 2 squares”

I am to formulate the logical proposition for

Every positive integer can be written as the sum of 2 squares (domain of integers)

One of the previous questions was

Formulate the logical proposition for the sentence "The number 100 can be written as the sum of 2 squares" (domain of integers)

And my answer was $$\exists x \exists y(x^2 + y^2 = 100)$$

So I thought to take the same approach with

Every positive integer can be written as the sum of 2 squares

And came up with

$$\forall x \exists a \exists b (a^2 + b^2 = x)$$

But there's no where stating that $x$ is positive, so would

$$\exists x \exists a \exists b (a^2 + b^2 = x)$$

If someone could tell me where I went wrong or give me a hint I'd greatly appreciate the help, thank you very much.

• $\forall{x_{\in\mathbb{N}}}\exists{a,b_{\in\mathbb{N}}}:x=a^2+b^2$. You can use $\mathbb{Z}^{+}$ instead of $\mathbb{N}$, if you're worried about $x=0$. – barak manos Aug 8 '16 at 9:39
• @barakmanos It works for $0$, but there are many positive integers it's false for. Whether or not the proposition is true is irrelevant to the question, which asks specifically for positive integers. – Patrick Stevens Aug 8 '16 at 9:40
• @PatrickStevens: I did not say that the statement was true. OP asks how to formulate it, not how to prove it. – barak manos Aug 8 '16 at 9:41
• @barakmanos I don't remember your original wording now, but it suggested to me (probably my misinterpretation) that you were saying "You can also include $0$ because the statement is true for $0$". Sorry. – Patrick Stevens Aug 8 '16 at 9:43
• @PatrickStevens: Yes, I understand why this statement has caused the impression that I was assuming that the statement was true. Good thing I fixed it (though I did so for a different reason). – barak manos Aug 8 '16 at 9:45

Why would you switch from "forall" to "exists" if you wanted to specify "$x$ is positive"?

You're going to want $$(\forall x > 0)(\exists a \exists b)(a^2+b^2 = x)$$ or, if your language doesn't let you formulate that, $$(\forall x)[x > 0 \to (\exists a \exists b)(a^2+b^2 = x)]$$

As an aside, the proposition is false: $3$ cannot be written as the sum of two squares. It is necessary and sufficient that primes $3 \pmod{4}$ appear only to even powers in the prime factorisation.

• Yeah I knew it was false, (read it somewhere) but the question wanted me to do it anyway. This makes much more sense (your second version) Thank you very much! So I can define for all x, x > 0 as a condition? I don't have to state all the limitations at the beginning? – Samir Chahine Aug 8 '16 at 9:30
• It depends quite how formal you need to be. $(\forall x > 0)(\exists a \exists b)(a^2+b^2 = x)$ is totally unambiguous, but many inductive definitions of languages would forbid its construction. $(\forall x > 0)\phi$ could be viewed as a shorthand for $(\forall x)(x > 0 \to \phi)$. I don't really know what you mean by "I don't have to state all the limitations at the beginning"; in this instance you need the $x>0$ condition to come before the existential quantifiers, because otherwise you're asserting the existence of some $a,b$ pair which works for all $x>0$. – Patrick Stevens Aug 8 '16 at 9:39
• @PatrickStevens: I'm not sure of that. If you have the existence quantifiers outside the material implication, but inside the universal, you still have a separate (a, b) for each x. It's just that you also have an (a, b) for negative x, which don't have any particular constraints on them because the antecedent is false. But that's OK since you can always pick an arbitrary (a, b). – Kevin Aug 8 '16 at 22:34
• Wouldn't most courses or professors in logic expect the natural number restriction to be listed explicitly in the answer? – nickalh Aug 9 '16 at 4:29
• @nickalh I would personally expect the answer to be written in the language of the ordered ring of integers (that would be the least surprising language for it to be written in), so $\mathbb{Z}$ is implicit. – Patrick Stevens Aug 9 '16 at 8:02

$$P_{100}:= \exists\ x,y\ (x^2 + y^2 = 100)$$

where you replace $100$ by "any positive integer", let $z$:

$$\forall z>0\ P_z,$$ giving $$\forall z>0\ \exists\ x,y\ (x^2 + y^2 = z).$$

($x,y,z\in\mathbb Z$ is left implicit.)

You can formulate this statement as:

$\large\forall_{x\in\mathbb{N}}\exists_{a,b\in\mathbb{N}}:x=a^2+b^2$

If you're worried about $0\in\mathbb{N}$ (which is a matter of definition), then you can use $\mathbb{Z^+}$ instead.

BTW, the statement itself is false.

Your second version is an a fortiori of what you're trying to express: there must exist such an $x$ since you "know" every $x$ has that form!

I think just $\forall x (x>0 \implies \exists a \exists b (a^2+b^2=x))$ will do.

• Thank you, makes more sense! – Samir Chahine Aug 8 '16 at 9:30
• Also, instead of restricting x on the left side, you could use |x| on the right side. – amI Aug 8 '16 at 21:24