The universal properties of Dedekind finite cardinals (Q2540423)

This paper deals with properties of Dedekind cardinals, which are defined as infinite cardinals \(m\) such that \(m+1\ne m\). Of course, one can assume that such cardinals exist only if one works in a set theory which does not admit the full axiom of choice. The author takes as a basis of his discussion an axiomatic system of set theory which he calls \(\mathfrak S^0\). It differs from the Gödel-Bernays system in the following two points: (a) the axiom \(E\) is replaced by the axiom of choice for arbitrary families of non-empty finite sets; (b) one assumes the existence of an infinite set of individuals which are not sets and reformulates suitably the axiom of extensionality. The modification (b) is motivated by the author's desire to use the so-called permutation method in constructing models of his set theory. He states that he is able to obtain all results also in the case of the usual Gödel-Bernays system modified as in (a). This necessitates the use of Cohen's methods in the construction of models. The modification (a) is slightly artificial; it would seem more natural to study Dedekind cardinals without any form of the axiom of choice. The author states, however, that he is able to construct models showing that most of his results are not provable if no form of the axiom of choice is admitted in set theory. The first problem discussed in the paper is to define operations on cardinals which would be natural extensions of number-theoretic functions. This is done for a rather wide class of number-theoretic functions first defined by Myhill and called by him combinatorial functions [Bull. Am. Math. Soc. 64, 373--376 (1958; Zbl 0085.24801)]. A mapping \(f \colon N^n\to N\) where \(N\) is the set of all integers and \(n\in N\), is called combinatorial if \[ f(x_1,\ldots, x_n) = \sum c(i_1, \ldots, i_n) C_{x_1i_1} \cdots C_{x_ni_n}, \] where \(C_{p,q}\) is the binomial coefficient, the \(c(i_1, \ldots, i_n)\) are non-negative integers and the summation is taken over indices \(i_j\) satisfying the inequalities \(0\le i_j\le x_j\). The author defines in purely set-theoretical terms certain operations on sets which he calls combinatorial operators. In the special case when all sets considered are contained in \(N\), these operators were defined by Myhill. For every combinatorial function \(f\) there is exactly one combinatorial operator \(F\) such that \[ \vert F(A_1,\ldots, A_n)\vert = f(\vert A_1\vert, \ldots, \vert A_n\vert) \] for arbitrary finite sets \(A_1,\ldots, A_n\) \(\vert X\vert\) denotes here the cardinal of \(X)\). This relationship between combinatorial functions and operators is one-to-one, i.e., to every combinatorial function corresponds exactly one combinatorial operator and every such operator corresponds to a combinatorial function. Furthermore, every combinatorial operator \(F\) has the property that if \(\vert A_i\vert = \vert B_i\vert\) for \(i\le n\), then \[ \vert F(A_1,\ldots, A_n)\vert = \vert F(B_1,\ldots, B_n)\vert. \] It is therefore clear that every combinatorial function can be extended to an operation on arbitrary cardinals. (Myhill extended in the same way the combinatorial functions to operations on arbitrary recursive equivalence types.) The second problem dealt with in the paper is this: Which propositions of the form \((x_1, \ldots,x_n) \mathfrak A (x_1, \ldots,x_n)\) valid for all integers are also valid for all Dedekind cardinals? The basic result, given in Theorem 6, states that this is the case when \(\mathfrak A\) is the formula \(f_0(x) = f_1(x) \to g_0(x) = g_1(x)\), where \(f_0,f_1,g_,g_1\) are combinatorial functions and \(x\) standsfora string of \(n\) variables. This result is further extended to the case when \(\mathfrak A\) is an arbitrary Horn sentence. More generally, the author formulates (in the language of set theory) a condition \(\mathfrak{Cond}(\mathfrak A)\) with the two properties: If \(\mathfrak{Cond}(\mathfrak A)\), and \(\mathfrak A\) is true for all integers, then it is also true for all Dedekind cardinals; there is an extension \(\mathfrak S_0^0(\Delta)\) of \(\mathfrak S^0\) consistent relative to \(\mathfrak S^0\) and such that it is provable in \(\mathfrak S_0^0(\Delta)\) that if \(\mathfrak A\) is true for all Dedekind cardinals, then \(\mathfrak{Cond}(\mathfrak A)\). Thus formulas satisfying \(\mathfrak{Cond}(\mathfrak A)\) form a largest class for which one can prove in \(\mathfrak S^0\) that if \(\mathfrak A\) is true for all integers, then it is true for all Dedekind cardinals. The extension \(\mathfrak S_0^0(\Delta)\) is obtained from \(\mathfrak S^0\) by adjoining the axiom which states the existenxe of a cardinal \(x\) with this property: whenever \(f\) and \(g\) are combinatorial functions and \(f(x) = g(x)\), then the equation \(f(n) = g(n)\) is true for almost all integers \(n\); thus \(x\) is, so to speak, a generic zero of the equations \(f(n)=g(n)\). In the final part of the paper, the author deduces a number of corollaries from his previous general theorems. These corollaries have either the form of cancellation laws for Dedekind cardinals and are proved in \(\mathfrak S^0\), or the form that there exist Dedekind cardinals which do not satisfy certain cancellation laws and are proved in \(\mathfrak S_0^0(\Delta)\). A typical example of a cancellation law is: \(m^k = n^k\to m = n\) for finite \(k\); a typical example of a negative result is: there are Dedekind cardinals \(m\) and \(n\) such that \(m^{k+2} \le n^{k+2}\) and \(m\not\le n\).