0
$\begingroup$

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$:
  1. $A \subseteq P$
  2. $1 \in A$
  3. $n \in A$
  4. $(\forall u)(S(u) \in A \Rightarrow u \in A)$
  • Conditions on $f$:
  1. $f(1) = c$
  2. $(\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

The Number Systems Of Analysis and Theory of Radicals

$\endgroup$
5
  • 1
    $\begingroup$ The way you wrote it, you're close, but slightly misunderstanding. During the proof, we do not yet have an $F$ that we could restrict, so you'd have to throw in a couple of "hypothetical" there. If we had the additional condition $S(n) \notin A$, then an $n$-admissible function would be a function that could be a restriction of such an $F$ to the initial segment $I_n := \{1, \dotsc, n\}$ of $P$. Since $A$ might be a larger segment, a function is $n$-admissible if its restriction to $I_n$ could be the restriction of such an $F$. The conditions make the "could be" precise. $\endgroup$ Jul 28 '20 at 13:56
  • $\begingroup$ Im a bit confused, because if we let some $f$ be a restriction of such an $F$ to the initial segment $I_n = \{1,...,n\}$ of $P$, where $S(n) \notin I$, but we have $1 \in I$, $I \subseteq P$, $n \in I$ and we can define $f$ to met the conditions to be $n$-admissible, but I cant see what will be the image from $f(n)$. $\endgroup$ Jul 28 '20 at 14:36
  • $\begingroup$ I'm not sure what you're confused about. What do you mean by "the image from $f(n)$"? $\endgroup$ Jul 28 '20 at 14:40
  • $\begingroup$ I just did a big mistake, I was thinking about sucessor of $n$ instead of how $f(n)$ will be defined in case $S(n) \notin I$, but as long $n \neq 1$, we have that $(\exists !q)(n = S(q))$, thus $f(n) = f(S(q)) = g(f(q)$, and we have that $q \in I$, because the way $I$ was defined and because condition (4) too. Sorry for this, Im new to abstract mathematics. From your comment I wonder why the author dont restricted $S(n) \notin A$, can you see a good reason? $\endgroup$ Jul 28 '20 at 14:46
  • $\begingroup$ Can you submit you first comment as an answer? This explanation give a precise definition of what n-admissible is in the given context. $\endgroup$ Jul 30 '20 at 2:21
1
$\begingroup$

What you wrote is not quite correct. During the proof we do not yet have an $F$ that we could restrict, thus one cannot "specify a restriction of the function $F$". But if one inserts the word "hypothetical" into that, then one gets a correct (albeit not yet precise) description of the concept. The underlying idea is that if a function $F$ with the desired properties exists, then the restrictions of $F$ to initial segments of $P$ must satisfy certain conditions. The concept of $n$-admissibility makes that precise.

Conditions 1-4 say that the domain $A$ of an $n$-admissible function $f$ is an initial segment of $P$ containing $n$. Condition 5 is property a), and condition 6 says property b) holds as far as that makes sense, that is, on the whole domain of $f$.

Altogether, these are the conditions a restriction of $F$, if such an $F$ exists, to an initial segment of $P$ containing $n$ must necessarily satisfy.

Then the proof goes on to show that there is a unique $F \colon P \to W$ with properties a) and b), and thus $n$-admissibility is also sufficient to characterise the restrictions of $F$ to initial segments of $P$.

That proof is a (maybe the, discounting trivial variations) standard proof of the iteration theorem. That the concept of $n$-admissibility doesn't seem very common is because many authors do not give it a name. One can use the idea without naming it. Having a name for it adds convenience at some points of the proof, but at the (not very high) cost of introducing a new name.

$\endgroup$
1
  • $\begingroup$ Thanks for clarifying this concept, I bet this will help other newcomers in abstract mathematics. $\endgroup$ Jul 30 '20 at 19:09

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.