CGV googology part 1: veblen function

Hello, this post will be introducing a small (and presumably the most successful) portion of the fascinating subject of combinatorial game value or surreal googology. This is the Veblen function \(\phi:\mathrm{On}\times\mathrm{No}\mapsto\mathrm{No}\), defined in two different ways by me and PlanetN9ne, and later shown to be equivalent (by me!).

Note, there is a veblen function \(\phi:\mathrm{No}\times\mathrm{No}\mapsto\mathrm{No}\) but it’s cursed. Most of this is due to the fact that \(\phi(\frac{1}{2})\) enumerates some fixed points of \(x\mapsto\omega^x\) which are already values of \(\phi(1)\).

My definition

\(\phi(x,y)=\{0,r\phi(x,y^L),\phi(x^\prime,\phi(x,y)^L)|r\phi(x,y^R),\phi(x^\prime,\phi(x,y)^R)\}\), where \(x^\prime\) ranges over ordinals less than \(x\), \(r\) ranges over all positive real numbers, and \(y^L\) and \(y^R\) range over left and right sets of \(y\).

Planet’s definition

First, we need to discuss sign expansions. Look it up.

Secondly, we need to discuss a method that interpolates all “hypernormal” ordinal functions. A function f is hypernormal if it is normal and \(\alpha<\beta\) implies \(f(\alpha)+f(\beta)=f(\beta)\).

For any surreal \(x\), let \(s_1,s_2,\ldots\) be the sign expansion of \(x\). Then we can define the interpolated function \(f\) by \(f(x)=+^{f(0)}s_1^{f(1)}s_2^{f(2)}\ldots\). This agrees with \(f\) on all ordinal values. Proof by induction: obviously true for 0, and \(f(\alpha+1)\)’s sign-expansion is just that of \(f(\alpha\)\) with \(f(\alpha+1)\) pluses added. So it is the ordinal sum \(f(\alpha)+f(\alpha+1)\) which is \(f(\alpha+1)\) by hypernormality. The limit case follows from normality.

Planet’s veblen is obtained by interpolating the second argument of veblen in this manner. We use \(\varphi\) to denote it.

Proof of equivalence

The following properties hold of Planet’s veblen function:

  1. \(\varphi(\alpha,x)\) is increasing, because \(\varphi(\alpha)\) repeats every sign some number of times and adds some signs to the front, which clearly preserves comparison.
  2. \(\varphi(\alpha^\prime,\varphi(\alpha,x))=\varphi(\alpha,x)\), given \(\alpha^\prime<\alpha\).. Proof: let the sign expansion of \(x\) be \(stu\ldots\). Then that of \(\varphi(\alpha,x)\) is \(+^{\phi(\alpha,0)} s^{\phi(\alpha,1)}\ldots\), and that of \(\varphi(\alpha^\prime,\varphi(\alpha,x))\) is \(+^{\phi(\alpha^\prime,0)}\)\(+^{\phi(\alpha^\prime,1)+…+\text{up to but not including }\phi(\alpha^\prime,\phi(\alpha,1))} \)\(s^{\phi(\alpha^\prime,\phi(\alpha,1))+…+\text{up to but not including }\phi(\alpha^\prime,\phi(\alpha,2))}\ldots\)\(=+^{\phi(\alpha,0)} s^{\phi(\alpha,1)}\ldots\).
  3. \(\varphi(\alpha,x)\) is simpler than \(\varphi(\alpha,y)\) if \(x\) is simpler than \(y\), because it applies \(\phi(\alpha)\) to the birthday.
  4. Every common fixed point of \(\varphi(\alpha^\prime)\) for \(\alpha^\prime<\alpha\) is of the form \(\varphi(\alpha,x)\). Proof: let the fixed point be \(y=+^b -^c +^d -^e\ldots\). (It has to start with a plus because every value is positive.) Then it’s easy to see (similarly to (2)) that \(b,c,d,\ldots\) are all fixed points of \(\phi(\alpha^\prime)\), thus they are values of \(\phi(\alpha)\) making \(y\) a values of \(\varphi(\alpha)\).
  5. \(\varphi(\alpha,x)\) is the simplest common fixed point of \(\varphi(\alpha^\prime,y)\) between \(\varphi(\alpha,x^L)\) and \(\varphi(\alpha,x^R)\), which trivially follows from the previous.
  6. \(\varphi(0,x)=\omega^x\). Proof to be given at a later date.

But \(\phi\) is, by construction, the unique function satisfying (5) and (6). Thus, \(\phi=\varphi\).

3 thoughts on “CGV googology part 1: veblen function”

  1. btw, the definition of the cursed $\textrm{No}\times\textrm{No}\mapsto \textrm{No}$ one was $\phi(0,x)=\{0,r\phi(0,x^{L})|r\phi(0,x^{R})\}$ where $r$ ranges over $\mathbb{R}$ if $x>0$; $\phi(x,y)=\{0,\phi(x,y^{L})+1,\phi(x^{L},y),\phi(x^{L},\phi(x,y)^{L})|\phi(x,y^{R})-1,\phi(x^{R},y)-1,\phi(x^{L},\phi(x,y)^{R})\}$ otherwise

    1. oops! it’s been pointed out that there’s a mistake here. r must be a *positive* real number. I *think* that domain restriction was somewhere along the way a typo of (r>0) or something, so probably the first line should be something like: $\phi(0,x) = \{0,r\phi(0,x^{L})|r\phi(0,x^{R})\}$ where $r$ ranges over $\mathbb{R}$ and $r>0$. If someone knows better please tell me.

Leave a Comment

Your email address will not be published. Required fields are marked *