Show natural numbers ordered by divisibility is a distributive lattice.
$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!
divisibility lattice-orders natural-numbers
$endgroup$
add a comment |
$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!
divisibility lattice-orders natural-numbers
$endgroup$
add a comment |
$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!
divisibility lattice-orders natural-numbers
$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
divisibility lattice-orders natural-numbers
asked Dec 10 '14 at 1:49
xaelxael
11
11
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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.
$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
add a comment |
$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.
$endgroup$
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
$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
add a comment |
$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.
$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
add a comment |
$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.
$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.
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
add a comment |
$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
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered May 9 '18 at 21:39
amrsaamrsa
3,8452618
3,8452618
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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