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

- All Categories 2.4K
- Chat 505
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 75
- Azimuth Code Project 111
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 719

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