1
$\begingroup$

Triggered by previous question, can one prove GCD(0,8)≠1 purely by lattice laws?

Brute force Prover9/Mace4 assertions

x ^ y = y ^ x.  (x ^ y) ^ z = x ^ (y ^ z).  x ^ (x v y) = x.  x v y = y v x.  (x v y) v z = x v (y v z).  x v (x ^ y) = x.  1 v x = x. 1 ^ x = 1. 0 ^ x = 1. 

exhibit no [finite] model, which is indication that the system is inconsistent. I have trouble, however, understanding how to elevate this intuition into a formal proof (there is no goal).

  • 0
    Do you have x ^ x = x from your laws ?2011-03-18
  • 0
    @chandok: Yes, it is redundant.2011-03-18
  • 0
    Is 0 v x = 1 correct?2011-03-19
  • 0
    That is what the original thread suggested. It has been refuted together with another option: 0 v x = 1. The correct version is 0 v x = x and, predictably, Mace4 generates 2 element model. I'm interested, however disproving the wrong assertion 0 v x = 1. I tried putting its negation into Prover9 goal, still Prover9 doesn't seem to be able to derive it.2011-03-19
  • 0
    @Tegiri: You either have things backward, or you are viewing the divisibility order backwards, with $a|b$ meaning $b\leq a$...2011-03-19
  • 0
    @Arturo: distinguishing left and right is extraordinary ability:-) I agree that having GCD lattice order being compatible with standard total order is a natural choice.2011-03-19
  • 0
    @Arturo: Edited: swapped join and meet to eliminate confusion.2011-03-19
  • 0
    @Tegiri: Your listed rules are not inconsistent: they havee a model with one element, all binary operations the obvious ones, and all nullary operations the unique element.2011-03-19

2 Answers 2

1

Note $\rm\ x = 0\ $ in $\rm\ x \wedge (x \vee y)\ =\ x\ \ \Rightarrow\ \ 0\wedge (0\vee y)\ =\ 0\ \ $ contra $\rm\ \ 0\wedge x\ =\ 1\ \ $ (presuming $\rm\ 0 \ne 1\:$).

Alternatively, recall that the idempotent laws follows from the absorption laws, viz.

$$\rm x\wedge x\ =\ x\wedge (x\vee (x\wedge x))\ =\ x $$

Hence $\rm\ \ 0\wedge 0\ =\ 0\ \ $ contra $\rm\ \ 0\wedge x\ =\ 1\:.$

  • 0
    Just to clarify: you are using $0$ and $1$ to denote the corresponding integers, and not to denote the infimum and supremum of the lattice, correct?2011-03-19
  • 0
    No, the above is in the equational theory that the OP gave.2011-03-19
  • 0
    @Bill: Right: so that $0$ denotes the *usual* $0$, not the least element of the lattice. (His theory includes, e.g., $1\lor x = x$, which of course means that "1" does not represent the maximum, as is standard in 01-lattices).2011-03-19
  • 0
    @Arturo: Possible models are not relevant to the above equational proof (other than the assumption that $\rm\ 0 \ne 1\:$).2011-03-19
  • 0
    I tried absorption and even distributivity, but this rather simple proof escaped me. Thank you.2011-03-21
  • 0
    Here is automatic proof, which is identical to Bill's. The culprit was to go after correct goal! 1 0 ^ x = 0 # label(non_clause) # label(goal). [goal]. 4 x ^ (x v y) = x. [assumption]. 10 0 ^ x = 1. [assumption]. 11 0 ^ c1 != 0. [deny(1)]. 12 0 != 1. [copy(11),rewrite([10(3)]),flip(a)]. 30 0 = 1. [para(10(a,1),4(a,1)),flip(a)]. 31 $F. [resolve(30,a,12,a)].2011-03-21
0

Solved the remaining bit of the puzzle: GCD(0,8)≠0.

1 v x = x ⇒  1 v 0 = 0 0 ^ x = 0 ⇒  1 ^ 0 = 0   1 v 0 = 1 ^ 0 ⇒  1 = 0