# Concerning the countability of the set of primitive recursive functions

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") ?

-

I cannot understand in what way that is going outside of mathematics! – Mariano Suárez-Alvarez♦ Apr 27 '11 at 6:43
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"... – temo Apr 28 '11 at 4:17

## 2 Answers

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.

-

## Did you find this question interesting? Try our newsletter

email address

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

-
You can iterate this, of course. Pick one function which is not in the set I described, add it and take the closure under composition and primitive recursion. You can repeat this transfinitely many times, once per countable ordinal (I guess...) – Mariano Suárez-Alvarez♦ Apr 27 '11 at 6:56

1
Each one is countable, but the union is not, i.e. there are uncountably many countable ordinals! – Kaveh May 10 '11 at 3:06

1
I interpreted "You can repeat this transfinitely many times, once per countable ordinal" as meaning we continue doing it once per each countable ordinal, and the only way of making sense of it that I see is taking the union, this is what is usually done for limit ordinals in definitions using transfinite recursion. If you are not taking the union you are doing it up to some fixed countable ordinal (which can be chosen arbitrarily). – Kaveh May 10 '11 at 3:15

1
Then I think we agree in content, but I wouldn't put "once per ordinal" (it gives the sense of parts of a process,) but rather use "you can do this for any countable ordinal". :) – Kaveh May 10 '11 at 3:20

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$). – Kaveh May 10 '11 at 3:23
show 11 more comments
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 22, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9499518275260925, "perplexity_flag": "head"}