4

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?

tpv
  • 396
  • 4
    A pointer: what happens if you define $\neg x=x$? – mac May 10 '11 at 10:49
  • @mac: What do you mean by define? – tpv May 10 '11 at 11:49
  • 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. – joriki May 10 '11 at 12:02
  • @joriki: thanks, I think I'm kinda getting it now... – tpv May 10 '11 at 12:18
  • 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). – Asaf Karagila May 13 '11 at 11:59
  • @Asaf Karagila : I added the solution I came up with based on the comments :). – tpv May 13 '11 at 15:21
  • @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. – Asaf Karagila May 13 '11 at 15:30
  • @Asaf Karagila: Oh, I see. It's done, thanks for the suggestion. – tpv May 13 '11 at 18:41
  • 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)? – mafu Apr 24 '14 at 19:34

1 Answers1

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.

tpv
  • 396