## FANDOM

10,023 Pages

The bop-counting function is a function defined by Harvey Friedman, arising in study of binary operations on structures.[1]

## DefinitionEdit

Let $$D$$ be a set. A ternary relation on $$D$$ is a set $$R\subseteq D^3$$. We call two ternary relations $$R \subseteq D^3,\, R' \subseteq D'^3$$ equivalent or isomorphic iff there is a bijection $$f:D\rightarrow D'$$ such that $$(a,b,c)\in R\Leftrightarrow (f(a),f(b),f(c))\in R'$$.

A ternary relation $$R$$ is a binary operator or bop iff every $$(a,b)\in D^2$$ uniquely determines $$c\in D$$ such that $$(a,b,c)\in R$$ (so that $$R$$ is a function $$D^2\rightarrow D$$). For $$k\in\Bbb N$$ a $$k$$-restriction of $$R$$ is a domain restriction of $$R$$ to a set $$E^2$$ such that $$|E|=k$$. Two bops $$R_1,R_2$$ are $$k$$-similar if for every $$k$$-restriction of $$R_1$$ we can find $$k$$-restriction of $$R_2$$ which is isomorphic to it, and vice versa. $$k$$-similarity is an equivalence relation, and this is easy to show.

Finally, define the bop-counting function $$\theta(k)$$ for $$k\in\Bbb N$$ to be the number of equivalence classes under $$k$$-similarity.

## PropertiesEdit

By counting the number of possible (up to isomorphism) $$k$$-restrictions of a set, it can be show that $$\theta(k)$$ is a function which is at most triply exponential in $$k$$ (i.e. it is bounded by $$2^{2^{2^{ck}}}$$ for some constant $$c$$). Nevertheless, Friedman has shown that this function is not recursive. This presents algorithmic difficulty in finding values of this function.

A more striking result regards the specific value $$\theta(12)$$. Friedman has shown that the statement "$$\theta(12)=N$$", for any natural number $$N$$, cannot be proven in any of well-known strong formal theories, including ZFC + I1, and NBG + "there exists a nontrivial elementary $$j:V\rightarrow V$$" (assuming they are consistent).

We can however try to measure how "close" a theory is to providing exact value of the number, by asking for upper bounds which the theory can provide. To be precise, for theory $$T$$, let $$\theta(12,T)$$ be the least $$N$$ such that $$T \vdash \theta(12) \leq N$$. If $$T,T'$$ are "standard" large cardinal extensions of ZFC (with term "standard" being intentionally left vague; Friedman defers clarification until a later paper), and both are consistent, then if $$T'$$ proves the consistency of $$T$$ then $$\theta(12,T') < \theta(12,T)$$. This, in a way, shows how bad these theories are at estimating $$\theta(12)$$, as even a barely stronger system asserting consistency already shows tighter bound.

## ReferencesEdit

1. Impossible counting by Harvey M. Friedman