Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to write a first order sentence, which if, interpreted the symbols in this natural manner in the set of Naturals, would assert that:

Every even number is the sum of two prime numbers.

Here's my shot at it:

For all x, (2|x) ^ (x>2) ---> __

Should I bring in more variables?

Also, In L$_(groups)$, how can we give an axiomatization for the class of groups?

So I see that we need to check associativity, identity and inverses. But not sure how it follows.

THanks

share|improve this question
    
You have at least two questions here. You should ask them separately. But more importantly - what have you tried for each one? Where did you encounter them? If you know enough about first order logic to understand there is language for groups, and you know the usual axioms for them, surely you can see that the usual axioms for groups are already stated in that language. –  Carl Mummert Mar 7 '13 at 3:38
add comment

2 Answers

up vote 1 down vote accepted

We assume that variables range over positive integers, and that we have a constant symbol to represent the number $1$. And, contrary to the standard rules of predicate calculus, we write $x+y$ to represent the sum of $x$ and $y$. In principle, we should use something like $S(x,y)$, where $S$ is a binary function symbol.

Similarly, we denote the product of $x$ and $y$ by the usual $xy$, instead of something like $P(x,y)$.

Our sentence will ultimately be a little complicated, so we introduce two abbreviations.

Write $\operatorname{Even}(x)$ as an abbreviation for $\exists s(s(1+1)=x)$.

Write $\operatorname{Prime}(x)$ as an abbreviation for $\lnot(x=1)\land \forall u\forall v(uv=x\to (u=1\lor v=1))$.

Then a sentence that does what you want is $$\forall x(\operatorname{(Even}(x)\land \lnot(x=1+1))\to (\exists u\exists v(\operatorname{Prime}(u)\land \operatorname{Prime}(v)\land x=u+v)).$$ Now in this sentence, replace occurrences of $\operatorname{Even}(t)$ and $\operatorname{Prime}(t)$ by their long forms.

We have been a little too casual about parentheses. And we put in the additional hypothesis $\lnot (x=1+1)$, because the even natural number $2$ is not the sum of two primes.

Added: For groups, we can use the following axiomatization. If you want, you can take the conjunction of the axioms below, to get a single axiom. Our language has a single constant symbol $e$, and a binary function symbol $P$. For greater readability, you may want to replace $P(x,y)$ below by $xy$.

Axiom $1.$ $\forall x\forall y\forall z(P(P(x,y),z)=P(x,P(y,z)))$. This is a formal language version of the Associative Law $(xy)z=x(yz)$.

Axioms $2.$ $\forall x P(e,x)=x$; $\forall x(P(x,e)=x$.

Axioms $3.$ $\forall x\exists y(P(x,y)=e)$; $ \forall x\exists y(P(y,x)=e)$.

Note that this is not a minimal set of axioms. Also, one can get rid of the constant symbol $e$, and work with a single binary function symbol $P$. It makes the axioms a little messier.

share|improve this answer
    
Thanks, this makes sense. However, in L(groups), how can we give an axiomatization for this? I dont quite understand –  Buddy Holly Mar 7 '13 at 3:02
    
Yes, we can give an axiomatization of first-order group theory. The axioms are usually given in semi-formal language that is not hard to put more formally. We can collapse these into a single axiom by combining the various axioms with $\land$. If you really need the axioms, I can add something to the answer above, but probably you can do it. The details depend a bit on the language $L$ that you use. I suggest having a constant symbol $e$ (for the identity) and that you denote product by the illegal $xy$, and not as $P(x,y)$. –  André Nicolas Mar 7 '13 at 3:11
    
OK. I would appreciate if you can put in the axioms to the above equation. I dont want to mess up what you have written since I cant make so much sense of it. –  Buddy Holly Mar 7 '13 at 6:24
add comment

Hint: "$y$ is prime" means there do not exist $u$ and $v$ with $u > 1$, $v > 1$ and $y = uv$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.