Show natural numbers ordered by divisibility is a distributive lattice.












0












$begingroup$


I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with gcd as AND and lcm as OR.



I know it can be shown that
a AND (b OR c) >= (a AND b) OR (a AND c)
for a general lattice, and that if we can show the opposite, that
a AND (b OR c) <= (a AND b) OR (a AND c)
that implies the two are equal. How do I prove this second part? I am not experienced with number theory, and I have struggled to get a meaningful expression of gcd's and lcm's.



Alternatively, is there a different way you can show me how to prove this?



Thank you!










share|cite|improve this question









$endgroup$

















    0












    $begingroup$


    I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with gcd as AND and lcm as OR.



    I know it can be shown that
    a AND (b OR c) >= (a AND b) OR (a AND c)
    for a general lattice, and that if we can show the opposite, that
    a AND (b OR c) <= (a AND b) OR (a AND c)
    that implies the two are equal. How do I prove this second part? I am not experienced with number theory, and I have struggled to get a meaningful expression of gcd's and lcm's.



    Alternatively, is there a different way you can show me how to prove this?



    Thank you!










    share|cite|improve this question









    $endgroup$















      0












      0








      0


      1



      $begingroup$


      I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with gcd as AND and lcm as OR.



      I know it can be shown that
      a AND (b OR c) >= (a AND b) OR (a AND c)
      for a general lattice, and that if we can show the opposite, that
      a AND (b OR c) <= (a AND b) OR (a AND c)
      that implies the two are equal. How do I prove this second part? I am not experienced with number theory, and I have struggled to get a meaningful expression of gcd's and lcm's.



      Alternatively, is there a different way you can show me how to prove this?



      Thank you!










      share|cite|improve this question









      $endgroup$




      I need a proof that the set of natural numbers with the the relationship of divisibility form a distributive lattice with gcd as AND and lcm as OR.



      I know it can be shown that
      a AND (b OR c) >= (a AND b) OR (a AND c)
      for a general lattice, and that if we can show the opposite, that
      a AND (b OR c) <= (a AND b) OR (a AND c)
      that implies the two are equal. How do I prove this second part? I am not experienced with number theory, and I have struggled to get a meaningful expression of gcd's and lcm's.



      Alternatively, is there a different way you can show me how to prove this?



      Thank you!







      divisibility lattice-orders natural-numbers






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 10 '14 at 1:49









      xaelxael

      11




      11






















          2 Answers
          2






          active

          oldest

          votes


















          2












          $begingroup$

          We will construct a function from the natural numbers onto a distributive lattice, namely the lattice of all infinite sequences of natural numbers, all but finitely many of which are 0, with coordinatewise maximum as the join and coordinatewise minimum as the meet. The function is a lattice isomorphism. Let $p_1,p_2,ldots$ be all prime numbers indexed in order. If
          $$n=p_1^{i_1}p_2^{i_2}cdots$$
          map $nmapsto (i_1,i_2,i_3,ldots)$. Then this is a lattice homomorphism, join corresponds to LCM and meet corresponds to GCD.



          If you can't use this answer directly, consider this as a hint that LCM means you are taking the maximum of all powers of particular primes among the two numbers and GCD means you're taking the minimum.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
            $endgroup$
            – xael
            Dec 10 '14 at 2:18












          • $begingroup$
            Totally got it now. Thanks
            $endgroup$
            – xael
            Dec 10 '14 at 12:51










          • $begingroup$
            @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
            $endgroup$
            – Matt Samuel
            Dec 10 '14 at 16:22



















          1












          $begingroup$

          Picking on Matt Samuel's answer, the reason for which it works is that, if the prime divisors of $a,b,c in mathbb N$ are $p_1, ldots, p_n$, so that



          $$a=p_1^{i_1}cdot cdots cdot p_n^{i_n}, quad b=p_1^{j_1}cdot cdots cdot p_n^{j_n}, ;text{ and }; c=p_1^{k_1}cdot cdots cdot p_n^{k_n},$$



          with $i_r,j_r,k_r geq 0$, for $1leq r leq n$, then



          $$gcd{a,b} = p_1^{alpha_1}cdot cdots cdot p_n^{alpha_n}quadtext{and}quadmathrm{lcm}{a,b} = p_1^{beta_1}cdot cdots cdot p_n^{beta_n},$$



          where $alpha_r = min{i_r,j_r}$ and $beta_r=max{i_r,j_r}$.



          Since, for $u,v,w in mathbb N$
          $$max{ min{u,v}, min{u,w} } = min{ u, max{v,w} }$$
          (easy to check), it follows that
          $$gcd{ a,mathrm{lcm}{b,c} } = mathrm{lcm}{ gcd{a,b}, gcd{a,c} },$$
          that is,
          $$a wedge (b vee c) = (a wedge b) vee (a wedge c),$$
          taking "$gcd$" as "$wedge$" and "$mathrm{lcm}$" as "$vee$", with infix notation.






          share|cite|improve this answer









          $endgroup$














            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1060198%2fshow-natural-numbers-ordered-by-divisibility-is-a-distributive-lattice%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            2












            $begingroup$

            We will construct a function from the natural numbers onto a distributive lattice, namely the lattice of all infinite sequences of natural numbers, all but finitely many of which are 0, with coordinatewise maximum as the join and coordinatewise minimum as the meet. The function is a lattice isomorphism. Let $p_1,p_2,ldots$ be all prime numbers indexed in order. If
            $$n=p_1^{i_1}p_2^{i_2}cdots$$
            map $nmapsto (i_1,i_2,i_3,ldots)$. Then this is a lattice homomorphism, join corresponds to LCM and meet corresponds to GCD.



            If you can't use this answer directly, consider this as a hint that LCM means you are taking the maximum of all powers of particular primes among the two numbers and GCD means you're taking the minimum.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
              $endgroup$
              – xael
              Dec 10 '14 at 2:18












            • $begingroup$
              Totally got it now. Thanks
              $endgroup$
              – xael
              Dec 10 '14 at 12:51










            • $begingroup$
              @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
              $endgroup$
              – Matt Samuel
              Dec 10 '14 at 16:22
















            2












            $begingroup$

            We will construct a function from the natural numbers onto a distributive lattice, namely the lattice of all infinite sequences of natural numbers, all but finitely many of which are 0, with coordinatewise maximum as the join and coordinatewise minimum as the meet. The function is a lattice isomorphism. Let $p_1,p_2,ldots$ be all prime numbers indexed in order. If
            $$n=p_1^{i_1}p_2^{i_2}cdots$$
            map $nmapsto (i_1,i_2,i_3,ldots)$. Then this is a lattice homomorphism, join corresponds to LCM and meet corresponds to GCD.



            If you can't use this answer directly, consider this as a hint that LCM means you are taking the maximum of all powers of particular primes among the two numbers and GCD means you're taking the minimum.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
              $endgroup$
              – xael
              Dec 10 '14 at 2:18












            • $begingroup$
              Totally got it now. Thanks
              $endgroup$
              – xael
              Dec 10 '14 at 12:51










            • $begingroup$
              @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
              $endgroup$
              – Matt Samuel
              Dec 10 '14 at 16:22














            2












            2








            2





            $begingroup$

            We will construct a function from the natural numbers onto a distributive lattice, namely the lattice of all infinite sequences of natural numbers, all but finitely many of which are 0, with coordinatewise maximum as the join and coordinatewise minimum as the meet. The function is a lattice isomorphism. Let $p_1,p_2,ldots$ be all prime numbers indexed in order. If
            $$n=p_1^{i_1}p_2^{i_2}cdots$$
            map $nmapsto (i_1,i_2,i_3,ldots)$. Then this is a lattice homomorphism, join corresponds to LCM and meet corresponds to GCD.



            If you can't use this answer directly, consider this as a hint that LCM means you are taking the maximum of all powers of particular primes among the two numbers and GCD means you're taking the minimum.






            share|cite|improve this answer









            $endgroup$



            We will construct a function from the natural numbers onto a distributive lattice, namely the lattice of all infinite sequences of natural numbers, all but finitely many of which are 0, with coordinatewise maximum as the join and coordinatewise minimum as the meet. The function is a lattice isomorphism. Let $p_1,p_2,ldots$ be all prime numbers indexed in order. If
            $$n=p_1^{i_1}p_2^{i_2}cdots$$
            map $nmapsto (i_1,i_2,i_3,ldots)$. Then this is a lattice homomorphism, join corresponds to LCM and meet corresponds to GCD.



            If you can't use this answer directly, consider this as a hint that LCM means you are taking the maximum of all powers of particular primes among the two numbers and GCD means you're taking the minimum.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Dec 10 '14 at 1:58









            Matt SamuelMatt Samuel

            39.1k63770




            39.1k63770












            • $begingroup$
              Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
              $endgroup$
              – xael
              Dec 10 '14 at 2:18












            • $begingroup$
              Totally got it now. Thanks
              $endgroup$
              – xael
              Dec 10 '14 at 12:51










            • $begingroup$
              @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
              $endgroup$
              – Matt Samuel
              Dec 10 '14 at 16:22


















            • $begingroup$
              Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
              $endgroup$
              – xael
              Dec 10 '14 at 2:18












            • $begingroup$
              Totally got it now. Thanks
              $endgroup$
              – xael
              Dec 10 '14 at 12:51










            • $begingroup$
              @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
              $endgroup$
              – Matt Samuel
              Dec 10 '14 at 16:22
















            $begingroup$
            Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
            $endgroup$
            – xael
            Dec 10 '14 at 2:18






            $begingroup$
            Hey Matt,I appreciate the reply. There are a few details missing from the lattice of infinite sequences of natural numbers... or perhaps I'm not understanding them as presented. Are these sequences of unique numbers or can they contain the same numbers multiple times? If they cannot contain the same number twice then an infinite sequence has no bound on the maximum value in it (is that what "coordinate wise max" means?), right?
            $endgroup$
            – xael
            Dec 10 '14 at 2:18














            $begingroup$
            Totally got it now. Thanks
            $endgroup$
            – xael
            Dec 10 '14 at 12:51




            $begingroup$
            Totally got it now. Thanks
            $endgroup$
            – xael
            Dec 10 '14 at 12:51












            $begingroup$
            @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
            $endgroup$
            – Matt Samuel
            Dec 10 '14 at 16:22




            $begingroup$
            @xael sorry I didn't respond, I only saw your comment before the edit, which only said you appreciated the reply. Glad you figured it out.
            $endgroup$
            – Matt Samuel
            Dec 10 '14 at 16:22











            1












            $begingroup$

            Picking on Matt Samuel's answer, the reason for which it works is that, if the prime divisors of $a,b,c in mathbb N$ are $p_1, ldots, p_n$, so that



            $$a=p_1^{i_1}cdot cdots cdot p_n^{i_n}, quad b=p_1^{j_1}cdot cdots cdot p_n^{j_n}, ;text{ and }; c=p_1^{k_1}cdot cdots cdot p_n^{k_n},$$



            with $i_r,j_r,k_r geq 0$, for $1leq r leq n$, then



            $$gcd{a,b} = p_1^{alpha_1}cdot cdots cdot p_n^{alpha_n}quadtext{and}quadmathrm{lcm}{a,b} = p_1^{beta_1}cdot cdots cdot p_n^{beta_n},$$



            where $alpha_r = min{i_r,j_r}$ and $beta_r=max{i_r,j_r}$.



            Since, for $u,v,w in mathbb N$
            $$max{ min{u,v}, min{u,w} } = min{ u, max{v,w} }$$
            (easy to check), it follows that
            $$gcd{ a,mathrm{lcm}{b,c} } = mathrm{lcm}{ gcd{a,b}, gcd{a,c} },$$
            that is,
            $$a wedge (b vee c) = (a wedge b) vee (a wedge c),$$
            taking "$gcd$" as "$wedge$" and "$mathrm{lcm}$" as "$vee$", with infix notation.






            share|cite|improve this answer









            $endgroup$


















              1












              $begingroup$

              Picking on Matt Samuel's answer, the reason for which it works is that, if the prime divisors of $a,b,c in mathbb N$ are $p_1, ldots, p_n$, so that



              $$a=p_1^{i_1}cdot cdots cdot p_n^{i_n}, quad b=p_1^{j_1}cdot cdots cdot p_n^{j_n}, ;text{ and }; c=p_1^{k_1}cdot cdots cdot p_n^{k_n},$$



              with $i_r,j_r,k_r geq 0$, for $1leq r leq n$, then



              $$gcd{a,b} = p_1^{alpha_1}cdot cdots cdot p_n^{alpha_n}quadtext{and}quadmathrm{lcm}{a,b} = p_1^{beta_1}cdot cdots cdot p_n^{beta_n},$$



              where $alpha_r = min{i_r,j_r}$ and $beta_r=max{i_r,j_r}$.



              Since, for $u,v,w in mathbb N$
              $$max{ min{u,v}, min{u,w} } = min{ u, max{v,w} }$$
              (easy to check), it follows that
              $$gcd{ a,mathrm{lcm}{b,c} } = mathrm{lcm}{ gcd{a,b}, gcd{a,c} },$$
              that is,
              $$a wedge (b vee c) = (a wedge b) vee (a wedge c),$$
              taking "$gcd$" as "$wedge$" and "$mathrm{lcm}$" as "$vee$", with infix notation.






              share|cite|improve this answer









              $endgroup$
















                1












                1








                1





                $begingroup$

                Picking on Matt Samuel's answer, the reason for which it works is that, if the prime divisors of $a,b,c in mathbb N$ are $p_1, ldots, p_n$, so that



                $$a=p_1^{i_1}cdot cdots cdot p_n^{i_n}, quad b=p_1^{j_1}cdot cdots cdot p_n^{j_n}, ;text{ and }; c=p_1^{k_1}cdot cdots cdot p_n^{k_n},$$



                with $i_r,j_r,k_r geq 0$, for $1leq r leq n$, then



                $$gcd{a,b} = p_1^{alpha_1}cdot cdots cdot p_n^{alpha_n}quadtext{and}quadmathrm{lcm}{a,b} = p_1^{beta_1}cdot cdots cdot p_n^{beta_n},$$



                where $alpha_r = min{i_r,j_r}$ and $beta_r=max{i_r,j_r}$.



                Since, for $u,v,w in mathbb N$
                $$max{ min{u,v}, min{u,w} } = min{ u, max{v,w} }$$
                (easy to check), it follows that
                $$gcd{ a,mathrm{lcm}{b,c} } = mathrm{lcm}{ gcd{a,b}, gcd{a,c} },$$
                that is,
                $$a wedge (b vee c) = (a wedge b) vee (a wedge c),$$
                taking "$gcd$" as "$wedge$" and "$mathrm{lcm}$" as "$vee$", with infix notation.






                share|cite|improve this answer









                $endgroup$



                Picking on Matt Samuel's answer, the reason for which it works is that, if the prime divisors of $a,b,c in mathbb N$ are $p_1, ldots, p_n$, so that



                $$a=p_1^{i_1}cdot cdots cdot p_n^{i_n}, quad b=p_1^{j_1}cdot cdots cdot p_n^{j_n}, ;text{ and }; c=p_1^{k_1}cdot cdots cdot p_n^{k_n},$$



                with $i_r,j_r,k_r geq 0$, for $1leq r leq n$, then



                $$gcd{a,b} = p_1^{alpha_1}cdot cdots cdot p_n^{alpha_n}quadtext{and}quadmathrm{lcm}{a,b} = p_1^{beta_1}cdot cdots cdot p_n^{beta_n},$$



                where $alpha_r = min{i_r,j_r}$ and $beta_r=max{i_r,j_r}$.



                Since, for $u,v,w in mathbb N$
                $$max{ min{u,v}, min{u,w} } = min{ u, max{v,w} }$$
                (easy to check), it follows that
                $$gcd{ a,mathrm{lcm}{b,c} } = mathrm{lcm}{ gcd{a,b}, gcd{a,c} },$$
                that is,
                $$a wedge (b vee c) = (a wedge b) vee (a wedge c),$$
                taking "$gcd$" as "$wedge$" and "$mathrm{lcm}$" as "$vee$", with infix notation.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered May 9 '18 at 21:39









                amrsaamrsa

                3,8452618




                3,8452618






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f1060198%2fshow-natural-numbers-ordered-by-divisibility-is-a-distributive-lattice%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Bressuire

                    Cabo Verde

                    Gyllenstierna