I was trying to go through a proof of the Iteration Theorem from the book Number Systems and Foundations of Analysis from Mendelson when I came across the concept of n-admissible function.
The context is the following:
Iteration Theorem: Consider any Peano system $(P,S,1).$ Let $W$ be an arbitrary set, let $c$ be a fixed element of $W$, and let $g$ be a singulary opration on $W$. Then, there is a unique function $F:P \rightarrow W$ such that:
- $a) F(1) = c$
- $b) F(S(x)) = g(F(x))$ for all $x$ in $P$
The Proof: First, we shall prove the existence of a suitable function $F$. Take any $n$ in $P$. A function $f:A \rightarrow W$ is said to be n-admissible if and only if:
- Conditions on $A$:
- $A \subseteq P$
- $1 \in A$
- $n \in A$
- $(\forall u)(S(u) \in A \Rightarrow u \in A)$
- Conditions on $f$:
- $f(1) = c$
- $(\forall u)(S(u) \in A \Rightarrow f(S(u)) = g(f(u)))$
- $\textrm{I})$ If $f$ is $S(n)$-admissible, then $f$ is $n$-admissible.
Conditions (1),(2),(4)-(6) automatically go over from $S(n)$ to n. It only remain to check (3), that is to prove that $n \in A$. But, by assumption of $S(n)$-admissibility of $f$, $S(n) \in A$. But, then by (4), $n \in A$
- $\textrm{II})$ For any $n$ in $P$, there exist at least one $n$-admissible function.
We shall prove this by mathematical induction. Let $B$ be the set of all members of $n$ of $P$ for which there exist at least one $n$-admissible function. We must show that $B=P$. First $1 \in B$. Simply define the function $f$ with domain $\{1\}$ such that $f(1) = c.$ Clearly $f$ if $1$-admissible. Second assume $n \in B$. Then there is some $n$-admissible function $f$. Let $A$ be the domain of $f$. We define another function $f^*$ as follows: For any $x$ in $A$, let $f^*(x) = f(x)$, and, if $S(n) \notin A$, let $f^*(S(n)) = g(f(n))$. Note that, if $S(n) \in A$, then by (4), $f(S(n)) = g(f(n))$. Hence, in this case also, $f^*(S(n)) = g(f(n))$. The domain $A^*$ of $f^*$ is $A \cup \{S(n)\}$, which is equal to $A$ in the case where $S(n) \in A$. The verification that $f^*$ is $S(n)$-admissible is straightforward and is left as an exercise for the reader. Thus, $S(n) \in B$. We have shown that $n \in B \Rightarrow S(n) \in B$. By mathematical induction, $B=P$.
- $\textrm{III})$ If $f$ is $n$-admissible and $h$ is $n$-admissible, then $f(n) = h(n)$.
We shall prove this by mathematical induction. Let $Y = \{n : n \in P \land (\forall f)(\forall h)(f$ is $n$-admissible $\land \space h $ is $n$-admissible $\Rightarrow f(n) = h(n))$. We must show that $Y=P$. First $1 \in Y$ since $f(1) = c = h(1)$. Second, assume $n \in Y$, and let $f$ and $h$ be $S(n)$-admissible. By($\textrm{I}$), $f$ and $h$ are $n$-admissible. Hence, since $n \in Y$, it follows that $f(n) = h(n)$. Then, by (4), $f(S(n)) = g(f(n)) = g(h(n)) = h(S(n))$. Thus, $S(n) \in Y$. We have shown that $n \in Y \Rightarrow S(n) \in Y$. Hence, by mathematical induction, P=Y.
- $\textrm{IV})$ For any $n$ in $P$, by virtue of ($\textrm{II}$), we may take some $n$-admissible function $f$.
Let us define $F(n) = f(n)$. By ($\textrm{III}$), the value of $F(n)$ doest not depend upon the particular choice of the $n$-admissible function $f$.
It is obvious that the domain of $F$ is $P$. Also $F(1)$ = $f(1)$ for some $1$-admissible function $f$. But $f(1)=c$. Hence, we have condition (a):$F(1)=c$.
In addition, $F(S(n)) = f(S(n))$ for some $S(n)$-admissible function $f$. Since $f$ is also $n$-admissible, by virtue of ($\textrm{I}$), $F(n)=f(n)$. But, since $f$ is $S(n)$-admissible, $f(s(n)) = g(f(n))$. This yields (b): $F(S(n)) = g(F(n)).$
Thus conditions (a), (b) on the function $F$ are satisfied. We must still show that the range of $F$ is included in $W$. For any $n$ in $P$, $F(n) = f(n)$ for some $n$-admissible function $f$. Since $Range(f) \subseteq W$, it follows that $F(n) \in W$.
Uniqueness. Assume $F_1$ and $F_2$ are functions from $P$ into $W$ satisfying condition (a), (b). Let $K = \{n : n \in P \land F_1(n)=F_2(n)\}$. Now, $1 \in K$, since $F_1(1) = c = F_2(1)$. Moreover, if $n \in K$, then $F_1(n) = F_2(n)$. Hence, $F_1(S(n)) = g(F_1(n)) = g(F_2(n)) = F_2(S(n))$, that is, $S(n) \in K$. We have shown that $n \in K \Rightarrow S(n) \in K$. Hence, by mathematical induction, $P=K$. Thus, $F_1(n) = F_2(n)$ for all $n$ in $P$. Since $P$ is the domain of both $F_1$ and $F_2$, it follows that $F_1 = F_2$. $\blacksquare$
Let me know if Im reading this concept in the right way, from what I have understood the author take some $n$ of $P$ and specify a restriction of the function $F$ to the function $f$ which satisfy the six listed conditions. So when satysfing those conditions the function is called $n$-admissible.
Thus if the function is $n$-admissible, then the function holds property (a) and partially holds property (b), but by the fact that exist a $n$-admissible function for every $n$ in $P$ and $F$ is defined as $F(n)=f(n)$ then $F$ hold property (b) for all $n$ in $P$.
I tried to found other usage of the concept of $n$-admissible, but it dont seem to be very common, there are a few examples following.
edit 1 It dont seems to be very common, I was trying to found other usage by searching for the same term, I found out this document C Ring Project which mentions admissible function at page 50, but it takes the definition from Mendelson who is the author of the book Im following.
Some books seems to use "n-admissible" definition too, as examples we have