can GCD(0,8)≠1 be proven purely by lattice laws?

289 Views Asked by At

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).

2

There are 2 best solutions below

6
On BEST ANSWER

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
On

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