4
$\begingroup$

Let $\mathrm{R}_0,\cdots,\mathrm{R}_8$ be the following functions:

$\mathrm{R}_0(x,y)=\{x,y\}$

$\mathrm{R}_1(x,y)=x-y$

$\mathrm{R}_2(x)=\bigcup x$

$\mathrm{R}_3(x,y)=x\times y$

$\mathrm{R}_4(x)=\mathrm{Dom}(x)$

$\mathrm{R}_5(x)=\{(a,b)\ |\ a\in b\ \wedge\ a\in x\ \wedge\ b\in x\}$

$\mathrm{R}_6(x)=\{(a,b,c)\ |\ (b,a,c)\in x\}$

$\mathrm{R}_7(x)=\{(a,b,c)\ |\ (b,c,a)\in x\}$

$\mathrm{R}_8(x,y)=\{x[\{a\}]\ |\ a\in y\}\ \ $ where $x[\{a\}]=\{b\ |\ (a,b)\in x\}$ .

Gandy-Jensen system $\mathsf{GJ}_0$ is the system of which the set-theoretic axioms are the Axiom of Extensionality and the following nine set-existence axioms:

$\mathrm{R}_0(x,y)\in\mathrm{V},\ \cdots,\ \mathrm{R}_8(x,y)\in\mathrm{V}$ .

The class of rudimentary functions is the closure of $\mathrm{R}_0,\cdots,\mathrm{R}_8$ under composition.

It is obvious that if $F$ is a $n$-ary rudimentary function then $\mathsf{GJ}_0\vdash F(x_1,\cdots,x_n)\in\mathrm{V}$ .

My question is that whether the converse of the above proposition is true, i.e. is it true that:

For every class term $A(x_1,\cdots,x_n)$ whose free variables are in $x_1,\cdots,x_n$ , if $\mathsf{GJ}_0\vdash A(x_1,\cdots,x_n)\in\mathrm{V}$ , then $(x_1,\cdots,x_n)\mapsto A(x_1,\cdots,x_n)$ is a $n$-ary rudimentary function.


Edit 1 : I think I should make my terminologies more precise:

Let $\mathsf{T}$ be an axiom system of set theory (such as $\mathsf{GJ}_0,\ \mathsf{ZFC},$ and so on). We say that a function F is a n-ary $\mathsf{T}$-rudimentary function if there is a n-ary rudimentary function G such that $\mathsf{T}\vdash F=G$ .

I actually asked that whether the following statement is true:

For every class term $A(x_1,\cdots,x_n)$ whose free variables are in $x_1,\cdots,x_n$ , if $\mathsf{GJ}_0\vdash A(x_1,\cdots,x_n)\in\mathrm{V}$ , then $(x_1,\cdots,x_n)\mapsto A(x_1,\cdots,x_n)$ is a $n$-ary $\mathsf{ZFC}$-rudimentary function.

Where $\mathsf{ZFC}$ can be replaced by other systems such as $\mathsf{GJ}_0$ and then we have more similar questions.


Edit 2 : The question become trivial if I restrict "rudimentary" to "$\mathsf{T}$-rudimentary" defined in Edit 1 . So I will remove this restriction, and still ask that whether the original proposition (which is weaker than the false proposition in Edit 1 ) is true.

$\endgroup$
  • $\begingroup$ I think it's high time we have a [fine-structure] tag. But I'd be happy if one of the guys that know more about it will write the tag wiki/excerpt. I feel insufficiently knowledgeable about the topic. $\endgroup$ – Asaf Karagila Oct 20 '14 at 7:08
  • $\begingroup$ Isn't sufficient to show that these functions produce Godel operators? $\endgroup$ – Mohammad Golshani Oct 20 '14 at 7:27
  • $\begingroup$ If $A$ is $x\cap B$ and $B$ is $\Delta_0$ , then it is sufficient to show that these functions produce Godel operators. $\endgroup$ – Sencodian Oct 20 '14 at 13:31
5
$\begingroup$

Rudimentary functions can only increase rank by a fixed finite amount. So $$A(x,y) = \begin{cases} x + y & \text{when $x,y \in \omega$,} \\ 0 & \text{otherwise,} \end{cases}$$ is not rudimentary even if $\mathsf{GJ}_0 \vdash A(x,y) \in V$.


This is true even for nonstandard models of $\mathsf{GJ}_0$ but one has to be careful about the definition of $A(x,y)$. For simplicity, I will use $F(x) = 1+A(x,x) = 1+2x$. Then $F(x) = y$ iff $x \in \omega$ ($\omega$ being understood as a definable class, not necessarily a set) and there is exactly one sequence $s$ with domain $x+1$ such that if $s(0) = 1$ and $s(z+1) = s(z)+2$ whenever $z \lt x$ then $s(x) = y$; otherwise, $F(x) = 0$.

In ill-founded models, $\{x \in \omega : F(x) \neq 0\}$ could be a proper cut in $\omega$ but that doesn't change the fact that this provably total function $F$ is not rudimentary.

$\endgroup$
  • $\begingroup$ Why $\mathsf{GJ}_0\vdash A(x,y)\in\mathrm{V}$ ? There is no axiom of induction or foundation in $\mathsf{GJ}_0$ . $\endgroup$ – Sencodian Oct 24 '14 at 11:42
  • $\begingroup$ I think Sencodian is right to ask this: $\mathsf{GJ_0}$ does not prove the graph of addition exists as a set; it cannot even prove that the class of even (von Neumann) natural numbers is a set. $\endgroup$ – Philip Welch Oct 24 '14 at 19:42
  • $\begingroup$ Yes, this is what I tried to clarify in the addendum. I'm using $\omega$ as a definable class. (Assuming the existence of $\omega$, the constant function with value $\omega$ is an easier example.) The key point is that any model of $\mathsf{GJ}_0$ contains a copy of HF and therefore can represent all primitive recursive functions in the sense that there is a definable total function whose values at standard finite ordinals agree with the real-world primitive recursive function. Almost none of these are rudimentary because they grow too fast. $\endgroup$ – François G. Dorais Oct 24 '14 at 20:20
2
$\begingroup$

I'm not well versed in fine structure, so this may well be wrong:

I think it depends what you mean by a "class term." Since the language of set theory contains no function symbols, there are no terms as usually defined; so you would need to fix a set of function symbols to be used as the language out of which terms can be built. Note that, in this case, your function symbols must be complicated for the answer to be nontrivial, since if your function symbols are expressible in terms of rudimentary functions (e.g., "$x\mapsto \{x\}$" is just $R_0(x, x)$), then the answer to your question is trivially yes.

If on the other hand by "class term" you mean a definable function - that is, a formula $p(\overline{x}, y)$ such that $GJ_0$ (or similar) proves that for every $\overline{x}$ there is exactly one $y$ such that $p(\overline{x}, y)$ - then I think the answer is no, since we can define functions by cases (e.g., "$x\mapsto \{x\}$ if $x=\emptyset$ and $x\mapsto \emptyset$ otherwise"). It seems that in general such "definably piecewise rudimentary" functions need not be rudimentary, but of course $GJ_0$ will prove that each one is total.


Edit: the new phrasing of the question - roughly "if $GJ_0$ proves that F is total, then $ZFC$ proves that $F=G$ for some rudimentary $G$" - yields a very simple negative answer, for the reasons you say. In fact, we can replace $ZFC$ with any reasonable theory $T$: pick some sentence $p$ undecidable in $T$, and let $F: x\mapsto\emptyset$ if $p$ and $\{x\}$ if $\neg p$. It's easy to see that $GJ_0$ proves that $F$ is total, but that $F$ is not $T$-rudimentary.

The question is much more interesting without this restriction, I feel.

(Also, you should still define what you mean by "class term.")

$\endgroup$
  • $\begingroup$ I think the same with you. But how to prove that "definably piecewise rudimentary functions need not be rudimentary" ? Consider an example such as $x\mapsto x\cap\{x\ |\ \mathrm{CH}\}$ , where $\mathrm{CH}$ means the Continuum Hypothesis. How can we prove this function is not rudimentary(assume our meta-system is ZFC)? $\endgroup$ – Sencodian Oct 20 '14 at 0:50
  • $\begingroup$ Well, that function actually is rudimentary, provably in ZFC: either CH holds, or it doesn't, and in either case it's a rudimentary function. Which rudimentary function it happens to be is independent, of course, but it is provably rudimentary. The potential counterexamples are definitions by cases where the cases are in terms of $x$. $\endgroup$ – Noah Schweber Oct 20 '14 at 7:14
  • $\begingroup$ See my new remark above. In this sense, how can we prove $x\mapsto x\cap\{x\ |\ \mathrm{CH}\}$ is $\mathsf{ZFC}$-rudimentary ? Let this function be $F(x)$ , neither $\mathsf{ZFC}\vdash F(x)=x$ nor $\mathsf{ZFC}\vdash F(x)=\varnothing$ is true, since $\mathrm{CH}$ can't be decided in $\mathsf{ZFC}$ . $\endgroup$ – Sencodian Oct 20 '14 at 13:27
  • $\begingroup$ Noah, as a side remark, you should join us at the sans serif side and start denoting theories with \mathsf. It looks nicer on this side of the board. :-P $\endgroup$ – Asaf Karagila Oct 20 '14 at 22:02
  • $\begingroup$ Yes, You are right. My question is trivial with this restriction. In fact, for every non-$\Delta_0^{\mathsf{T}}$ sentence $\phi$ , the function $x\mapsto \{x\}\cap\{x\ |\ \phi\}$ is not $\mathsf{T}$-rudimentary, where $\mathsf{GJ}_0\subseteq\mathsf{T}$ . $\endgroup$ – Sencodian Oct 21 '14 at 1:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.