It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.3K
- Chat 498
- Study Groups 16
- Petri Nets 7
- Epidemiology 3
- Leaf Modeling 1
- Review Sections 9
- MIT 2020: Programming with Categories 52
- MIT 2020: Lectures 21
- MIT 2020: Exercises 25
- MIT 2019: Applied Category Theory 339
- MIT 2019: Lectures 79
- MIT 2019: Exercises 149
- MIT 2019: Chat 50
- UCR ACT Seminar 4
- General 65
- Azimuth Code Project 110
- Statistical methods 2
- Drafts 2
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 147
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 707

Options

## Comments

It is not a total order. Specifically, to be a total order it must satisfy the

trichotomyrequirement. It's sufficient to provide a counterexample here: 2 and 3. \(2 \nleq 3\) and \(3 \nleq 2\).`![figure](https://docs.google.com/drawings/d/e/2PACX-1vSY0m8Zr8dYWlNJIH0By_6EoeKYYkbKhx0VOEdxoqWbTHAbYEjdnULroyiF8pgpBXOc1fupkVGbAoq6/pub?w=354&h=349) It is not a total order. Specifically, to be a total order it must satisfy the *trichotomy* requirement. It's sufficient to provide a counterexample here: 2 and 3. \\(2 \nleq 3\\) and \\(3 \nleq 2\\).`

On the other hand, we can get quite nice graded lattices out of the divisibility relation. For better or for worse, these are usually what I visualize when I think of lattices.

`On the other hand, we can get quite nice [graded lattices](https://en.wikipedia.org/wiki/Graded_poset) out of the divisibility relation. For better or for worse, these are usually what I visualize when I think of lattices. [![Divisibility lattice](https://i.stack.imgur.com/k6oX5.jpg)](https://math.stackexchange.com/a/1838291)`

For the extra credit, I

wantto say that the poset on \(\mathbb{Z}^+\) ordered by divisibility is isomorphic to the product of a countably infinite number copies of \(\mathbb{N}\). It's really the lattice of multisets ("bags") over the set of primes, which falls out neatly from the prime factorization theorem. (A lattice is a poset with all finite joins and meets.) I'm not sure this really meets the bar of a "characterization", but I'll write it out anyway.(

EDIT:This argument fails to account for the fact that the multiset of prime factors for a positive integeris finite. We're essentially throwing out any multiset that's "too large". So my final statement is a bit of a lie, because we have to restrict our attention to a certain kind of multiset. Ithinkthis is similar to the difference between the product topology and the box topology. The product topology requires all but finitely many components to be trivial, whereas the box topology relaxes this constraint entirely. Essentially, I'm assuming a box product below, where I need to use the categorical product. I think this is solvable by sprinkling in the phrase "of finite support" liberally.)(

EDIT 2:I suspect this might be a kind of restricted wreath product, which is based on the idea of a direct sum, which makes the same finite support distinction as the box/product topology above. It seems like we're actually looking at a categoricalcoproduct, even though in the case of topological spaces it's theproductthat requires finite support. This is fascinating, and I hope I'm reading all of this properly.)Recall that the indicator function of a set \(X \subseteq U\) is a map \(\mathbf{1}_X : U \to \mathbb{B}\) such that \(\mathbf{1}_X(x) = \mathrm{true}\) iff \(x \in X\). We can generalize this to multisets by considering maps \(\mathbb{N}_X : U \to \mathbb{N}\), mapping each element of \(U\) to the number of times it appears in \(X\). The subset relation for multisets is given by \(X \subseteq Y\) iff \(\mathbb{N}_X(u) \le \mathbb{N}_Y(u)\) for all \(u \in U\). (Notice how regular sets are just multisets that range only over \(\{0, 1\} \subseteq \mathbb{N}\)!)

If we take \(U\) to be \(\mathbb{P}\), the set of prime numbers, we can assign every positive integer \(n \in \mathbb{Z}^+\) a unique map \(\mathbb{P}_x : \mathbb{P} \to \mathbb{N}\) such that $$x = \prod_{p \in \mathbb{P}} p^{\mathbb{P}_x(p)}.$$ The prime factorization theorem gives us a one-to-one correspondence between positive integers and multisets of finite support (so that the product above is well-defined). In other words, the poset of positive integers ordered by division \(\langle \mathbb{Z}^+ , \mid \rangle\) is isomorphic to the poset of multisets over \(\mathbb{P}\). Of course, \(\mathbb{P}\) is only used as an index set at this level of abstraction; all we require is that \(\mathbb{P}\) be a countably infinite set. In other words, this poset is also isomorphic to the poset of maps \(\mathbb{N} \to \mathbb{N}\), which we can also denote as \(\mathbb{N}^\mathbb{N}\), ordered as above. (Exponential notation is nice because it makes it clear why I called this the product of a countably infinite number copies of \(\mathbb{N}\) above: \(\mathbb{N}^\mathbb{N} \cong \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \cdots\).)

So I guess I want to say that this is the unique poset (up to isomorphism) that factors into a countably infinite number of copies of the totally ordered chain \(\mathbb{N}\).

`For the [extra credit](https://forum.azimuthproject.org/discussion/2051/exercises-and-puzzles-3-chapter-1), I _want_ to say that the poset on \\(\mathbb{Z}^+\\) ordered by divisibility is isomorphic to the product of a countably infinite number copies of \\(\mathbb{N}\\). It's really the lattice of [multisets](https://en.wikipedia.org/wiki/Multiset) ("bags") over the set of primes, which falls out neatly from the [prime factorization theorem](https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic). (A [lattice](https://en.wikipedia.org/wiki/Lattice_(order)) is a poset with all finite joins and meets.) I'm not sure this really meets the bar of a "characterization", but I'll write it out anyway. (**EDIT:** This argument fails to account for the fact that the multiset of prime factors for a positive integer _is finite_. We're essentially throwing out any multiset that's "too large". So my final statement is a bit of a lie, because we have to restrict our attention to a certain kind of multiset. I _think_ this is similar to the difference between the [product topology](https://en.wikipedia.org/wiki/Product_topology) and the [box topology](https://en.wikipedia.org/wiki/Box_topology). The product topology requires all but finitely many components to be trivial, whereas the box topology relaxes this constraint entirely. Essentially, I'm assuming a box product below, where I need to use the categorical product. I think this is solvable by sprinkling in the phrase "of finite support" liberally.) (**EDIT 2:** I suspect this might be a kind of [restricted wreath product](https://en.wikipedia.org/wiki/Wreath_product), which is based on the idea of a [direct sum](https://math.stackexchange.com/questions/39895/the-direct-sum-oplus-versus-the-cartesian-product-times#39900), which makes the same finite support distinction as the box/product topology above. It seems like we're actually looking at a categorical _coproduct_, even though in the case of topological spaces it's the _product_ that requires finite support. This is fascinating, and I hope I'm reading all of this properly.) Recall that the [indicator function](https://en.wikipedia.org/wiki/Indicator_function) of a set \\(X \subseteq U\\) is a map \\(\mathbf{1}\_X : U \to \mathbb{B}\\) such that \\(\mathbf{1}\_X(x) = \mathrm{true}\\) iff \\(x \in X\\). We can generalize this to multisets by considering maps \\(\mathbb{N}\_X : U \to \mathbb{N}\\), mapping each element of \\(U\\) to the number of times it appears in \\(X\\). The subset relation for multisets is given by \\(X \subseteq Y\\) iff \\(\mathbb{N}\_X(u) \le \mathbb{N}\_Y(u)\\) for all \\(u \in U\\). (Notice how regular sets are just multisets that range only over \\(\\{0, 1\\} \subseteq \mathbb{N}\\)!) If we take \\(U\\) to be \\(\mathbb{P}\\), the set of prime numbers, we can assign every positive integer \\(n \in \mathbb{Z}^+\\) a unique map \\(\mathbb{P}\_x : \mathbb{P} \to \mathbb{N}\\) such that $$x = \prod_{p \in \mathbb{P}} p^{\mathbb{P}_x(p)}.$$ The prime factorization theorem gives us a one-to-one correspondence between positive integers and multisets of [finite support](https://en.wikipedia.org/wiki/Multiset#Basic_properties_and_operations) (so that the product above is well-defined). In other words, the poset of positive integers ordered by division \\(\langle \mathbb{Z}^+ , \mid \rangle\\) is isomorphic to the poset of multisets over \\(\mathbb{P}\\). Of course, \\(\mathbb{P}\\) is only used as an index set at this level of abstraction; all we require is that \\(\mathbb{P}\\) be a countably infinite set. In other words, this poset is also isomorphic to the poset of maps \\(\mathbb{N} \to \mathbb{N}\\), which we can also denote as \\(\mathbb{N}^\mathbb{N}\\), ordered as above. (Exponential notation is nice because it makes it clear why I called this the product of a countably infinite number copies of \\(\mathbb{N}\\) above: \\(\mathbb{N}^\mathbb{N} \cong \mathbb{N} \times \mathbb{N} \times \mathbb{N} \times \cdots\\).) So I guess I want to say that this is the unique poset (up to isomorphism) that factors into a countably infinite number of copies of the totally ordered chain \\(\mathbb{N}\\).`

I follow the nice Jonathan's reasoning. Another take from the book of Birkhoff on lattice theory, says that chains are distributive lattices, the direct product of a set of chains still is a distributive lattice, as well as any sublattice, and then: prime powers form chains under the GCD meet operation, and the divisibility lattice of the naturals is seen as a sublattice of the direct product of those chains.

`I follow the nice Jonathan's reasoning. Another take from the book of Birkhoff on lattice theory, says that chains are distributive lattices, the direct product of a set of chains still is a distributive lattice, as well as any sublattice, and then: prime powers form chains under the GCD meet operation, and the divisibility lattice of the naturals is seen as a sublattice of the direct product of those chains.`