I'm less than a rookie so it might seem like an easy question but I want a head start to figure things later on my own. The question wants me to prove that the set $D(m) = \{ x \in \mathbb N - \{0\} : x\mid m \}$ where $m$ is a positive number, is a lattice under two binary operations of taking : gcd and lcm. So I figured out that first I have to prove that it's a partially ordered set ( reflexive - anti Symmetric - transitive), but the problem here I can't understand what does it mean by these two operations. I need an example on the reflexive part so I could understand. or at least any example. and Sorry for this low Question.
Asked
Active
Viewed 203 times
0
-
1Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to. – José Carlos Santos Jun 05 '20 at 15:04
-
What are you asking? What is the meaning of $\gcd$ and $\operatorname{lcm}$???? $\gcd$ is the greatest common divisor (ex. $\gcd(20,12)=4$ because $4|20$ and $4|12$) and $\operatorname{lcm}$ is least common multiple (ex. $\operatorname{lcm}(20,12)=60$ because $20|60$ and $12|60$. If you meant some other question could you clarify what you are asking? – fleablood Jun 05 '20 at 15:23
-
I dont understand how to usethem in the proof, and no I'm not asking what is the meaning of gcd and lcm. – Omar Muhammed Aly Jun 05 '20 at 15:37
2 Answers
2
It is reflexive because each number divides itself, so $a$ divides $a$ for every non-zero $a$, it is antisymmetric, because if $a$ divides $b$ and $b$ divides $a$, then $a=\pm b$, but $a$ and $b$ being positive, it must be that $a=b$. Surely you can prove that if $a$ divides $b$ and $b$ divides $c$ then $a$ divides $c$, which is transitivity.
To show that it is a lattice you have to prove that for every two numbers $a$ and $b$ there exist $\inf\{a,b\}$ and $\sup\{a,b\}$. Recall that $\inf\{a,b\}$ must divide both $a$ and $b$ and if $c$ divides both $a$ and $b$, then $c$ must divide $\inf\{a,b\}$. Dually, both $a$ and $b$ divide $\sup\{a,b\}$ and if both $a$ and $b$ divide $c$, then $\sup\{a,b\}$ must divide $c$. Hence you are left to prove that $\gcd(a,b)$ and $\operatorname{lcm}(a,b)$ play the role of $\inf\{a,b\}$ and $\sup\{a,b\}$respectively.
Maryam
- 1,889
0
It seems that most of the people are missing PO's question, which is how to use $\operatorname{lcm}$ and $\gcd$.
You need to prove that any subset $\left\{a,b\right\}\subseteq D(m)$ has a least upper bound $\operatorname{LUB}(\left\{a,b\right\})$ and a greatest lower bound $\operatorname{GLB}(\left\{a,b\right\})$ defined by you.
By defining $\operatorname{LUB}(\left\{a,b\right\}) = \operatorname{lcm}(a,b)$ and $\operatorname{GLB}(\left\{a,b\right\})=\gcd(a,b)$, you need to prove that for any $\left\{a,b\right\}\subseteq D(m)$, the $\operatorname{LUB}(\left\{a,b\right\})\in D(m)$ and $\operatorname{GLB}(\left\{a,b\right\})\in D(m)$.
This is easy to prove as if $\left\{a,b\right\}\subseteq D(m)$, then $a\mid m$ and $b\mid m$, hence $\gcd(a,b)\mid m$, so $\operatorname{GLB}(\left\{a,b\right\})\in D(m)$. You can work on the second part. Hint: The expression $ab=\gcd(a,b)\times \operatorname{lcm}(a,b)$ might be useful. Try to think what happens if $\operatorname{LUB}(\left\{a,b\right\})\not\in D(m)$.
liwuen
- 299
-
Just be careful. In your problem you are using the poset $D(m)$ with $\text{lcm}$ and $\gcd$. But not all the posets with these two operations will give you a lattice. Example $S=\left{2,3,6,12,24,36\right}$, as $\gcd(2,3)$ and $\text{lcm}(24,36)$ are not in $S$. – liwuen Jun 05 '20 at 15:43