Is this a lattice? X = {1,3,4,12}, Divisilibity relation.

795 Views Asked by At

I am just starting to learn about lattices. I am trying to see what examples I can come up with. It is helpful if I can have some outside confirmation about my thinking.

Let $X = \{1,3,4,12\}$

Define poset $\{X,\mid\}$ where $\mid$ refers to divisibility. (So, $4\mid1$ but $1\nmid4.)$

I am under the impression that $X$ is a lattice. Divisibility makes $\wedge = gcd$ and $\vee = lcm$

In particular,

$$(1 \wedge 3) = 1 \in X$$

$$(1 \vee 3) = 3 \in X$$

$$(1 \wedge 4) = 1 \in X$$

$$(1 \vee 4) = 4 \in X$$

$$(1 \wedge 12) = 1 \in X$$

$$(1 \vee 12) = 12 \in X$$

$$(3 \wedge 4) = 1 \in X$$

$$(3 \vee 4) = 12 \in X$$

$$(3 \wedge 12) = 3 \in X$$

$$(3 \vee 12) = 12 \in X$$

$$(4 \wedge 12) = 4 \in X$$

$$(4 \vee 12) = 12 \in X$$

Sorry to just write out all the cases. A simple "Yes" or "No" with a brief explanation if No would be very helpful.

2

There are 2 best solutions below

6
On BEST ANSWER

That's exactly right... for the opposite relation, $$x \preceq y \iff x \text{ divides } y \text{.}$$ Note: standard usage is that "$x\mid y$ " means this relation "$x$ divides $y$", not "$x$ is divisible by $y$".

For $\preceq$ as above, $\wedge$ and $\vee$ are gcd and lcm respectively. Of course all your cases are correct.

However, the relation "is divisible by" is the reverse of $\preceq$: $$ x \sqsubseteq y \iff y \preceq x $$ so with respect to $\sqsubseteq$, meet and join are interchanged: $\wedge_{\sqsubseteq}$ is lcm and $\vee_{\sqsubseteq}$ is gcd.

If an ordering is a lattice ordering then so is its reverse. If you confirm that an ordering is a lattice ordering (sup and inf exist for all pairs of elements), and then use $\wedge$ and $\vee$ to denote the sup and inf that you proved to exist, then you don't have to prove that the lattice axioms hold for $\wedge$ and $\vee$: they do, by definition. That's the case here.

3
On

Nothing at all wrong with writing out all the cases. It's one of the clearer ways to do it in this case!

You'll also need to show that the following laws hold:

  • commutative ($A \wedge B = B \wedge A$ and $A \vee B = B \vee A$)
  • associative ($A \wedge (B \wedge C) = (A \wedge B) \wedge C$ and $A \vee (B \vee C) = (A \vee B) \vee C$)
  • absorption ($A \wedge (A \vee B) = A$ and $A \vee (A \wedge B) = A$ )
  • idempotent ($A \vee A = A$ and $A \wedge A = A$)