4
$\begingroup$

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
    A pointer: what happens if you define $\neg x=x$?2011-05-10
  • 0
    @mac: What do you mean by define?2011-05-10
  • 1
    @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.2011-05-10
  • 0
    @joriki: thanks, I think I'm kinda getting it now...2011-05-10
  • 1
    @tpv: If you have solved your own question, please post a solution/hints/partial solution (the kind of answer that you were hoping for).2011-05-13
  • 0
    @Asaf Karagila : I added the solution I came up with based on the comments :).2011-05-13
  • 0
    @tpv: So I see, I actually meant that you would add that as an answer (and perhaps even accept it), this way the question will not be bumped by the server every now and then.2011-05-13
  • 0
    @Asaf Karagila: Oh, I see. It's done, thanks for the suggestion.2011-05-13
  • 0
    Why can you simply define $\neg x := x$? Is it because there was no definition provided yet (i.e. we only got comm, assoc, and the two written above)?2014-04-24

1 Answers 1

2

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.