# Can't interpret this predicate logic formula

I have some formula in predicate logic that contain predicate symbols and function symbols and I should define their meaning and the domain of discourse.

• $Q(x,y)$ is predicate symbol of arity 2
• $n$ is function symbol of arity 0 (a constant)
• $*$ is function symbol of arity 2
• other...

From other forumula it kinda looks like

• the domain of discourse could be all positive (w/o zero) rational (or even real) numbers
• $n$ could be one
• $*$ could be multiplication

Now I've hit this formula, which looks almost like the definition of divisibility on integers.

$\varphi\equiv\forall x \forall y (Q(x,y)\Leftrightarrow (y=n \lor \exists z (Q(x,z) \land y=x*z)))$

The problem is it is NOT a divisibility!

Let's say $y$ divides $x$, $x=6$ and $y=3$. Then for $z=2$ it holds $Q(6,2)$ as 2 divides 6, but $3=6*2$ does not hold!

Let's say $x$ divides $y$, $x=3$ and $y=6$. Then from $6=3*z$ we conclude $z=2$, but $Q(6,2)$ does not hold, as 6 does not divide 2!

So my question is, do you think there is an error in $\varphi$ and $y=x*z$ should correctly be $x=y*z$? If it is not an error, what exactly could this formula represent? Do I have to change my domain of discourse, function/predicate symbols?

• If it would indeed be divisibility, then why the separate check for y=1 (assuming n is indeed 1)? – Bram28 Nov 21 '16 at 2:42
• Good point, I did not think of it. What do you reckon it could be, then? – Slazer Nov 21 '16 at 2:43
• No clue yet :p sorry! – Bram28 Nov 21 '16 at 2:44
• By the way, the other formula pretty much define the regular set axioms, associativity, commutativity, relation HigherThan, relation isOdd and a condition to disallow any negative values. – Slazer Nov 21 '16 at 2:45
• Just noticed that you could see $Q(x,y)$ as $y$ is a power of $x$. E.g. $Q(x,1)$ is true ... And therefore $Q(x,x)$ is true, and therefore $Q(x,x^2)$ is true, etc. – Bram28 Nov 21 '16 at 2:52

## 1 Answer

Yeah, I'll put that as my answer:

$Q(x,y)$: $y$ is $x^n$ with $n$ a natural number.

E.g we have $Q(x,x^2)$ iff $Q(x,z) \land x^2 = x*z$, i.e. iff $Q(x,x)$ iff $Q(x,z) \land x = x* z$ i.e. iff $Q(x,1)$ ... Which is true since $1=n$.

And of course $1$ is $x^0$ for any positive number $x$, so that works.

Proof: for any real numbers $x$ and $y$: $y = x^p$ for some real number $p$. We have $Q(x,x^p)$ iff $Q(x,z)$ where $x^p = x*z$ i.e. where $z= x^{p-1}$, so basically $Q(x,x^p)$ iff $Q(x,x^{p-1})$. Since this only bottoms out at $y=1$ i.e. where $p=0$, $Q(x,y)$ will be true for all and only those $y$ for which $y=x^p$ with $p$ a natural number (including 0).

• Frankly, it's quite hard for me to grasp it this late. Could you tell me how sure are you with your answer from 0 (unsure) to 10 (certain)? I'd pretty much appreciate a little peer review before accepting :S. Or at least some literature, I could really use it! – Slazer Nov 21 '16 at 3:09
• I'd say a 9, but I will try to produce a proof to get to that 10! :) but yeah, some per review would be good. – Bram28 Nov 21 '16 at 3:13
• Mind that we are working on rational numbers, but that should be ok. – Slazer Nov 21 '16 at 3:14
• Yeah, naturals, rationals, reals, it works the same either way. In the proof I just assumed reals. – Bram28 Nov 21 '16 at 3:25