Options

Exercise 32 - Chapter 1

edited April 2018 in Exercises

Write down the numbers \(1, 2, \ldots, 10\) and draw an arrow \(a \to b\) if \(a\) divides perfectly into \(b\). Is it a total order?

Comments

  • 1.
    edited April 2018

    figure

    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\).

    Comment Source:![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\\).
  • 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.

    Divisibility lattice

    Comment Source: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)
  • 3.
    edited April 2018

    For the extra credit, 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 ("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 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 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 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 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}\).

    Comment Source: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}\\).
  • 4.
    edited April 2018

    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.

    Comment Source: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.
Sign In or Register to comment.