2
$\begingroup$

If we generally would define the smallest set, that has to have some properties, as the set obtained by intersecting all the sets that have those properties (if the intersection is non-empty) and the tiniest set, that has to have some properties, as the set with the least cardinality, that has to have those properties (if there is only one set with the least cardinality), would then the set $F$ of primitive recursive function be also the tiniest set (besides being the smallest one) $F \subseteq \cup_{k\in \mathbb{N}} \left\{f:\mathbb{N}^k \rightarrow \mathbb{N} \right\}$, that contains the base functions and is closed under composition and primitive recursion ? (Or if I may rephrase the question: Is $F$ the only countable set, that contains the base functions and is closed under composition and primitive recursion ?)

Side question: I know $F$ is countable set, since to every function $f \in F$ there corresponds a very basic program containing only bounded loops and such; and a program is just a finite (but arbitrary long) string over a finite (and fixed) alphabet; thus $F$ can be seen as a reunion of all finite strings (that make synthactically sense; i.e. are programs) over a finite fixed alphabet - and therefore has to be countable. But how can I prove that $F$ is countable without falling back to interpret a function $f\in F$ as a program (just by staying "inside mathematics") ?

  • 0
    Of course choosing the way over the set of all programs is also inside mathematics, but for me it is still a difficult jump to see programs as a well-defined part of mathematics, so that's why I said "inside mathematics". Maybe I should have rather said something like "inside set theory"...2011-04-28

2 Answers 2

5

You can prove $F$ is countable without appealing to its characterization as the set of all programs by the following argument. $F$ is constructed as follows: Let $F_0$ be the collection of base functions which is easily seen to be countable. Let $F_{n+1}$ be $F_n$ together with every composition of finitely many elements of $F_n$ and all applications of primitive recursion to elements of $F_n$. It's easy to prove by induction that each $F_n$ is countable, and hence the union of the $F_n$ is countable. It's clear that this union satisfies the desired closure properties, hence this union is in fact $F$.

This can be generalized: Closing an infinite set $X$ under $\leq |X|$ many finitary operations results in a set of the same size $|X|$. This can be generalized further still, but I'll leave at this for now.

4

The closure under composition and primitive recursion of the set of base functions and the Ackermann function is countable.

  • 1
    It is misleading (at least for me :), I think the alternative that I wrote above expresses the same thing without possibility of confusion. ps: btw, you are still taking union at some steps (for limit ordinals, like $\omega+\omega$).2011-05-10