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

- All Categories 2.2K
- Applied Category Theory Course 356
- Applied Category Theory Seminar 4
- Exercises 149
- Discussion Groups 50
- How to Use MathJax 15
- Chat 482
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 149
- Azimuth Forum 29
- Azimuth Project 189
- - Strategy 108
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 711
- - Latest Changes 701
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 21
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 42

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.`