What is the lower ordinal bound for the smallest fixed point of derivations with infinitary rules

21 Views Asked by At

Assume $J$ is a set (of judgments). A rule is a pair $(P,c)$ with $P\subseteq J$ and $c\in J$ with the reading that $P$ is a set of preconditions and $c$ is the conclusion. A system of rules is a set $R\subseteq \mathrm{Pow}(J)\times J$. The operator $R_{\mathrm{op}}\colon\mathrm{Pow}(J)\to\mathrm{Pow}(J)$ for $R$ is defined by $$S\mapsto\lbrace c\vert P\subseteq S\land(P,c)\in R\rbrace.$$ Not only is $R_{\mathrm{op}}$ clearly monotone (i.e. $R_{\mathrm{op}}(A)\subseteq R_{\mathrm{op}}(B)$ for $A\subseteq B$), in practice, all $P$ are finite and thus $R_{\mathrm{op}}$ is continuous (i.e. given $S_n\subseteq S_{n+1}$, we have $R_{\mathrm{op}}\bigl(\bigcup_{n\in\mathbb N}S_n\bigr)=\bigcup_{n\in\mathbb N} R_{\mathrm{op}}(S_n)$). Because of that, the smallest fixed point $\mu(R_{\mathrm{op}})$ of $R_{\mathrm{op}}$ is $\bigcup_{n\in\mathbb N}R_{\mathrm{op}}^n(\emptyset)$. I am not interested in the continuous case.

When there is a rule $(P,c)$ with infinite $P=\lbrace p_n\rbrace_{n\in\mathbb N}$ such that $p_n\in R_{\mathrm{op}}^{n+1}(\emptyset)\setminus R_{\mathrm{op}}^n(\emptyset)$, then $c\in R_{\mathrm{op}}\bigl(\bigcup_{n\in\mathbb N}R_{\mathrm{op}}^n(\emptyset)\bigr)\setminus\bigcup_{n\in\mathbb N} R_{\mathrm{op}}^n(\emptyset)$. If we extend the notion $R_{\mathrm{op}}^n$ to ordinals and, for $\lambda$ a limit ordinal, let $$R_{\mathrm{op}}^\lambda(S)=\bigcup_{\alpha<\lambda}R_{\mathrm{op}}^\alpha(S),$$ we can rephrase the above as $c\in R_{\mathrm{op}}^{\omega+1}(\emptyset)\setminus R_{\mathrm{op}}^\omega(\emptyset)$. Now, rather obviously, $$\mu(R_{\mathrm{op}})=\bigcup_{\alpha\in\mathbf{On}}R_{\mathrm{op}}^\alpha(\emptyset)$$ (where $\mathbf{On}$ denotes the class of ordinals). I wonder if we can do better by taking into account the cardinalities of the sets involved. My intuition tells me that $|J|$ is irrelevant and if we take $\kappa=\min\lbrace|R|,\sup_{(P,c)\in R}|P|\rbrace$ then $\kappa=\aleph_\beta$ for some ordinal $\beta$ and $$\mu(R_{\mathrm{op}})=R_{\mathrm{op}}^{\omega_{\beta+1}}(\emptyset)=\bigcup_{\alpha<\omega_{\beta+1}}R_{\mathrm{op}}^\alpha(\emptyset).$$ Am I correct?

1

There are 1 best solutions below

0
On

I can prove it for $\kappa=\aleph_0$, but I am unsure if my argument generalizes to larger cardinalities. Also, my proof seems not to make assumptions on $|R|$ which seems odd to me.

So, let $P$ be countable for every $(P,c)\in R$. We have to show that $R_{\mathrm{op}}^{\omega_1+1}(\emptyset)=R_{\mathrm{op}}^{\omega_1}(\emptyset)$. The direction $\supseteq$ is immediate by monotonicity, so $\subseteq$ remains.

Suppose there is $c\in R_{\mathrm{op}}^{\omega_1+1}(\emptyset)\setminus R_{\mathrm{op}}^{\omega_1}(\emptyset)$. Then, there is a rule $(\lbrace p_j\rbrace_{j\in\mathbb N}, c)\in R$ such that for every $j\in\mathbb N$ we have $p_j\in R_{\mathrm{op}}^{\omega_1}(\emptyset)$, that is, there is $\alpha<\omega_1$ such that $p_j\in R_{\mathrm{op}}^\alpha(\emptyset)$. Because $c\notin R_{\mathrm{op}}^{\omega_1}(\emptyset)$, for all $\alpha<\omega_1$ there are $j\in\mathbb N$ and $\beta_j<\omega_1$ such that $p_j\in R_{\mathrm{op}}^{\beta_j}(\emptyset)\setminus R_{\mathrm{op}}^\alpha(\emptyset)$ (of course, $\beta_j>\alpha$). But this is absurd! Take $\gamma=\sup_{j\in\mathbb N}\beta_j$. As $\mathbb N$ and all $\beta_j$ are countable, so are $\gamma$ and $\gamma+1$, i.e. $\gamma+1<\omega_1$. Thus, $p_j\in R_{\mathrm{op}}^\gamma(\emptyset)$ for all $j\in\mathbb N$, and thus $c\in R_{\mathrm{op}}^{\gamma+1}(\emptyset)\subseteq R_{\mathrm{op}}^{\omega_1}(\emptyset)$.

This means, no such $c$ can exist, that is, $R_{\mathrm{op}}^{\omega_1+1}(\emptyset)\subseteq R_{\mathrm{op}}^{\omega_1}(\emptyset)$.

That we cannot have a lower bound than $\omega_1$ is somewhat evidenced by the definition of $\gamma$. The countable supremum of countable ordinals is countable, but we do not get a better lower bound.