Glory to Arstotzka—The Glorious Infinite Regiment

Question

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.

Answer 1

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.

Answer 2

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<x$), there is a medal number $i$ such that $y$ has less medals of type $i$ than $x$ (written $y_i<x_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<x, \ y_i<x_i\}. $$ 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.

Answer 3

An answer without using induction:

Let's introduce a partial ordering on the set of medal sets. Define that a set A precedes another set B if and only if some (including zero) medals can be added to A to form B. Obviously, the least glorious set in a regiment cannot be preceded by any distinct set of that regiment, so we can pick all soldiers that are not preceded by others, and since this subset of soldiers must be finite, we can select the least glorious one of them which would be the least glorious of the entire regiment.