I'm given the following axioms:

  1. $\forall x \forall y \forall z(xQy \wedge yQz \rightarrow xQz)$

  2. $\forall x \forall y \forall z [(x\ast y)\ast z Qx \ast (y \ast z)]$

  3. $\forall x \forall y \forall z (xQy \rightarrow x \ast zQz \ast y)$

  4. $\forall x \forall y (\neg xQy \rightarrow (\exists z) (x Q y \ast z \wedge y \ast z Q x))$

  5. $\forall x \forall y (\neg x \ast y Q x)$

And I'm trying to prove that the second axiom $$\forall x \forall y \forall z [(x\ast y)\ast z Qx \ast (y \ast z)]$$ is independent of the rest.

In my attempt, I use the following interpretation:

Domain: $\mathbb{R}^+$

$xQy \leftrightarrow x\leq y$

$x \ast y \leftrightarrow xy+1$

So the axioms can be rewritten as:

  1. $\forall x \forall y \forall z(x \leq y \wedge y \leq z \rightarrow x \leq z)$

  2. $\forall x \forall y \forall z [(xy+1)z+1 \leq x(yz+1)+1]$

  3. $\forall x \forall y \forall z (x \leq y \rightarrow xz+1 \leq zy+1)$

  4. $\forall x \forall y (\neg x \leq y \rightarrow (\exists z) (x \leq yz+1 \wedge yz+1 \leq x))$

  5. $\forall x \forall y [\neg(xy+1 \leq x)]$

Note that axiom 2 can be rewritten as $$\forall x \forall y \forall z [xyz+z+1 \leq xyz+x+1]$$ Which is false because the inequality doesn't hold for, say, z=y=2 and x = 1.

The next step would be to show that the other axioms are true in this interpretation. In general, to show that a formula governed by a universal quantifier is false, one would only need to provide a counter example. But what steps do I need to take in order to show that such a formula is true? For example, it's quite intuitive that the first axiom: $$\forall x \forall y \forall z(x \leq y \wedge y \leq z \rightarrow x \leq z)$$ is true in this interpretation. But will I have to prove in some systematic way that $(x \leq y \wedge y \leq z \rightarrow x \leq z)$ is true for all x, y, and z? How do I formally argue that it's true in this interpretation?

This question may sound silly but appreciate any help or feedback :)


First, there is no need to do a formal proof to show that statements are true (or false) given an interpretation ... at that point you can just use plain mathematics.

Second, unfortunately your interpretation does not make axiom 5 true: pick $x=10$ and $y=0.1$ for a counterexample.

  • $\begingroup$ Very helpful! Thanks :) $\endgroup$
    – LG01
    Mar 26 '19 at 2:05
  • $\begingroup$ @Unknowledgeable Glad you think so ... I would be frustrated that the model doesn't work! I have been trying to find a different model, but nothing that works so far ... $\endgroup$
    – Bram28
    Mar 26 '19 at 2:17
  • $\begingroup$ Yeah. It is taking a while for me to prove the system is independent haha. I changed the domain of the interpretation I gave here to real numbers greater than 1 which so far I think proves the independence of the second axiom. But I'm still trying to prove the independence of the third. Thanks again for the feedback! $\endgroup$
    – LG01
    Mar 26 '19 at 2:50

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.