0
$\begingroup$

From reading my textbook, I am having difficulty grasping how Peano Arithmetic works.

I tried to find a formula in the language of PA that expresses each of the following:

1. a | b

In terms of a formula, I came up with "$\mathsf {PA} \vdash \exists c(a * c = b)$" but I fail to see what peano axioms can lead to this formula or how the procedure would look like

2. a is prime

In terms of a formula for this one, I came up with "$\mathsf {PA} \vdash a > 1 \land \forall bc(a | b * c \to a | b \lor a | c) $"

3. a is a perfect square

I don't know if I was thinking overcomplicated for this one but does "$\mathsf {PA} \vdash \exists a(a * a = a^2)$" work?

I don't know if it suffices to have a formula and thats it or it's necessary to provide a proof of the formula working as well?

Thanks for reading and helping!

$\endgroup$
4
  • $\begingroup$ Please avoid just referring to an image. In this case the image is complete as there is a footnote that isn't included. Also your formula for the second point is missing a parenthesis. $\endgroup$
    – skyking
    Mar 16, 2017 at 7:59
  • $\begingroup$ For 1) the definition is correct; buu it is a definition and not a theorem. You cannot prove it. Formally, a defintion is an abbreviation : $\text {Div} (a,b)$ in place of $\exists c \ (a * c=b)$. $\endgroup$
    – Mauro ALLEGRANZA
    Mar 16, 2017 at 8:02
  • $\begingroup$ For 3), it is wrong : $\text {Perf Sq}(a) := \exists b (a= b * b)$. (there is no "exponentiation" in the set of symbols of your language). $\endgroup$
    – Mauro ALLEGRANZA
    Mar 16, 2017 at 8:05
  • $\begingroup$ I removed an unbalanced parenthesis from the "prime" definition (which may have contributed to an apparent misunderstanding in skyking's answer). Unfortunately I had to add some blanks in free space before it would take the change and now I can't delete the blanks. Apologies. $\endgroup$
    – Martin Rattigan
    Mar 16, 2017 at 8:37

1 Answer 1

Reset to default
1
$\begingroup$
  1. a is a divisor of b**

That's correct. Note that this and the others are mere definitions, they need only be statements that is gramatically correct in the language of PA. You're allowed to multiply for example. I also assume that you're allowed to use quantifiers.

Formally one uses the first and second definition to show that it's a formula by noting that $a\cdot c$ (by 7.1iii) is a term and therefore $(a\cdot c=b)$ is a formula (by 7.2i), therefore also $\exists c(a\cdot c = b)$ is a formula (by 7.2ii).

  1. a is prime**

No. The $x|y$ is normally means that $x$ divides $y$. A prime number is allowed to divide other numbers - it's the other way around. Also you actually don't need to involve divisibility. Alternatives are:

$$(1 < a) \land \forall b,c(a = bc) \rightarrow (b=a \lor c=a)$$ $$(1 < a) \land\forall b(b| a) \rightarrow (b=a \lor b=1)$$

However this requires $1$ to be defined first, but you could use $S(0)$ instead as this would be the probable definition of $1$. Note that your proposal included the relation $>$ which isn't defined - the definition 7.2 only states that $(t<u)$ is a formula.

These requires us to be allowed to use our definitions. Otherwise we would use

$$(S(0) < a) \land \forall b,c(a = bc) \rightarrow (b=a \lor c=a)$$

  1. a is a perfect square**

Incorrect, for one you can't reuse $a$ to be quantified over. Also you should realize that a perfect square is a number that is the square of another number:

$$\exists b (a = b\cdot b) $$

Note that we don't write $b^2$ as that would require us to define squaring first.

$\endgroup$
5
  • $\begingroup$ Thanks for the clear explanation! For number 2, could we reference successor of 0 (S0) to represent 1 (S(0) = 1) so that we don't have to define 1 for both the alternatives? $\endgroup$
    – T.Steinkempt
    Mar 16, 2017 at 9:09
  • $\begingroup$ @T.Steinkempt Yes. I chose to use the symbol $1$ because I assumed that the definition was introduced. Besides the meaning of $S$ seem to be clarified in a footnot that wasn't included in your picture. $\endgroup$
    – skyking
    Mar 16, 2017 at 9:31
  • $\begingroup$ The relation "<" doesn't need a definition (it appears in the rules for valid wffs in the link given). The axioms (not shown) presumably include "$t<St\wedge (t<u\Rightarrow St<Su)$" or something of the kind. All that is then needed is to write $1<a $ instead of $a>1$. If the formula were then written as a definition (with balanced parentheses of course) it would correctly define a prime. Your formulae would normally define an irreducible, which in this case comes to the same thing. $\endgroup$
    – Martin Rattigan
    Mar 16, 2017 at 9:32
  • $\begingroup$ @MartinRattigan You're correct, I've missed that and updated the answer. However $>$ would need a definition. $\endgroup$
    – skyking
    Mar 16, 2017 at 9:39
  • $\begingroup$ True. That would be more useful than reversing the terms forever. $\endgroup$
    – Martin Rattigan
    Mar 16, 2017 at 9:41

You must log in to answer this question.

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