Glory to Arstotzka—The Glorious Infinite Regiment

There are 7 different medals in the Arstotzkan army, which may be awarded multiple times to indicate glory. For any two distinct collections of medals, one is decisively more glorious than the other. However, the bureaucratic rules for determining exactly which of the two is more glorious is unreasonably complicated. All you know is that "more glorious" is a transitive relation, and that earning another medal will always render you more glorious than you were before.

Prove that every (potentially infinite) regiment of Arstotzkan soldiers has a least glorious member.

• For each soldier, is the collection of medals that they have always finite? Jul 7, 2020 at 4:17
• Also, if every soldier has the same collection of medals, then all of them will be part of the least glorious member, right? Jul 7, 2020 at 4:22
• Indeed, each soldier has a finite number of medals. In the event that two soldiers share the same set of medals, they should be considered equally glorious—or equally least glorious, as the case may be. Jul 7, 2020 at 4:47
• This follows immediately from Dickson's Lemma Jul 7, 2020 at 13:00
• @Magma I see you've found one mathematical theorem that's equivalent to this problem—personally I crafted it from Hilbert's basis theorem as applied to custom monomial orders (see: Grobner basis stuff). Jul 8, 2020 at 15:33

An empty regiment has no least glorious member, and I wouldn't put it past Arstotzka to make empty regiments. For nonempty regiments, though, and counting two soldiers as both least glorious if they tie...

For there to be no least glorious soldier in a nonempty regiment, we need an infinite sequence of less glorious soldiers. Assume for contradiction we have such a sequence $$(S_n)_{n \in \mathbb{N}}$$.

Number the medal types from 1 to 7, and denote the number of medals of type $$k$$ a soldier $$S$$ has as $$m_k(S)$$. The sequence $$(m_1(S_n))_{n \in \mathbb{N}}$$ of type-1 medal counts of the $$S_n$$ soldiers is an infinite sequence of nonnegative integers, and thus must contain an infinite non-decreasing subsequence. Let $$(S_n^1)_{n \in \mathbb{N}}$$ be a subsequence of $$(S_n)_{n \in \mathbb{N}}$$ with non-decreasing numbers of type-1 medals.

Similarly, $$(S_n^1)_{n \in \mathbb{N}}$$ must contain an infinite subsequence $$(S_n^2)_{n \in \mathbb{N}}$$ with non-decreasing numbers of type-2 medals (and non-decreasing numbers of type-1 medals, as it's a subsequence of $$(S_n^1)_{n \in \mathbb{N}}$$), and $$(S_n^2)_{n \in \mathbb{N}}$$ must contain an infinite subsequence $$(S_n^3)_{n \in \mathbb{N}}$$ with non-decreasing type-3 medals, and so on all the way up to $$(S_n^7)_{n \in \mathbb{N}}$$, which has non-decreasing numbers of every type of medal.

However, for one soldier to be less glorious than another, the first soldier must have less of at least one medal type than the other. $$(S_n^7)_{n \in \mathbb{N}}$$ was constructed as a subsequence of a sequence of successively less glorious soldiers, but its soldiers cannot be successively less glorious.

This is a contradiction, so the original regiment cannot have an infinite sequence of less glorious soldiers, and it must thus have a least glorious soldier.

• Ahh, nice. This is the proof I was working towards. Nice use of that subsequence. Jul 7, 2020 at 13:14
• My inner Bourbakist is satisfied. Nice. Jul 7, 2020 at 13:20

Here is another try using induction on the number of medals. Assume that for $$n$$ medals and all possible notions of gloriousness there is always a soldier with least glory (which is clear for $$n=1$$). Now look at the situation with $$n+1$$ medals. Pick one soldier $$x$$. Then for each soldier $$y$$ with less glory than $$x$$ ($$y), there is a medal number $$i$$ such that $$y$$ has less medals of type $$i$$ than $$x$$ (written $$y_i), as otherwise $$y$$ has at least as many medals of each type as $$x$$ given $$y$$ at least the same glory as $$x$$. Define $$S_i:= \{ y : \ y Now each $$S_i$$ has a soldier with least glory: For each number $$j\in \{0\dots x_i-1\}$$ of medals of type $$i$$, there is (per induction assumption) a soldier of least glory among those with $$j$$ medals of type $$i$$: We can define a modified glory-function on these soldiers: it is the original glory applied to a set of $$n$$ types (not of type $$i$$) of medals plus $$j$$ medals of type $$i$$. This modified glory depends only on the number of types of $$n$$ medals, and satisfies the assumption of the OP. So we can apply the induction hypothesis.
Of this $$x_i$$-many there is a soldier of least glory, giving us the soldier of least glory in $$S_i$$ for each $$i=1\dots n+1$$. Of these $$n+1$$ many, there is a soldier of least glory, which is the soldier of least glory of the whole army.

• I think your proof suffers from the same flaw as Deusovi's: the assumption that the induction hypothesis applies to a subset of people with a fixed number of one medal, and n other medals. This does not seem obvious to me, except to the extent that the whole thing is "obvious" by well-ordering. Jul 7, 2020 at 7:34
• @JeremyDover This can be repaired by assuming the induction hypothesis is true for all gloriousness functions according to the OP. (Instead of the induction hypotheses is true for the one given function)
– daw
Jul 7, 2020 at 9:07
• I marked the edits to reflect this by italic letters.
– daw
Jul 7, 2020 at 9:07
• I think this basically works, though my inner Bourbakist remains unsatisfied. I would change the definition of $S_i$ to use $<=$ instead of $<$. As it stands some of your $S_i$ can be empty. Allowing equality ensures $x$ is in each $S_i$. If $x$ is the least element, your proof may fail due to all $S_i$ being empty. Jul 7, 2020 at 11:32