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?

  • $\begingroup$ If it would indeed be divisibility, then why the separate check for y=1 (assuming n is indeed 1)? $\endgroup$ – Bram28 Nov 21 '16 at 2:42
  • $\begingroup$ Good point, I did not think of it. What do you reckon it could be, then? $\endgroup$ – Slazer Nov 21 '16 at 2:43
  • $\begingroup$ No clue yet :p sorry! $\endgroup$ – Bram28 Nov 21 '16 at 2:44
  • $\begingroup$ 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. $\endgroup$ – Slazer Nov 21 '16 at 2:45
  • $\begingroup$ 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. $\endgroup$ – Bram28 Nov 21 '16 at 2:52

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

  • $\begingroup$ 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! $\endgroup$ – Slazer Nov 21 '16 at 3:09
  • $\begingroup$ 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. $\endgroup$ – Bram28 Nov 21 '16 at 3:13
  • $\begingroup$ Mind that we are working on rational numbers, but that should be ok. $\endgroup$ – Slazer Nov 21 '16 at 3:14
  • 1
    $\begingroup$ Yeah, naturals, rationals, reals, it works the same either way. In the proof I just assumed reals. $\endgroup$ – Bram28 Nov 21 '16 at 3:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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