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