Infinite ordinals from a well-ordering

Question

Your task is to write a short program that represents a large (infinite) ordinal, using a well-ordering of the set of positive integers. Your program will take two different positive integers and indicate which one is greater in your chosen well-ordering. The order type of the well-order is the represented ordinal. The challenge is to min-max your code size and the represented ordinal respectively.

Explanation

Usually the positive integers are ordered like so:

1, 2, 3, 4, 5, ...

In this ordering, the expressions: 2 < 5, 1 < 2, 3 < 19, are true, as usual. The expressions 5 < 2, 10 < 3, and so on, are false. However, we can order the positive integers also in the following way:

2, 4, 6, 8, 10, ..., 1, 3, 5, 7, ...

Here all the even numbers are followed by all the odd numbers. Now the expressions 2 < 1, 6 < 8, 1 < 5, 100 < 51 are true, and the expressions 101 < 2 5 < 3 and 120 < 110 are false.

This is another well-ordering:

2, 4, 6, 8, 10, ..., 3, 9, 15, 21, ..., 5, 25, 35, 55, ..., 7, 49, 77, ..., ..., 1

First we have all the even numbers, then all the remaining numbers that are divisible by 3, then ones that are divisible by 5 and so on. Finally, at the very end is 1. Notice that we have a nested "...". This is allowed. What is not allowed is a "..." that starts from the left.

1, 3, 5, 7, 9, ..., ..., 10, 8, 6, 4, 2

This is not a well-order (just a total order). A more rigorous way of stating this rule is that every nonempty subset must have a smallest element. Here the subset of even numbers doesn't have a smallest element.

Another way of looking at this, is to imagine starting from the right and walking to the left. You can jump over an arbitrary (possibly infinite) amount of numbers, but you have to always go left. If the numbers are well-ordered, your walk will always take a finite amount of steps. In this example however, you can just stay on the even side, by never jumping over the three dots, thus never reaching the beginning.

Notice that if you lay the three well-orders on top of each other like so:

1, 2, 3, 4, 5,  ...
2, 4, 6, 8, 10, ..., 1, 3, 5,  7,  ...
2, 4, 6, 8, 10, ..., 3, 9, 15, 21, ..., 5, 25, ..., ..., 1

They have different "length". The bottom one is the longest, and the top one is the shortest. The "length" is called the "order type", and it can be measured with an ordinal. Our first well-order has order type \$\omega\$, the second one \$\omega\cdot2\$ and the third one is \$\omega^2+1\$

Your program will compare two positive integers, according to a well-ordering of your choice. That way your program will represent the order type of your well-order.

For more info on ordinals, visit the Wikipedia page for ordinals and ordinal arithmetic. For more ordinals, visit Googology Wiki. Also check out the previous infinite ordinal question on Code Golf.

More ordinal examples

\$\omega\$ 1, 3, 2, 4, 5, 7, 6, 8, ...

\$\omega^2\$ 1, 2, 4, 8, 16, ..., 3, 5, 6, 9, 10, 12, 17, 18, ..., 7, 11, 13, 14, 19, 21, 22, ..., 15, 23, 27, ..., ... (popcount then value)

\$\omega^2+\omega\$ 2, 4, 8, 16, 32, ..., 3, 9, 27, 81, ..., 5, 25, 125, ..., ..., 1, 6, 10, 12, 14, ...

\$\omega^\omega\$ 1, 2, 4, 8, 16, ..., 3, 6, 12, 24, 48, ..., 9, 18, 36, 72, ..., ..., 5, 10, 20, 40, 80, ..., 15, 30, ..., 45, ..., ..., ..., etc. (reverse lexiographic ordering of the standard form)

Rules

You must pick a well-ordering on \$\mathbb{Z}^+\$. A well ordering is a binary relation \$<\$ such that for all distinct elements \$a\$, \$b\$, \$c\$, \$a<b\space\veebar\space b<a\$ and \$a<b\space\land\space b<c\implies a<c\$ and also for every nonempty subset \$S\$ of \$\mathbb{Z}^+\$, there is a minimal element \$m\$, so that for every other member \$n\$ in \$S\$, \$m<n\$.

Your program will receive two distinct positive integers \$a\$ and \$b\$ in some reasonable format. The program will output TRUE if \$a<b\$ and FALSE otherwise. Instead of "TRUE" and "FALSE", you can choose any two distinct output strings, such as ("true", "false"), ("1", "0") and so on.

Instead of reading from stdin/cmdline and writing to sdtout, you can make a function that takes two integers. The function should still have only two possible (distinct) return values, although they don't have to be strings.

If your programming language has no built-in bignum support, you can assume that a native integer datatype has infinite range (doesn't overflow).

Scoring

Your score is the tuple \$(Value, Bytes)\$ where \$Value\$ is the represented ordinal and \$Bytes\$ is the number of bytes in your program. For example, if you implement the ordinal \$\omega^3+\omega\$ in 6 bytes, your score is \$(\omega^3+\omega, 6)\$.

To compare scores we define a partial order \$\ge\$ so that \$(v_0, b_0)\ge (v_1, b_1)\$ iff \$v_0\ge v_1\$ and \$b_0\le b_1\$. A score \$(v_0, b_0)\$ is better than a score \$(v_1, b_1)\$ iff \$(v_0, b_0)\ge (v_1, b_1)\$ and the scores are not equal.

In other words, your submission is better than another submission, if you achieve more bang-for-buck. That is, you achieve a bigger ordinal with the same number of bytes, or achieve the same ordinal, with a smaller amount of bytes. And obviously if you achieve a bigger ordinal with fewer bytes, your submission is better.

This does mean that some scores can't be compared. For example, \$(\omega\cdot 2, 2)\$ and \$(\omega^2, 4)\$ are incomparable.

You are a winner if there is no submission that is better than yours. If there are two or more submissions with the exact same score, the one submitted first is the winner. Since some scores can't be compared with others, there can be multiple winners. You are free to make multiple submissions, and possibly have multiple winning ones.

List of winning submissions

Bytes	Value	Language and Author
1	\$\omega\$	Polyglot - community wiki
6	\$\omega^\omega\$	Pyth - Anders Kaseorg
12	\$\omega^\omega+1\$	Husk - Dominic van Essen
17	\$\varepsilon_0\$	Pyth - Anders Kaseorg
208	\$\phi_{\Omega^\omega}(0)\cdot\omega\$	Haskell - Grain Ghost
218+2\$n\$	\$\phi_{\Omega^\omega}(0)^n\cdot\omega\$	Haskell - Grain Ghost

Answer 1

Pyth, \$(ω^ω, 6)\$

>_PE_P

Try it online!

Compares the reversed prime factorizations of the two inputs.

Pyth, \$(ε_0, 17)\$

L_SmylP#U_dPb>yEy

Try it online!

L                     def y(b):
           Pb           prime factors of b
   m                    map over d:
         _d               -d
        U                 range [-d, …, -1]
      P#                  filter for (negated) primes
     l                    count
    y                     recursively call y
  S                     sort
 _                      reverse
             >yEyQ    y(second input) > y(first input)

The ordinal corresponding to each positive integer is given by

$$α(p_{i_0}p_{i_1} \dotsc p_{i_{c-1}}) = \sum_k ω^{α(i_k)}$$

where \$p_i\$ is the \$i\$th prime, and the sum on the right is taken in nonincreasing order of \$α(i_k)\$ (since ordinal addition isn’t commutative). This allows us to build any ordinal with a finitely long Cantor normal form. For example:

α(1) = 0,          y(1) = []
α(2) = 1,          y(2) = [[]]
α(4) = 2,          y(4) = [[], []]
α(8) = 3,          y(8) = [[], [], []]
α(16) = 4,         y(16) = [[], [], [], []]
α(3) = ω,          y(3) = [[[]]]
α(6) = ω + 1,      y(6) = [[[]], []]
α(12) = ω + 2,     y(12) = [[[]], [], []]
α(9) = ω·2,        y(9) = [[[]], [[]]]
α(18) = ω·2 + 1,   y(18) = [[[]], [[]], []]
α(27) = ω·3,       y(27) = [[[]], [[]], [[]]]
α(7) = ω^2,        y(7) = [[[], []]]
α(14) = ω^2 + 1,   y(14) = [[[], []], []]
α(21) = ω^2 + ω,   y(21) = [[[], []], [[]]]
α(49) = ω^2·2,     y(49) = [[[], []], [[], []]]
α(19) = ω^3,       y(19) = [[[], [], []]]
α(5) = ω^ω,        y(5) = [[[[]]]]
α(10) = ω^ω + 1,   y(10) = [[[[]]], []]
α(15) = ω^ω + ω,   y(15) = [[[[]]], [[]]]
α(35) = ω^ω + ω^2, y(35) = [[[[]]], [[], []]]
α(25) = ω^ω·2,     y(25) = [[[[]]], [[[]]]]
α(13) = ω^(ω + 1), y(13) = [[[[]], []]]
α(23) = ω^(ω·2),   y(23) = [[[[]], [[]]]]
α(17) = ω^ω^2,     y(17) = [[[[], []]]]
α(11) = ω^ω^ω,     y(11) = [[[[[]]]]]
α(31) = ω^ω^ω^ω,   y(31) = [[[[[[]]]]]]

Pyth, \$(ε_0, 19)\$

L_S.ey-bkx1_jb2>yEy

Explanation for this old answer, which is now obsolete, but may be of interest for porting to languages lacking prime-related builtins.

Answer 2

Haskell, \$(\omega, 3)\$

This solution is dead simple, really can't be beat in Haskell.

(<)

Try it online!

Haskell, \$(\omega+n,19+2\left\lfloor\log_{10}(n+1)\right\rfloor)\$

Here's a scheme to get \$\omega + n\$ for any \$n\in\mathbb{N}\$. Just replace the 9s below with one more than \$n\$. This will make the first \$n\$ numbers bigger than all other numbers but otherwise compare normally.

x#y=(x<9,x)<(y<9,y)

Try it online!

Looks like the leader board should now have an infinite number of winners. However we can beat an infinite number of these pretty easily. Most of this can just be done by fiddling with things a little bit up until we hit 26 bytes. So I will present my scores for 21, 23 and 25 without individual commentary. They should be pretty clear modifications of the 19 byte case.

21 bytes, \$\omega+98\$

x#y=(x<99,x)<(y<99,y)

23 bytes, \$\omega+387420488\$

x#y=(x<9^9,x)<(y<9^9,y)

25 bytes, \$\omega+9^{99}-1\$

(.q).(<).q
q x=(x<9^99,x)

Luckily this wraps up by 26 we can get to a much larger ordinal:

Haskell, \$(\omega\cdot n,26+\left\lfloor\log_{10}(n)\right\rfloor)\$

Thanks to the OP for pointing out that I didn't need division for this.

Another scheme much like the last, replace 9 with the desired number.

(.q).(<).q
q x=(mod x 9,x)

Try it online!

Once again we can use kolmogorov complexity to improve some of these. Here's a few that are currently records for their respective program sizes.

28 bytes, \$\omega\cdot 9^9\$

(.q).(<).q
q x=(x`mod`9^9,x)

29 bytes, \$\omega\cdot 9^{99}\$

(.q).(<).q
q x=(x`mod`9^99,x)

30 bytes, \$\omega\cdot 9^{9^9}\$

(.q).(<).q
q x=(x`mod`9^9^9,x)

31 bytes, \$\omega\cdot 9^{9^{99}}\$

(.q).(<).q
q x=(x`mod`9^9^99,x)

32 bytes, \$\omega\cdot 9^{9^{9^9}}\$

(.q).(<).q
q x=(x`mod`9^9^9^9,x)

33 bytes, \$\omega\cdot 9^{9^{9^{99}}}\$

(.q).(<).q
q x=(x`mod`9^9^9^9,x)

Haskell, \$(\omega^\omega, 63)\$

Implements the order for \$\omega^\omega\$ in the question.

n#1=[]
n#a|mod a n<1=n#div a n++[n]|m<-n+1=m#a
y=(.(2#))
f=y.y(<)

Try it online!

Haskell, \$(\phi_{\Omega^\omega}(0)\cdot\omega,208)\$

This implements the same ordinal as in cardboard_box's answer. It's slightly bigger than the small Veblen ordinal \$\phi_{\Omega^\omega}(0)\$.

This could certain be golfed more. I'm not sure that either the type or the instance are really necessary, but for now it puts Haskell back on the leaderboard.

data T=T[T]deriving Eq
instance Ord T where a<=b=a==b||a<b;T a<T b=any(T a<=)b||(all(<T b)a&&(l a,a)<(l b,b))
l=length
c x|odd x,(y,t)<-c$div x 2=(T t:)<$>c y|1>0=(div x 2,[])
g f x|(y,t)<-c x=f(T t,y)
g.g(<)

Try it online!

Haskell, \$(\phi_{\Omega^\omega}(0)^n\cdot\omega,218+2n)\$

This example code at 222 bytes, iterates the previous algorithm twice. Giving \$\phi_{\Omega^\omega}(0)^2\cdot\omega\$.

data T=T[T]deriving Eq
instance Ord T where a<=b=a==b||a<b;T a<T b=any(T a<=)b||(all(<T b)a&&(l a,a)<(l b,b))
l=length
c x|odd x,(y,t)<-c$div x 2=(T t:)<$>c y|1>0=(div x 2,[])
g f x|(y,t)<-c x=(T t,f y)
r=g$g id
f=(.r).(<).r

Try it online!

Every time we add a g$ to the front of the definition of r we add 1 to the power at the cost of two bytes.

---

Haskell Leaderboard

Since Haskell has been complete removed from the main leaderboard, for now I am maintaining a short list of Haskell winners here

Bytes	Value	Author
3	\$\omega\$	Grain Ghost
19	\$\omega+8\$	Grain Ghost
21	\$\omega+98\$	Grain Ghost
22	\$\omega\cdot 2\$	xnor
24	\$\omega\cdot 4\$	xnor
25	\$\omega\cdot 12\$	xnor
26	\$\omega\cdot 32\$	xnor
27	\$\omega\cdot 99\$	Grain Ghost
28	\$\omega\cdot 9^9\$	Grain Ghost
29	\$\omega\cdot 9^{99}\$	Grain Ghost
30	\$\omega\cdot 9^{9^9}\$	Grain Ghost
31	\$\omega\cdot 9^{9^{99}}\$	Grain Ghost
32	\$\omega\cdot 9^{9^{9^9}}\$	Grain Ghost
33	\$\omega\cdot 9^{9^{9^{99}}}\$	Grain Ghost
34	\$\omega^{10}\$	xnor
53	\$\omega^\omega\$	AnttiP
208	\$\phi_{\Omega^\omega}(0)\cdot\omega\$	Grain Ghost
218+2\$n\$	\$\phi_{\Omega^\omega}(0)^n\cdot\omega\$	Grain Ghost

Answer 3

Python 2, \$\psi_0(\Omega^{\Omega^\omega})\cdot\omega\$ with respect to Buchholz's psi, 266 bytes

l=len
T=lambda i,s='(',d=1:T(i/2,s+['),','('][i%2],d+i*2%4-1)if d else(eval(s)[0],i)
L=lambda A,B:any(A==b or L(A,b)for b in B)or all(L(a,B)for a in A)and(l(A)-l(B),0)<(0,next((L(a,b)for a,b in zip(A,B)if a!=b),0))
def f(a,b):A,a=T(a);B,b=T(b);return(a,0)<(b,L(A,B))

Try it online!

At least I think that's how this ordinal is written. It's a little bigger than the Small Veblen ordinal.

T is a bijective function that maps natural numbers n to tuples (tree,remainder) of ordered trees and natural numbers. It does so by treating the reversed binary representation of the input as a sequence of (s and )s, prepended by an extra (. Once the initial ( is given a matching ), the unused bits form the remainder. For example, 37 is 100101 in binary, which gets reversed to 101001 which becomes ( ()()) 1, giving (()()) as the tree and 1 as the remainder.

L is a well ordering of ordered trees, the ordinal of which is the small Veblen ordinal. It is taken from Jervell, Herman Ruge (2005), "Finite Trees as Ordinals" (which I found via the Wikipedia article linked above). I horizontally mirrored it because it made the code shorter.

f accepts 2 natural numbers, converts them to (tree,remainder) tuples, and compares these by remainder first, then by tree.

Numbers which map to tuples in the form (tree, 0) form the small Veblen ordinal.

Tuples in the form (tree, 1) come next, then (tree, 2), (tree, 3) etc. for a total of \$\omega\$ copies of the small Veblen ordinal, which I think is written \$\phi_{\Omega^\omega}(0)\cdot\omega\$.

Note: while I defined f in terms of non-negative integers, the ordinal doesn't change if you only use strictly positive integers.

Answer 4

Polyglot, \$(\omega, 1)\$

Feel free to add languages to the list.

<

Try it in:

• Actually. Outputs 0/1.
• APL family languages: APL, J, K, BQN. Outputs 1/0.
• Jelly. Outputs 1/0.
• Keg. Outputs 0/1.
• MathGolf. Outputs 0/1.
• MATL. Outputs 1/0.
• Pyt. Outputs False/True.
• Stax. Outputs 1/0.
• Vyxal. Outputs 0/1.

Also one byte in 05AB1E, but ‹ instead of <. Outputs 0/1.

Answer 5

Python 3, \$(\omega^2,28)\$

lambda a,b:(a&-a,a)<(b&-b,b)

Try it online!

Old version

This orders by number of trailing zeros (of binary rep) first and then by the number itself.

Answer 6

Haskell, \$ \omega \cdot 2\$, 22 bytes

(.q).(<).q
q=odd>>=(,)

Try it online!

Based off Grain Ghost's Haskell answers. The function q is pointfree for q x=(odd x,x). That is, we sort numbers by whether they're odd, then the number itself, which gives the evens followed by the odds. We can generalize this idea as:

Haskell, \$ \omega \cdot 4\$, 24 bytes

(.q).(<).q
q=gcd 6>>=(,)

Try it online!

Partitions numbers by the greatest common divisors with 6, which is one of [1,2,3,6]. In general, we can replace 6 with any number \$c\$, and get order type \$ \omega \cdot \sigma(c)\$, where \$ \sigma(c)\$ counts the divisors of \$c\$. For instance:

Haskell, \$ \omega \cdot 12\$, 25 bytes

(.q).(<).q
q=gcd 60>>=(,)

Try it online!

For 3 digits, 840 gives \$ \omega \cdot 32\$ for 26 bytes. The optimal values of \$c\$ to use are Highly Composite Numbers.

---

Haskell, \$\omega^{10}\$, 34 bytes

(.q).(<).q
q=scanl1 min.show>>=(,)

Try it online!

The helper scanl1 min.show takes the decimal representation of a number and computes the running minimum, resulting in a non-increasing sequence. For example, 45271 becomes 44521. We then compare these representations lexicographically, tiebroken by the number itself.

Let's show that the non-decreasing finite lists of digits \$0,\dots,9\$ are in well-ordered, with order type \$\omega^{10}\$. The lexicographic comparison first checks which sequence has more 9's in the prefix, tiebroken by whichever is followed by more 8's, and so on down to which ends with more 0's. So, if we represent the list as \$a_9\$ 9's followed by \$a_8\$ 8's, and so on to \$a_0\$ 0's, the comparison is equivalent to comparing \$a_9, a_8, \dots, a_0\$ lexicographically. Each \$a_i\$ is an arbitrary natural number, so this is exactly the order type \$\omega^{10}\$.

The scanl min operation suffices to obtain almost every non-increasing sequence of digits 0 through 9, as is seen by it leaving the numbers represented by these digits unchanged -- the only exception is sequences made of only 0's, but their omission doesn't affect the order type. Moreover, each such sequence is produced by a finite number of values, a subset of the numbers with that many digits, and it doesn't matter what the tiebreak is among these values as long as there are no ties. So, the order type produced by the main function is also \$\omega^{10}\$.

Sorting the digits in decreasing order would have also worked, but Haskell doesn't have a built-in sort. In other languages, sorting would likely be the way to go.

If we could remove the cap of 9 from the values of the digits, we'd get order type \$\omega^{\omega}\$

Answer 7

Husk, \$\omega\$, 2 bytes

¬<

Try it online!

Boring single-omega solution: well-ordering is just normal integer order (example 1 in question).

---

Husk, \$\omega\$+1, 7 bytes

¬F<σ7\0

Try it online!

Omega+1: well-ordering is integers starting at 1 in normal order, but missing 7, and finally with 7 last, so: 1,2,3,4,5,6,8,9,10,...,7.
Change the 7 in the code to select any other digit at the end.

---

Husk, \$\omega\$.2, 11 bytes

¬F<m?o_\I%2

Try it online!

Odd numbers first, then even numbers, so: 1,3,5,7,...,2,4,6,8,... .

---

Husk, \$ω^ω\$, 6 bytes

¬¤<(↔p

Try it online!

Port of Neil's omega^omega approach: gets the reversed (↔) prime factors of each ¤ argument, and compares them lexicographically (<), finally taking the logical NOT (¬) to ensure only two output values.

---

Husk, \$ω^ω\$+1, 12 bytes

¬¤>?o↔pȯ;\←←

Try it online!

Lexicographic ordering of reversed prime factors of inputs minus 1, but finally with 1 last: subtract 1 (←) from each (¤) input, then if the result is falsey (zero), convert it to a list containing infinity (ȯ;\←), otherwise make a list of its reversed (↔) prime factors, before comparing them (>) and taking the logical NOT (¬).

Answer 8

Charcoal, \$ω^2\$, 10 bytes

‹⟦ΣθＮ⟧⟦ΣηＮ

Try it online! Link is to verbose version of code. Orders by sum of digits, then regular ascending order, resulting in the following ordering:

1, 10, 100, ..., 2, 11, 20, 101, 200, ..., 3, 12, 21, 30, 102, 111, 120, 201, 210, 300, ..., 4, 13, 22, 31, 40, 103, 112, 121, 130, 202, 211, 220, 301, 400 ..., ...

Charcoal, \$ω^2\cdot 9\$, 14 bytes

‹⟦⌈θΣθＮ⟧⟦⌈ηΣηＮ

Try it online! Link is to verbose version of code. Orders by greatest digit, then sum of digits, then regular ascending order, resulting in the following ordering:

1, 10, 100, ..., 11, 101, ..., 111, ..., ... 2, 20, 200, ..., 12, 21, 102, 120, 201, 210, ..., 22, 112, 121, 202, 211, 220, ..., ... 9, 90, 900, ..., 91, 109, 190, 901, 910, ..., 92, 119, 191, 209, 290, 902, 911, 920, ..., ...

Charcoal, \$ω^3\$, 16 bytes

‹⟦ΣΣθΣθＮ⟧⟦ΣΣηΣηＮ

Try it online! Link is to verbose version of code. Orders by sum of digits of sum of digits, then sum of digits, then regular ascending order, resulting in the following ordering:

1, 10, ..., 19, 28, 37, 46, 55, 64, 73, 82, 91, ..., ... 2, 11, 20, ..., 29, 38, 47, 56, 65, 74, 83, 92, ..., ... 3, 12, 21, 30, ..., 39, 48, 57, 66, 75, 84, 93, ..., ... 4, 13, 22, 31, 40, ..., 49, 58, 67, 76, 85, 94, ..., ...

Charcoal, \$ω^ω\cdot 9\$, 29 bytes

Ｆ²⊞υ⟦Ｎ⟧Ｗ›⌈Ｅυ⌊κ⁹Ｆυ⊞κΣ⌊κ›⮌⊟υ⮌⊟υ

Try it online! Link is to verbose version of code. Repeatedly sums the digits of the inputs until they both reach their digital root, then compares the results in reverse order from the digital root working back to the original input. Since there are 9 digital roots and a potentially arbitrary number of summation steps I think I have the correct value for this. For small inputs the ordering is the same as the previous version; it first diverges for 199, which for instance compares less than 99 here but not in the previous ordering.

Answer 9

Retina 0.8.2, \$ω^ω\$, 54 bytes

\d+
$*
+`\b(11+)(\1)+\b
$1 1$#2$*
^(.+)(,\1|\b.*,\1\B)

Try it online! Link includes test cases. Explanation:

\d+
$*

Convert to unary.

+`\b(11+)(\1)+\b
$1 1$#2$*

Factorise with the smallest prime factors last.

^(.+)(,\1|\b.*,\1\B)

Compare lexicographically.

Answer 10

Python 2, \$\omega^{10}\$, 48 bytes

lambda*l:cmp(*[(sorted(`n`)[::-1],n)for n in l])

Try it online!

Outputs -1 for < and +1 for >

Takes each number and sorts its digits in descending order, then compares lexicographically. This effectively compares the count of digit 9's, tiebroken by the number of count 8's, and so on down to 0's. This is all tiebroken by the value of the number itself.

This having order type \$\omega^{10}\$ follows the same argument as my Haskell \$\omega^{10}\$ answer, with sorting replacing taking the running minimum.

Answer 11

Haskell, \$\omega^\omega\$,62 53 bytes

i#0=[i]
i#a=(i+1)#sum[1|'0'<-show a]++[a]
a&b=1#a<1#b

Try it online!

-9 bytes thanks to xnor

Conceptually, this transforms an integer into an infinite list, that is made by iterating sum[1|'0'<-show a], which just counts the zeroes, until zero is reached. Then it's just zeroes after that. Then those lists are then compared in reverse lexicographic order.

To actually do that in practice, the lists are constructed in reverse, and the head of the list is it's own length. The "ideal" infinite lists have an infinite trail of zeroes, which are removed in the "practical" ones. These zeroes are accounted for with the length.

For example, the number 100_000_000_001 has the "ideal" representation [100_000_000_001,10,1,0,0,0,...] and the "practical" representation [4, 1, 10, 100_000_000_001]