2
$\begingroup$

Let $\mathcal{E}_{\lambda}$ be the set of all elementary embeddings from $V_{\lambda}$ to $V_{\lambda}$. If $j\in\mathcal{E}_{\lambda}$ is a non-trivial elementary embedding, then define $\mathrm{crit}(j)$ to be the least ordinal $\alpha$ where $j(\alpha)>\alpha$. Recall that $\mathcal{E}_{\lambda}$ may be endowed with a self-distributive operation $*$ where $j*k=\bigcup_{\alpha<\lambda}j(k|_{V_{\alpha}})$. We shall therefore regard $\mathcal{E}_{\lambda}$ as an algebraic structure with the operation $*$. Now, for each limit ordinal $\gamma<\lambda$, let $\equiv^{\gamma}$ be the congruence on $\mathcal{E}_{\lambda}$ where we set $j\equiv^{\gamma}k$ if and only if $j(x)\cap V_{\gamma}=k(x)\cap V_{\gamma}$ for each $x\in V_{\gamma}$.

$\mathbf{Theorem:}$ If $X$ is a finitely generated subalgebra of $\mathcal{E}_{\lambda}$ and $\gamma<\lambda$ is a limit ordinal, then $\mathcal{E}_{\lambda}/\equiv^{\gamma}$ is finite.

$\mathbf{Theorem:}$ If $X$ is a finitely generated subalgebra of $\mathcal{E}_{\lambda}$, then $\{\mathrm{crit}(j)|j\in X\}$ has order type $\omega$.

Suppose that $X\subseteq\mathcal{E}_{\lambda}$ is finitely generated. Let $\mathrm{crit}_{n}(X)$ denote the $n$-th element $\{\mathrm{crit}(j)|j\in X\}$. Then how slowly can the function $n\mapsto|X/\equiv^{\mathrm{crit}_{n}(X)}|$ grow? Can the function $n\mapsto|X/\equiv^{\mathrm{crit}_{n+1}(X)}|-|X/\equiv^{\mathrm{crit}_{n}(X)}|$ grow at a rate of $O(\log(n))$? The following result gives a lower bound of this growth rate of $X$.

$\mathbf{Theorem:}$ Suppose that $X$ is a finitely generated subalgebra of $\mathcal{E}_{\lambda}$. Then there is a $\delta>0$ such that for all $n>0$, we have $$|X/\equiv^{\mathrm{crit}_{n}(X)}|>\delta\cdot n\cdot\log(n).$$ (I have been able to obtain conjecturally sharp lower bounds for $|X/\equiv^{\mathrm{crit}_{n}(X)}|$ but it will probably be very difficult to actually prove these more precise lower bounds are sharp without extraordinary theoretical developments).

  1. Does there exist a cardinal $\lambda$ and a finitely generated subalgebra $X\subseteq\mathcal{E}_{\lambda}$ along with a $\delta>0$ where for all $n>0$, we have $|X/\equiv^{\mathrm{crit}_{n}(X)}|<\delta\cdot n\cdot\log(n)$?

  2. Does there exist a $\lambda$ and a finitely generated subalgebra $X\subseteq\mathcal{E}_{\lambda}$ along with a $\delta>0$ where for all $n>0$, we have $|X/\equiv^{\mathrm{crit}_{n+1}(X)}|-|X/\equiv^{\mathrm{crit}_{n}(X)}|<\delta\cdot\log(n)$?

  3. Suppose that $r>1$. Does there exist a $\delta>0$ along with a cardinal $\lambda$ and $X\subseteq\mathcal{E}_{\lambda}$ is generated by $r$ elementary embeddings where if $n>1$ then $|X/\equiv^{\mathrm{crit}_{n}(X)}|<\delta\cdot n\cdot\log(n)$?

  4. Suppose that $r>1$. Does there exist a $\delta>0$ along with a cardinal $\lambda$ and $X\subseteq\mathcal{E}_{\lambda}$ generated by $r$ elementary embeddings where if $n>1$ then $|X/\equiv^{\mathrm{crit}_{n+1}(X)}|-|X/\equiv^{\mathrm{crit}_{n}(X)}|<\delta\cdot\log(n)$?

  5. If questions 1-4 are too difficult, can one prove assuming large cardinals that there is some $\lambda$ and finitely generated $X\subseteq\mathcal{E}_{\lambda}$ where if $f(n)=|X/\equiv^{\mathrm{crit}_{n}(X)}|$, then $f(n)=O(a^{n})$ for all $a>1$ or where $f(n)=O(n^{d})$ for some integer $d$?

I would be especially interested if the function mapping $n$ to the multiplication table of $\mathrm{crit}_{n}(X)$ is computable in polynomial time.

This question could more or less have been formulated algebraically without any reference to large cardinals. I will therefore gladly accept answers to the algebraic formulations of these questions.

Note: For all $n$, there exists algebras of elementary embeddings $X\subseteq\mathcal{E}_{\lambda}$ such that $|X/\equiv^{\gamma}|=n$ and where $|\{\mathrm{crit}(j)|j\in X\}\cap(\gamma+1)|=n$. The condition that $X$ is finitely generated is therefore necessary.

Note: My computer experiments suggest that it should be possible for $|\langle j_{1},\dots,j_{r}\rangle/\equiv^{\mathrm{crit}_{n}(j_{1},\dots,j_{r})}|$ to grow at a rate of $O(n\cdot\log(n))$.

Note: In case you are wondering, there is also an upper bound of the cardinality $|\langle j_{1},\dots,j_{r}\rangle/\equiv^{\mathrm{crit}_{n}(j_{1},\dots,j_{r})}|.$ We have $|\langle j_{1},\dots,j_{r}\rangle/\equiv^{\mathrm{crit}_{n}(j_{1},\dots,j_{r})}|\leq\frac{r^{2^{n}}-1}{r-1}$. This bound is sharp when we reformulate the question in an algebraic context and it is probably sharp in a set theoretic context as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.