Wikipedia:Reference desk/Archives/Mathematics/2022 July 27

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 27

Categories, Rings, and Fields (oh my!)

I'm taking a break from my normal work to just indulge in some abstract math that is way over my head but I just love even trying to understand 1% of it. I've been interested in Category Theory since the 90's when Object-Oriented Programming was still a new thing in Computer Science (my real job) and some guys I respected immensely in the Formal Methods community thought Category Theory was THE answer as to how to define specifications for OOP (as well as the answer to the meaning of life the universe and everything... exaggerating but just a bit, these were guys who never got outwardly excited about anything and they behaved like my daughter at a Pink concert when you mentioned Category Theory). I'm just trying to learn the very basics so I always start with subsumption hierarchies. One of the things that always confused me as I started reading about CT was what is a category compared to a group, a field, etc. After reading the opening paragraphs of the various articles I've come up with the following hierarchy:

 Category
   Set
     Ring
       Field

I.e., all Fields are Rings, all Rings are Sets and all Sets are Categories. Correct so far? If yes then what else is a Category that isn't a set?

Also, the article says that Category theory is an alternative to Set theory as the foundation for math. Does that mean that Category Theory and Set Theory essentially are equivalent? My understanding is that Intuitionist Logic is also an alternative to ZFC Set Theory but that someone proved that the two were equivalent. I.e., anything you can prove in one you could prove in the other and vice versa. Assuming I'm correct about Intuitionist Logic and ZFC is the same true for Category Theory and ZFC? Or are there some things that can be proven with Category Theory but not with ZFC, or vice versa?

Any feedback would be appreciated. 03:20, 27 July 2022 (UTC) MadScientistX11 (talk) 03:20, 27 July 2022 (UTC)

In the classic definition, fields are algebraic structures with the same signature as rings, but satisfying stronger axioms. This implies that every field is also a ring. Every ring is a monoid in two different ways. These algebraic structures can be formally defined as a triple (Σ, Ω, Ξ), in which Σ is a set (the "carrier"), Ω is a signature over the carrier, and Ξ is the set of axioms. By dropping the last two of these components, we get a set, and that is what people would normally mean by saying that a field is (also) a set. But this is not entirely trivial. Each of the three components is a set, so in coercing (Σ, Ω, Ξ) to a set, why is that set Σ and not Ξ? This is a matter of convention, and not in any way forced by more fundamental considerations.

Sets are not obviously categories. There are several ways to construct a category C from a given set Σ. The simplest way is to take the discrete category over Σ:

ob(C)    = Σ ;

hom(C) = {1_x｜x ∈ Σ} .

Another way is to use the free monoid over Σ as the hom-set of a one-object category.

There are several ways to formalize set theory and several ways to formalize category theory. In general, the resulting theories are not formally comparable. There is no unique way to position category theory as a foundation of mathematics. Many category theorists are happy enough with ZFC, or, if their sets are getting too large for ZFC, NBG set theory. Inasmuch as one attempts to use topos theory as a foundation, one tends to end up with constructive mathematics, which some think is a Good Thing, but others find too limiting. The latest along these lines is homotopy type theory; the verdict on its touted suitability as a foundation is not yet in.  --Lambiam 08:34, 27 July 2022 (UTC)

@Lambiam: Great feedback thanks. To be honest I didn't follow all of it but it definitely helped. One last thing, I found two books on the Internet for free (and I'm pretty sure these are legitimate free copies not bootlegs). One is Basic Category Theory by Tom Leinstar and the other is Group Theory by J.S. Milne (actually I just realized I need to figure out how Groups fit in here). I thought I would start with the Group Theory book. I doubt I'll finish it but at least the chapters that go over the basic ideas. Any other suggestions regarding good books on these topics? Thanks again for taking the time to explain. MadScientistX11 (talk) 13:21, 27 July 2022 (UTC)

You might start with having a look at lattice theory. Most of the concrete examples of lattices (in the section Lattice (order)#Examples) are elementary and should be familiar. Since a lattice is (equivalent to) a partial order, and therefore also a preorder, it immediately gives rise to a category (see the third paragraph of Category (mathematics) § Examples). If you are familiar with Haskell notation, Category Theory for Programmers may be a good introduction. I have only glanced at it, but here is a positive review that also tells us there is a series of video lessons.  --Lambiam 15:39, 27 July 2022 (UTC)

Just to add, intuitionistic logic and ZFC are not equivalent as you describe. It's a type mismatch to try to compare them. Intuitionistic logic is a type of logic, usually contrasted with classical logic. ZFC is a set of axioms, which is a different sort of thing, and those axioms are generally interpreted in classical logic.2406:E003:812:5001:844C:EAEC:51CE:B55C (talk) 13:23, 27 July 2022 (UTC)

An example highlighting the difference is the axiom of (classical) propositional logic known as the law of excluded middle, in symbolic form P ∨ ¬ P, which asserts that every proposition is either true or false. When working in ZFC, this is assumed to be valid. But it is not an axiom or theorem of intuitionistic logic. The same holds for the axiom or theorem (¬ ¬ P) → P. In intuitionistic logic, the two negations do not cancel.  --Lambiam 15:55, 27 July 2022 (UTC)

Balanced subset of Polytope vertices (with more than two elements)

Let a Balanced subset of Polytope vertices be a subset of the vertices where the vectors from the center of the polytope to the elements of the subset sum to zero.

The subsets that have more than two elements and are not made of the union of multiple two elements subsets.

• The tetrahedron has no balanced subset.
• The cube has two balanced three element subsets which are the two "demi-cubes" of the alternating vertices .
• The Octahedron has no balanced subset that isn't two elements or a union of two elements.
• The 12 vertices of the Icosahedron, I'm not sure whether the six element subsets defined by one vertex and then the ones which are an edge distance of two (forming the narrower of the two Pentagonal pyramids) are a balanced subset.
• The 20 vertices of the Dodecahedron have balanced subsets of the ten two element subsets and the five four element subsets corresponding to the Compound of five tetrahedra, not sure if they have more...

(I think this can be extended to the regular 4-dimensional polytopes, but I'm not sure how.Naraht (talk) 13:28, 27 July 2022 (UTC)

By "subset" you appear to mean a non-empty proper subset. And I guess you are interested specifically in regular polytopes.  --Lambiam 16:01, 27 July 2022 (UTC)

I figure to start with the Regular Polytopes.Naraht (talk) 12:36, 28 July 2022 (UTC)

The question can also be posed for two-dimensional regular polytopes. It seems that the regular n-gon has a non-trivial balanced vertex set if and only if n is composite. Presumably (if true) there is a simple proof, but I don't see it.  --Lambiam 16:14, 27 July 2022 (UTC)

I think you're right. Let r=e^2πi/n. Any set of vertices adding to zero would imply an equation of the form 1+r^k₁+...+r^k_m =0 with k_m<n. But the minimum polynomial of r is 1+r+...+r^n-1 if n is prime. --RDBury (talk) 11:57, 28 July 2022 (UTC)

Nice to see this proved, it seemed insinctively true.Naraht (talk) 12:36, 28 July 2022 (UTC)

The Cartesian coordinates of the 12 vertices of a regular icosahedron with an edge length of 2, centred at the origin and oriented along the coordinate axes, are:

${\begin{array}{l}(~~\,\,0,\,\pm 1,\pm \varphi ),\\(\,\pm 1,\pm \varphi ,~~\,\,0),\\(\pm \varphi ,~~\,\,0,\,\pm 1),\end{array}}$

where $\varphi$ is the golden ratio. (Each line represents four vertices.) To be balanced, any vertex involving a $+1$ must be counterbalanced by one having $-1$ in the same position. Likewise for $+\varphi$ and $-\varphi$. So, for any vertex in a balanced set, the set also contains the antipodal vertex. A balanced vertex set is therefore a set of antipodal pairs, and any such set is balanced.  --Lambiam 15:54, 28 July 2022 (UTC)

Nice. If a balanced set contains a balanced proper subset, then the difference is also balanced. So the problem becomes to find the minimal balanced sets. You can then worry about finding disjoint sets of balanced sets. A similar analysis proves that the minimal balanced sets of an octahedron are antipodal pairs. (This is basically the content of bullet 3 above.) The minimal sets of a cube are the four pairs of antipodal points and the two tetrahedra of alternating vertices. (This is the content of bullet 2 above.) That leaves the dodecahedron, but it has at least the 10 pairs of antipodal points and 10 tetrahedra. For higher dimensions, for the regular n-simplex there is only the simplex itself, and for the n-cross polytope there are the n pairs of antipodal points. The n-cube seems tricky, the 24-,120- and 600-cell as well. --RDBury (talk) 23:03, 28 July 2022 (UTC)

PS. There is a minimal balanced set for the 4-cube of size 4. In fact there are at least 12 of them. Let the vertices be (±1, ±1, ±1, ±1). The plane x₁=x₂ intersects the 4-cube in 8-points that form a rectangular solid with sides 2, 2, 2√2. The two alternating tetrahedra of this solid are minimal balanced sets. There are 5 additional similar planes you can start with, with makes a total of 12 sets. Each tetrahedron has sides of length 2√2, 2√2, 2√2, 2√2, 2√3, 2√3, so they are not regular. This can be generalized to n-cubes for larger n as well. For the 5-cube I get 50 (non-regular) tetrahedrons in 2 shapes. I don't know if there are any more minimal balanced sets for n-cubes; I don't even want to hazard a guess. --RDBury (talk) 00:42, 29 July 2022 (UTC)

PPS. There is a minimal balanced set for the 5-cube of size 6: (1, 1, 1, 1, 1), (1, 1, -1, -1, -1), ( -1, 1, 1, -1,-1), ( -1, -1, 1, 1,-1), (-1, -1, -1, 1, 1), (1, -1, -1, -1, 1). This one doesn't seem to have an easy geometrical interpretation though. It looks like there are ways to generalize to higher dimensions. --RDBury (talk) 01:54, 29 July 2022 (UTC)

If I'm interpreting the problem correctly, I think any minimal balanced set of size k for an n-cube can generate a minimal balanced set of equal size for all larger cubes by just alternating appending 1 and -1 to the beginning of each set to get $(1,x_{1}),(-1,x_{2}),\ldots ,(-1,x_{k})$ (note that by default, k is even.) First, a set constructed this way is clearly balanced. And if we have some balanced subset of this new balanced set, say $(1,x_{a_{1}}),\ldots ,(1,x_{a_{q}}),(-1,x_{b_{1}}),\ldots ,(-1,x_{b_{q}})$ which sum to 0, then $(x_{a_{1}}),\ldots ,(x_{a_{q}}),(x_{b_{1}}),\ldots ,(x_{b_{q}})$ are a balanced subset of the n-cube minimal balanced set that we generated the new set from, and thus by minimality must be the minimal balanced set itself, meaning that the balanced (n+1)-cube set is minimal. This approach should actually yield minimal balanced sets of size 4 for all n-cubes with n at least 3 (as per the tetrahedra mentioned in your comment three levels above) and size 6 for all n-cubes with n at least 5 (as per the comment this is in reply to.) GalacticShoe (talk) 06:27, 29 July 2022 (UTC)

I don't see why the sets $\{(x_{i})\}_{i}$ and $\{(y_{i})\}_{i}$ are necessarily disjoint. Even if they are, why should their union be a minimal balanced set? Note that the cardinality of these vertex sets (if disjoint) remains the same after projection from $\mathbb {R} ^{n{+}1}$ to $\mathbb {R} ^{n}.$ Also, there is no such things as the n-cube minimal set.  --Lambiam 10:47, 29 July 2022 (UTC)

Whoops, communicatory error on my part, forgot that n is already used for the dimension of the cube. I'll rewrite my argument to make it clearer. GalacticShoe (talk) 00:14, 30 July 2022 (UTC)

That's a very interesting construction. In terms of the number of possible balanced sets of a given size, it drastically increases the number of possibilities. For sets with 4 elements, there are 6 ways of choosing the 1's and -1's for a new coordinate, 36 ways to add two new coordinates, etc. That means the number of minimal balanced sets of size 4 for the n-cube is at least on the order of 6ⁿ; I was thinking more like 3ⁿ. It should be feasible to compute the exact number for sets with 4 elements as an application of Burnside's lemma. For sets with a larger number of elements Burnside gets harder and harder to use; instead of a group with 24 elements you're looking at a set with k! elements where k is the number of elements. The problem with this approach is that while it might tell you that the number of sets is >0, it won't tell you how to actually construct one. --RDBury (talk) 14:36, 30 July 2022 (UTC)

PS. According to my calculations, which were a bit more tricky than I was expecting, the number of minimal balanced sets with 4 elements in the n-cube is:

${\frac {6^{n}-3\cdot 4^{n}+3\cdot 2^{n}}{24}}.$

This gives the value 0 for n=1 and 2, and 2 for n=3 (as expected). Pulling out a spreadsheet, the next few values are 24, 200, 1440, 9632 .... This showed up on OEIS as twice sequence A016283. There is a different combinatorial interpretation given there as well. --RDBury (talk) 15:45, 30 July 2022 (UTC)

Real quick, I'd like to note that the OEIS sequence is shifted over by one, in the sense that if we denote the number of minimal balanced 4-sets in the n-cube as b(n), then b(n) = 2a(n-1). I imagine there must be some nice one-to-two mapping from rectangles in (n-1)-cubes to minimal balanced sets in n-cubes, but as it stands I'm not sure what that mapping would be. GalacticShoe (talk) 20:11, 30 July 2022 (UTC)

Given a rectangle with vertices A, B, C, D, lift it to (-A, -1), (B, 1), (-C, -1), (D, 1). (Since rectangles are parallelograms, A + C = B + D.) 66.44.49.56 (talk) 14:37, 31 July 2022 (UTC)

Term for "lowest possible value above X, given available values to sum up"

Sometimes when I'm online shopping I like to see how low I can get the total price to be while still being above the minimum for free shipping, with the right combination of items. I think there's a mathematical term for a value that fulfills this criterion, or the process of trying to add up available values to get to it, but I can't remember it. What word or concept am I looking for? 24.43.123.79 (talk) 18:01, 27 July 2022 (UTC)

I'd say, "(try to) reach the threshold for free shipping", like foolishgrunt said here. This is not specifically mathematical terminology; "reach the threshold" is used in other contexts as well.^[1][2][3] By the way, if a web shop states "free shipping for orders over $50", this threshold is, strictly speaking, $50.01. Most web shops will write "free shipping for orders of $50 or more", or "for orders of at least $50", and then the threshold is $50.00.  --Lambiam 18:59, 27 July 2022 (UTC)

The term is "least upper bound", or supremum.

As a distracting side note, keep in mind that if the partially ordered set P were in this case to represent something like "all goods available currently to purchase on Amazon", then it's a finite set and the possible subset(s) of items in your cart S can be exactly determined based on the conditions you described, and the supremum of S ($25 to get free shipping, say) must be in the possible S.

But if, on the other hand (and I think I need backup on this because I never took measure theory), you were to define P as something like "all goods potentially/hypothetically available on Amazon ever," then P might not have an upper bound, and if in this hypothetical eternity the laws restricting consumer pricing were also infinitely flexible, then if the minimum threshold price is something one must exceed and not merely meet (and thus the maximum price of a single item in your cart for the cart to meet the minimum threshold is infinitesimally above $25), you would have an essential supremum of $25. SamuelRiv (talk) 19:09, 27 July 2022 (UTC)

This is very similar to the knapsack problem, (finding the greatest possible value below X, given available values to sum up) catslash (talk) 00:55, 28 July 2022 (UTC)

The subset sum problem is even closer. --116.86.4.41 (talk) 09:32, 31 July 2022 (UTC)

The subset sum problem can trivially be reduced to this problem (finding the least sum reaching a given threshold), so it is also in NP.  --Lambiam 11:22, 31 July 2022 (UTC)