7
$\begingroup$

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)$$

be correct instead?

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

$\endgroup$
5
  • 2
    $\begingroup$ $\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$. $\endgroup$ Aug 8, 2016 at 9:39
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 8, 2016 at 9:40
  • 2
    $\begingroup$ @PatrickStevens: I did not say that the statement was true. OP asks how to formulate it, not how to prove it. $\endgroup$ Aug 8, 2016 at 9:41
  • 1
    $\begingroup$ @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. $\endgroup$ Aug 8, 2016 at 9:43
  • 2
    $\begingroup$ @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). $\endgroup$ Aug 8, 2016 at 9:45

4 Answers 4

20
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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? $\endgroup$ Aug 8, 2016 at 9:30
  • 2
    $\begingroup$ 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$. $\endgroup$ Aug 8, 2016 at 9:39
  • $\begingroup$ @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). $\endgroup$
    – Kevin
    Aug 8, 2016 at 22:34
  • $\begingroup$ Wouldn't most courses or professors in logic expect the natural number restriction to be listed explicitly in the answer? $\endgroup$
    – nickalh
    Aug 9, 2016 at 4:29
  • $\begingroup$ @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. $\endgroup$ Aug 9, 2016 at 8:02
7
$\begingroup$

You can solve this question by using your previous answer,

$$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.)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, makes more sense! $\endgroup$ Aug 8, 2016 at 9:30
  • 1
    $\begingroup$ Also, instead of restricting x on the left side, you could use |x| on the right side. $\endgroup$
    – amI
    Aug 8, 2016 at 21:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .