Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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