Let’s consider algebras with the following axioms in addition to commutativity and associativity: $$x \vee x=x$$ $$\neg \neg x = x$$

Does the Huntington axiom ( $\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y) = x$ ) follow from the axioms? If yes prove it by showing how the axioms entail it, if not, give an interpretation that contradicts it, but satisfies the axioms above together with the commutativity and associativity axioms.

This is a homework assignment for my AI class, but I have no idea where to start. Could you give me some pointers?

  • 4
    $\begingroup$ A pointer: what happens if you define $\neg x=x$? $\endgroup$ – mac May 10 '11 at 10:49
  • $\begingroup$ @mac: What do you mean by define? $\endgroup$ – tpv May 10 '11 at 11:49
  • 1
    $\begingroup$ @tpv: Take any structure with a commutative and associative binary operation $\lor$ such that $x\lor x=x$ and define $\neg x:=x$. Then simplify $\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y)$ and note that there's no reason to expect it to equal $x$. Pick $\lor$ such that the result is different from $x$ to obtain a counterexample. $\endgroup$ – joriki May 10 '11 at 12:02
  • $\begingroup$ @joriki: thanks, I think I'm kinda getting it now... $\endgroup$ – tpv May 10 '11 at 12:18
  • 1
    $\begingroup$ @tpv: If you have solved your own question, please post a solution/hints/partial solution (the kind of answer that you were hoping for). $\endgroup$ – Asaf Karagila May 13 '11 at 11:59

Based on the comments I think I have the solution now:

Let's define $\neg x = x$, that is consistent with $\neg \neg x = x$, and let $x \vee x$ be the logical AND operation, that's associative, commutative, and $x$ AND $x=x$ holds.

Now let's work with the Huntington axiom: $$\neg (\neg x \vee y) \vee \neg (\neg x ∨ \neg y) = x$$ Using $\neg x = x$ we get: $$(x \vee y) \vee (x ∨ y) = x$$ Then applying $x \vee x = x$ yields $$(x \vee y) = x$$

But for the logical AND operation if $x$ is true and $y$ is false $x$ AND $y$ is false, and that a contradicts with the result. So we found a counterexample, and that means that the Huntington axiom does not follow from the given axioms.


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.