Question 1 of 12

Question 1

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. The predicate alphabet $P(x)$, $L(x,y)$, $E(x)$, $A(x,y,z)$ over the universe of positive integers, as stated in the question.

Find. A first-order logic sentence for each of the five statements (a)-(e), using only the given predicates, $\land,\lor,\neg,\to$, and $\forall/\exists$.

Approach. Translate each English sentence phrase-by-phrase: "not all" becomes a negated universal (or equivalently an existential negation), "there exists" an existential quantifier, "greater than 2" the given order predicate $L(2,x)$, and "sum of two primes"/"$n+2$" the addition predicate $A$.

1. a) Not all positive integers are prime. "Not all $x$ have $P(x)$" is the negation of a universal claim: $$\neg \forall x\, P(x)$$ equivalently (pushing the negation through) $\exists x\, \neg P(x)$ — some positive integer is not prime. $\boxed{\neg \forall x\, P(x)}$
2. b) There exists an even prime. One value that is simultaneously even and prime: $$\exists x\, \big(E(x) \land P(x)\big)$$ $\boxed{\exists x\,(E(x)\land P(x))}$ (witnessed by $x=2$).
3. c) Every even integer greater than 2 is a sum of two primes. "$x$ greater than 2" is $L(2,x)$; "sum of two primes equal to $x$" needs two prime witnesses $y,z$ with $A(y,z,x)$: $$\forall x\, \Big[\big(E(x)\land L(2,x)\big) \to \exists y\,\exists z\,\big(P(y)\land P(z)\land A(y,z,x)\big)\Big]$$ $\boxed{\forall x[(E(x)\land L(2,x))\to \exists y\exists z(P(y)\land P(z)\land A(y,z,x))]}$ — this is exactly the statement of Goldbach's conjecture.
4. d) There is no largest prime. Equivalently: for every prime $x$ there is a strictly larger prime $y$: $$\forall x\,\Big[P(x)\to \exists y\,\big(P(y)\land L(x,y)\big)\Big]$$ $\boxed{\forall x[P(x)\to\exists y(P(y)\land L(x,y))]}$
5. e) There are infinitely many twin primes. For every $x$ there is a twin-prime pair $(y,y+2)$ with $y>x$; write "$y+2=z$" as $A(y,2,z)$: $$\forall x\,\exists y\,\exists z\,\Big[L(x,y)\land P(y)\land P(z)\land A(y,2,z)\Big]$$ $\boxed{\forall x\exists y\exists z[L(x,y)\land P(y)\land P(z)\land A(y,2,z)]}$ — unproven in general (the Twin Prime Conjecture), but the sentence itself is a well-formed formalization.