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
    I cannot understand in what way that is *going outside of mathematics*!2011-04-27
  • 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

4

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.

  • 0
    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...)2011-04-27
  • 0
    Not "once per countable ordinal", but only *upto* a countable ordinal.2011-05-10
  • 0
    @Kaveh: what do you mean, exactly? Saying "up to a countable ordinal" leaves too much unspecified, for there are a lot of them! If one has done this process a countable number of times, then the number of functions in the set constructed is countable, so there is always one more function to do a step more: doesn't this imply that one can at least do it once per countable ordinal?2011-05-10
  • 0
    You can do it up to *any* countable ordinal but cannot do it for *all* countable ordinals. You cannot do it for all countable ordinals because there are uncountably many (the least uncountable ordinal is exactly the set of all countable ordinals, so if you are doing it for all countable ordinals you are doing it up to the first uncountable ordinal).2011-05-10
  • 0
    @Kaveh: But *why* can't one do this for all countable ordinals? The only reason the process would stop at a countable ordinal would be that at that point the functions got exhausted: but at that point only countable many functions are in the set.2011-05-10
  • 0
    At any point yes, but at the end, when taking the union of results for all countable ordinals, it will become an uncountable set.2011-05-10
  • 0
    @Kaveh: but that is not an obstacle: there are uncountably many functions $N\to N$.2011-05-10
  • 0
    Yes, but we want the resulting set to be countable, don't we?2011-05-10
  • 0
    @Kaveh: but for *each* countable ordinal the cardinality of the set *is* countable.2011-05-10
  • 1
    Each one is countable, but the union is not, i.e. there are *uncountably* many countable ordinals!2011-05-10
  • 0
    @Kaveh, I honestly do not know why you keep mentioning the union of the sets corresponding to countable ordinals. I never did...2011-05-10
  • 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).2011-05-10
  • 0
    What I meant was: «you can repeat this once per countable ordinal and thereby get lots of examples of countable sets like you wanted». Uncountably many, in fact.2011-05-10
  • 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". :)2011-05-10
  • 0
    Well, it *is* part of a process: the process whereby you get a chain of increasing examples...2011-05-10
  • 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