Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality

“The Axiom of Choice is obviously true, the well-ordering principle is obviously false, and who can tell about Zorn’s Lemma?” —Jerry L. Bona, [55, p. 145]

The Axiom of Choice (AC), in one of its many equivalent incarnations, says that for every collection (X_i)_i∈I of non-empty sets X_i (where I is an arbitrary index set), there is a “choice function” \(x\colon I \to \bigcup _{i \in I} X_{i}\) such that x(i) ∈ X_i for all i. Despite being non-constructive, this axiom is extremely useful throughout much of mathematics. In classical, Zermelo–Fraenkel set theory (ZF), there are many statements that are equivalent to AC. We refer to the books by Herrlich [37] and Rubin & Rubin [53, 54] for the classical AC and its many equivalent versions. Yet despite being equivalent in ZF, many versions often “feel” different, as captured nicely by Bona in the above quotation.

In this paper, we study several statements that are classically equivalent to AC and propose polynomial-time analogues that seem not to be equivalent to one another (under standard complexity assumptions). We show their relationship with some standard—and some less standard—complexity questions, most with relations to Alan Selman’s work, which is part of why we thought it fitting to submit to this memorial volume.

Informal Definition. A polynomial-time axiom of choice is any statement S which, if the words “polynomial-time,” “polynomially-bounded,” and similar were removed from S, would be equivalent (in Zermelo--Fraenkel set theory) to the usual Axiom of Choice.

Throughout this paper, our general philosophy is that “set” should become “language in P” and “function” should become “function in FP.” Where there are several obvious choices for how to formulate a polynomial-time version of AC equivalent to a given standard formulation, we generally avoid formulations that are trivially true or trivially false.

Because several statements classically equivalent to AC are phrased in terms of cardinals, we also develop a polynomial-time theory of “p-cardinals” in Section 4. The basic idea is as follows: Cantor’s idea of cardinality was that two sets have the same “size” iff there is a bijection between them, so by analogy, we say two languages \(A \subseteq {\Sigma }^{\ast }, B \subseteq {\Gamma }^{\ast }\) should have the same p-cardinality if there is a polynomial-time computable, polynomial-time invertible bijection between A and B. The key difference between this and the notion of p-isomorphism is that a p-isomorphism A → B must be given by a total p-computable, p-invertible bijection f : Σ^∗→Γ^∗ such that f(A) = B, whereas in our case we focus more on the sets themselves, only requiring our bijection to be computable and invertible in polynomial time when restricted to the sets A,B. Outside these sets it need not be injective nor surjective.

Our notion of p-cardinality turns out to be related to several complexity-theoretic notions of interest in Selman’s work, including p-enumerability (Observation 4.15 and Proposition 4.17), the Isomorphism Conjecture (Section 4.2), p-rankability (Section 4.3), and immunity (in Propositions 4.6 and 4.36). We suspect it has further relationships with other of Selman’s interests including disjoint NP pairs [17, 22,23,24], mitoticity [18,19,20], splitting [21], and p-selectivity [34, 48, 58, 59], but leave these as exciting future directions.

1.1 Related Work

Constructive versions of AC, even in the context of computability, have been studied previously, e. g., [8, 13], but we are not aware of other work studying polynomial-time analogues of AC.

For p-cardinality, the most closely related work is that of Nerode & Remmel [49,50,51,52]. They developed not only a theory of polynomial-time cardinals, called “polynomial equivalence types” or “PETs” (in analogy with previously studied recursive equivalence types [11], see [10]), but also began to develop a theory of polynomial-time structures such as vector spaces, groups, etc., in analogy with work on computable structures (see, e. g., [3, 9, 47]). However, their polynomial-time theory was developed for unary languages.

While the choice to use unary languages enabled many analogies with the recursive case to go through and led to a rich and interesting theory, it was mostly disconnected from more standard complexity questions such as P versus NP, because the latter are typically formulated over an alphabet of size at least 2. Downey, in his review [12] of [51] writes:

“What is not yet clear is the relationship, if any, of complexity questions (such as P=?NP) with [51]. For instance, it would be truly fascinating if the techniques could be used to prove P = NP to be independent of [intuitionistic Zermelo–Fraenkel set theory] via an analogue of McCarty’s work [44, 45]. Perhaps what is needed is the development of the theory over the standard languages \(\subseteq \{0,1\}^{\ast }\).” –R. Downey [12]

Here (Section 4) we pursue one such development of the theory over standard languages, that is, over alphabets of size at least 2. While we do not yet realize Downey’s suggestion about independence from IZF, we lay some possible foundations of such a theory. In fact, this paper originally was focused on AC, with p-cardinality as just a side note, and it was our discovery of Downey’s quote that spurred us on to develop some of the foundations of p-cardinality further.

1.2 Selman’s Influence on my Work

I only met Alan personally a few times—I think once when I visited Steve Homer at Boston University (to give my first talk on complexity theory research), and once or twice at the Conference on Computational Complexity. But even from those few meetings one could tell that he was nice, generous with his ideas and time, had broad interests, and seemed genuinely very happy to talk about complexity theory.

But his influence on my work extends far beyond just our few chance meetings. The general theme is this: when I started graduate school and was talking with Lance Fortnow and other members of the Theory group at U. Chicago (at the time: Stuart Kurtz, Ketan Mulmuley, Janos Simon, Laci Babai, and shortly after I joined, also Sasha Razborov), I was just over-the-moon with structural complexity theory. Properties of complexity classes, properties of (formal) languages, p-isomorphism, complexity cores, p-selectivity—I loved it all (still do!). Early on in my graduate career Selman’s two edited volumes [36, 61] were very influential on my thinking. Every chapter of [61] is related to something I have worked on at one point in my life (even if not resulting in any publications). They are still some of my favorite advanced complexity books on my shelf—and yes, I actually have the physical books, on a physical bookshelf.

While working on my first complexity paper [16], Lance pointed me to Selman’s taxonomy of function classes [62,63,64], and one can see that NPMV and its kin play an important role in that paper. Personal admission: I never really understood the definition of TFNP until reading Selman’s work on NPMV,NPSV, and their relatives. One of Selman’s results was in fact part of the motivation for [16] (discussed in my master’s thesis [28, Section 3.2]): although most function classes behave like their decision class counterparts, we have \(\mathsf {P}^{\mathsf {NP}[\log ]} = \mathsf {P}_{tt}^{\mathsf {NP}}\) [7, 31, 67] but Selman showed that for the corresponding function classes this is unlikely:

Theorem 1.1 (Selman 63)

\(\mathsf {FP}^{\mathsf {NP}[\log ]} = \mathsf {FP}_{tt}^{\mathsf {NP}}\) implies NP = RP and P = UP.

After that first complexity paper, I was hooked (if I wasn’t before). One of my favorite open oracle questions is still from Selman’s work. It remains open whether NP = UP collapses PH. But more than that, we don’t even know that it requires non-relativizing techniques. We wish to highlight this question here:

Open Question 1.2 (Folklore)

Build an oracle relative to which NP = UP but PH is infinite.

Hemaspaandra, Naik, Ogihara, and Selman [35] showed that a closely related statement does in fact collapse PH to Σ₂P. Namely, they showed that this collapse of PH follows from the assumption that \(\mathsf {NPMV}_{g} \subseteq _{c} \mathsf {NPSV}_{g}\). All terms are defined in Section 2, but for now, we can say that the latter statement is equivalent to: for every language \(A \subseteq {\Sigma }^{\ast } \times {\Sigma }^{\ast }\) in P, there is another language B “refining” A, in the sense that for all x ∈Σ^∗, if (x,y) ∈ A, then there exists some y_x such that (x,y_x) ∈ A and (x,y_x) is the unique element of B with first coordinate x. This implies NP = UP, and feels philosophically very closely related (indeed, it is the kind of statement that someone not familiar with it might mistake for the definition of NP = UP). I spent at least a summer, possibly more, in graduate school under Lance’s guidance trying to answer Question 1.2. The issue is that most naive ways of thinking about how to get NP = UP—and I was definitely naive at the time, probably still am—also imply \(\mathsf {NPMV}_{g} \subseteq _{c} \mathsf {NPSV}_{g}\), and thus that PH = Σ₂P. To get around this barrier, we first sought to build an oracle relative to which NP = UP but PH≠Σ₂P. We did not manage to do that, but I mention this because it led us to another of Selman’s works. Rather than trying to fully separate the levels of PH, which seems to require using the full strength of AC⁰ circuit lower bounds, we just sought to separate its second level, and Baker and Selman had built an oracle separating just two levels of PH [4], so we looked to their work for inspiration.

At this point I don’t remember why, but around the same time I was also led to read Selman’s work on disjoint pairs, mitoticity, immunity, and p-selectivity (e. g., [19, 22, 30, 33, 48]). In fact, Selman’s work on search-to-decision reductions was part of what spurred my interest, leading me to discuss them in the context of Group Isomorphism with Youming Qiao in graduate school over a decade ago; we just recently made progress on that problem [29].

Even though we didn’t solve Question 1.2, it was a glorious several months being fully immersed in Selman’s work, that had an influence on my thinking and my career, and will stick with me for the rest of my life. Thanks Alan—your intellectual legacy lives on, and you are missed.

Throughout, Σ (and sometimes also Γ) is a finite alphabet of size at least 2, containing at least the symbols 0,1. 𝜖 denotes the empty string, the unique string of length zero. |x| denotes the length of a string. Length-lexicographic ordering is defined by x <_lexy if |x| < |y|, or if |x| = |y| and x lexicographically precedes y, where lexicographic ordering is given according to some fixed (but unspecified, implicit) total order on Σ. Σ^∗ denotes the set of all finite strings over the alphabet Σ.

We move back and forth freely between Σ^∗ and \(\mathbb {N}\) as follows. The natural number associated to x ∈Σ^∗ is the number of strings that are ≤_lexx, and vice versa, so e. g., if Σ = {0,1,2} we have the association

For two strings x,y and a natural number n, when we write x + y or x + n, we first convert all strings to natural numbers using the above convention, then add them, and then convert back to the corresponding string, if needed.

For a language \(A \subseteq {\Sigma }^{\ast }\) we abuse notation by writing A(x) = 1 iff x ∈ A and A(x) = 0 iff x∉A. \(\overline {A}\) denotes the complement of A, \(\overline {A} = \{x \in {\Sigma }^{\ast } : x \notin A\}\).

A polynomial-time many-one reduction from A to B is a p-computable total function f such that x ∈ A ⇔ f(x) ∈ B for all x ∈Σ^∗, equivalently, A(x) = B(f(x)). In this case we write \(A {\leq _{m}^{p}} B\). If \(A {\leq _{m}^{p}} B\) and \(B {\leq _{m}^{p}} A\) we write \(A {\equiv _{m}^{p}} B\) and say that A and B have the same polynomial-time many-one degree (of difficulty). A bounded truth-table, or \(\leq _{btt}^{p}\), reduction is a nonadaptive Turing reduction that makes O(1) queries (we only use \(\leq _{btt}^{p}\) in reference to other people’s results). \(A \subseteq {\Sigma }^{\ast }\) and \(B \subseteq {\Gamma }^{\ast }\) are p-isomorphic, denoted A≅^pB, if there is a total, polynomial-time computable bijection f : Σ^∗→Γ^∗ for which f^− 1 is also computable in polynomial time, and such that f(A) = B.

For two languages \(A, B \subseteq {\Sigma }^{\ast }\), A ⊕ B denotes the “tagged” disjoint union {0a : a ∈ A}∪{1b : b ∈ B} and A × B denotes the usual Cartesian product. Pairs, tuples, etc. of strings are encoded using any of the standard polynomial-time computable and polynomial-time invertible bijections Σ^∗ →Σ^∗×Σ^∗. We write A =^∗B if their symmetric difference (A∖B) ∪ (B∖A) is finite.

We follow notation for partial, multi-valued functions set down by Selman [35, 63]. A (possibly) partial, multivalued function f is technically a relation \(\subseteq {\Sigma }^{\ast } \times {\Sigma }^{\ast }\), but we think of the first coordinate of this relation as inputs and the second as outputs, and we use standard functional language and notation. Rather than the relation notation xfy, we write f(x)↦y, but note that there may be more than one such y for a given x (so we are careful not to write f(x) = y unless there is exactly one output for f(x)). We write

Nondeterministic Turing machine transducers—machines with separate output tapes—naturally compute partial, multi-valued functions. Given such a machine M, we define f_M(x)↦y iff there is some accepting computation of M that halts with y on its output tape, and we say that f_M is computed by M. There is a related but subtly different function also associated with M that will be useful, namely acc_M(x)↦y iff y is the ordered list of nondeterministic choices made on an accepting branch of M; note that dom(f_M) = dom(acc_M) = L(M), the language accepted by M.

Abusing ordinary function notation, for two partial, multi-valued functions f,g, we may write, e.g., f(x,g(x)) to indicate the partial, multivalued function c(x) with c(x)↦z iff there is an output g(x)↦y such that f(x,y)↦z. (This also corresponds to composition of relations.)

We refer to a nondeterministic, polynomial-time machine M as “an NP machine”.

NPMV is the class of (possibly) partial, multi-valued functions computed by NP machines. NPSV is the subclass of NPMV consisting of those functions that are in fact single-valued, though they may still be partial and may have multiple accepting branches (as long as they all make the same output). PF is the class of functions computed by NP machines that use no nondeterminism, but may still be partial (viz., if they reject some input). FP is the class of total functions computed by deterministic polynomial-time machines.

A multivalued function f is a refinement of a multivalued function g if dom(f) = dom(g) and \(set\text {-} f(x) \subseteq set\text {-} g(x)\) for all x (this second condition is equivalent to f(x)↦y implying g(x)↦y). If \(\mathcal {F}_{1}, \mathcal {F}_{2}\) are two classes of functions, we write \(\mathcal {F}_{1} \subseteq _{c} \mathcal {F}_{2}\) if every \(f \in \mathcal {F}_{1}\) has a refinement in \(\mathcal {F}_{2}\).

For any function f —whether it be injective or not, single-valued or not, total or not, surjective or not—we define f^− 1 to be the partial multivalued function defined by f^− 1(y)↦x iff f(x)↦y. Given a class \(\mathcal {F}\) of functions, we say f is invertible in \(\mathcal {F}\) if f^− 1 has a refinement in \(\mathcal {F}\). By our symbolic conventions, note that even though f^− 1 may be partial and multivalued, we always have f^− 1(f(x))↦x. We also have f(f^− 1(x))↦x iff x is in the image of f.

A function f is (polynomially) honest if there is a polynomial p such that for every input x, there is some output y such that |x|≤ p(|y|). Note that honesty is a necessary condition to have some refinement of f^− 1 be computable in polynomial space, let alone polynomial time.

For these function classes, there are a number of subscripts to use that denote subclasses:

• The subscript t denotes the subclass of total functions, that is, whose domain is all of Σ^∗

• The subscript h denotes the subclass of honest functions

• The subscript g denotes the subclass of functions whose graph, \(\left \{ (x,y) : f(x) \mapsto y\right \}\), is decidable in polynomial time.

These subscripts may be used in any combination, e. g. NPMV_ght.

Selman [63] and Hemaspaandra, Naik, Ogihara, and Selman [35] showed that

Theorem/Definition Q ([14, Theorem 2]) Hypothesis Q is any of the following equivalent statements

1. Q1

   For all NP machines M that accept Σ^∗, there exists a polynomial-time computable function g_M such that for all x, g_M(x) outputs an accepting computation of M on x.

2. Q2

   All polynomial-time computable onto honest functions are invertible in PF.

3. Q3

   \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {FP}\).

4. Q4

   For all S ∈P such that \(S \subseteq \text {SAT}\), there exists a polynomial-time computable g such that for all x ∈ S, g(x) outputs a satisfying assignment of x.

5. Q5

   P = NP ∩coNP and \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {NPSV}_{t}\).

6. Q6

   For all NP machines M such that L(M) = SAT, there is f_M ∈PF such that for all φ ∈SAT, φ(f_M(φ,acc_M(φ))) = 1, that is, f_M takes in φ and any accepting computation of M on φ, and outputs at least one satisfying assignment to φ, and all such outputs satisfy φ.

7. Q7

   For all NP machines M,N such that \(L(M) \subseteq L(N)\), there is f_M ∈PF such that for all x ∈ L(M), f_M(x,acc_M(x)) makes some output, and all its outputs are accepting computations of N(x).

8. Q8

   For all L ∈P and all NP machines M accepting L, there is f_M ∈PF such that f_M(x) is an accepting computation of M(x).

The formulations in this section are mostly based on choice functions for collections of sets. If \(S = \left \{S_{i} : i \in I\right \}\) is a collection of sets (where I is an arbitrary index set), then a choice function for S is a function f such that f(i) ∈ S_i for all i ∈ I.

Definition 3.1 (Collection of languages, honestly non-empty, choice function)

Given a complexity class \(\mathcal {C}\), a \(\mathcal {C}\) collection of languages is a single language \(L \in \mathcal {C}\) such that each \(L_{x} := \left \{y : (x,y) \in L\right \}\) is also in \(\mathcal {C}\).

A collection L of languages is honestly non-empty if there are polynomials p,q of positive degree such that, for every x, L_x contains at least one string y of length p(|x|) ≤|y|≤ q(|x|). We call p,q “honesty (lower, resp. upper) bounds” for L.

A partial, multi-valued function f is a choice function for a collection L of languages if: (1) for all x, \(set\text {-} f(x) \subseteq L_{x}\), and (2) for every nonempty L_x, set-f(x) is nonempty.

Remark 3.2

The polynomial upper bound in the definition of honestly non-empty is easy enough to justify at this point: there should at least exist a y in L_x that did not require super-polynomial-space to write down (so, e.g., if L ∈PSPACE, then such a y could be found by a polynomial-space machine). But the polynomial lower bound may seem less intuitive. It turned out to be a very natural and useful condition at several points, e.g. Observation 3.6 and Proposition 3.8(1).

Classical AC 1 (See [53, AC1, p. 5]). Every collection of non-empty sets has a choice function.Polynomial-Time AC (PAC) 1 Every P collection of honestly non-empty languages has a choice function in FP.

Proposition 3.3

PAC1 holds iff \(\mathsf {NPMV}_{gt} \subseteq _{c} \mathsf {FP}\).

Proof

(⇒) Suppose PAC1 holds. Let f be an NPMV_gt function and let L be the graph of f. By definition of NPMV_g, the graph of f is in P, so L ∈P. Since f is total, every L_x is non-empty. Since each branch of f is polynomial-time, every output y of f(x) has |y|≤poly(|x|). To get a polynomial lower bound as well, we modify f to \(\hat {f}\), defined by \(\hat {f}(x) \mapsto (x,y) \Leftrightarrow f(x) \mapsto y\), so that every output now has \(|x| \leq |\hat {f}(x)|\). Let \(\hat {L}\) be the graph of \(\hat {f}\); \(\hat {L}\) is now a P collection of honestly non-empty languages. Thus, by assumption, there is a polynomial-time choice function \(\hat {g}\) for \(\hat {L}\). By construction of \(\hat {L}\), \(\hat {g}(x)\) always has the form (x,y). Finally, define \(g(x) = y \Leftrightarrow \hat {g}(x) = (x,y)\). It is clear that g is also in FP and refines f.

(⇐) Conversely, suppose \(\mathsf {NPMV}_{gt} \subseteq _{c} \mathsf {FP}\), and let L be a P collection of honestly non-empty languages, with honesty bounds p,q. Define f by

Since L ∈P, the graph of f is in P: use the polynomial-time decider for L, together with verifying the length relationship between x,y. Moreover, since L_x is honestly non-empty for every x, f is total, so f is in NPMV_gt. By assumption f has an FP refinement, which is clearly a polynomial-time choice function for L. □

The same argument can be trivially modified to several other standard complexity hypotheses, by varying the constraints in PAC1. We give two such here:

Proposition 3.4

Every NP collection of honestly non-empty languages has...

1. 1.

   ...an NPSV_t choice function iff \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {NPSV}_{t}\).

2. 2.

   ...an FP choice function iff \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {FP}\); note the latter is Hypothesis Q3.

Thus we see that Hypothesis Q is equivalent to a mixed nondeterministic/deterministic polynomial-time version of the Axiom of Choice. We will see below that Polynomial-Time AC 7 is also equivalent to Q.

Proof

Let \(\mathcal {F} \in \left \{\mathsf {NPSV}_{t}, \mathsf {FP}\right \}\).

(⇒) Suppose every NP collection of honestly non-empty languages has an \(\mathcal {F}\) choice function. Let f be in NPMV_t. As before, let \(\hat {f}(x) \mapsto (x,y) \Leftrightarrow f(x) \mapsto y\), and let \(\hat {L}\) be the graph of \(\hat {f}\). Since every NPMV function has its graph in NP, \(\hat {L}\) is in NP. As above, \(\hat {L}\) is an honestly non-empty collection of languages. By assumption, there is a choice function \(\hat {g} \in \mathcal {F}\) for \(\hat {L}\). Define g(x) by \(g(x) = y \Leftrightarrow \hat {g}(x) = (x,y)\); for either choice of \(\mathcal {F}\) it is clear that \(\hat {g} \in \mathcal {F} \Leftrightarrow g \in \mathcal {F}\). As above, g is clearly a refinement of f, and thus \(\mathsf {NPMV}_{t} \subseteq _{c} \mathcal {F}\).

(⇐) Conversely, suppose \(\mathsf {NPMV_{t}} \subseteq _{c} \mathcal {F}\), and let L be an NP collection of honestly non-empty languages, with honesty bounds p,q. Define f by

Since L ∈NP, the graph of f is in NP: use the polynomial-time verifier for L, together with verifying the length relationship between x,y. Moreover, since L_x is honestly non-empty for every x, f is total, so f is in NPMV_t. By assumption f has an \(\mathcal {F}\) refinement, which is clearly an \(\mathcal {F}\) choice function for L. □

Classical AC 2 (See [53, AC2, p. 5], [37, Proposition 2.1]) Given any set X of pairwise disjoint nonempty sets, there is a set C that contains exactly one element from each set in X.

Definition 3.5 (Transversal)

Given a collection L of languages, a transversal for L is a language C such that C ∩ L_x has exactly one element, for each x such that L_x is nonempty.

Polynomial-Time AC (PAC) 2 Every polynomial-time collection of honestly nonempty languages that are pairwise disjoint, has a transversal in P.

While we have not been able to get a polynomial-time upper bound on transversals of such collections, we can give an upper bound within the second level of PH. More specifically, recall that \(\mathsf {DP} = \{ L \subseteq {\Sigma }^{\ast } : L = L_{1} \backslash L_{2} \text { for some } L_{1}, L_{2} \in \mathsf {NP}\}\). DP is contained in P^NP, and even in P^NP[2] (the machine only makes 2 queries on inputs of length n). For any language L, we relativize DP to DP^L, by taking the preceding definition and replacing NP with NP^L.

Observation 3.6

Every collection L of pairwise disjoint, honestly non-empty languages has a transversal in DP^L.

Proof

Let p,q be honesty bounds for L, so that each L_x contains some y with p(|x|) ≤|y|≤ q(|x|). Let C consist of the lexicographically first element of L_x with length at least p(|x|), for each x ∈Σ^∗. Since the L_x are pairwise disjoint, C does not contain more than one element of each L_x, and thus it contains exactly one and is a transversal.

We now show that membership in C can be decided in DP^L. Let L₁ = {y : (∃x)[q^− 1(|y|) ≤|x|≤ p^− 1(|y|) and (x,y) ∈ L} and let \(L_{2} = \{ y : (\exists y^{\prime } <_{lex} y)(\exists x)[ \max \limits \{q^{-1}(|y^{\prime }|), q^{-1}(|y|)\} \leq |x| \leq \min \limits \{p^{-1}(|y|), p^{-1}(|y^{\prime }|)\} \text { and } (x,y) \in L \text { and } (x,y^{\prime }) \in L\}\). Note that L₁,L₂ are both in NP^L, and we have C = L₁∖L₂. □

Thus for collections in P, there always exists an DP transversal.

Open Question 3.7

Is there a P collection of pairwise disjoint, honestly non-empty polynomial-time languages such that every transversal for L is NP-hard? NP-complete? DP-complete?

While we do not have a clean equivalence between PAC2 and a more standard complexity hypothesis, we do have such a clean equivalence between more standard hypotheses and some NP versions of PAC2.

Proposition 3.8

1. 1.

   \(\mathsf {NPMV}_{gt} \subseteq _{c} \mathsf {NPSV}_{t}\) iff

   (*) every P collection of honestly nonempty, pairwise disjoint languages has a transversal in NP.

2. 2.

   \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {NPSV}_{t}\) iff

   (*\(^{\prime }\)) every NP collection of honestly nonempty, pairwise disjoint languages has a transversal in NP.

Proof

(1) Suppose (*) holds, and let f ∈NPMV_gt. Let L be {(x,(x,y)) : x ∈Σ^∗,f(x)↦y} be a modified version of the graph of f. By definition the graph of f is in P, so L is also in P. Since f is total and each nondeterministic branch uses at most polynomial time, every L_x is honestly nonempty. Since every element of L_x is of the form (x,∗), L_x and L_y are disjoint when x≠y. Hence there is a set C ∈NP that contains exactly one element from each L_x. We define an NPSV_gt function g that, on input x, nondeterministically guesses y and w, uses w as a witness to verify that (x,y) ∈ C, and outputs y. This g is an NPSV_t refinement of f.

Conversely, suppose \(\mathsf {NPMV}_{gt} \subseteq _{c} \mathsf {NPSV}_{t}\), and let L be a P collection of honestly nonempty, pairwise disjoint languages with honesty bounds p,q. Define f by

Since L ∈P, the graph of f is in P. Moreover, since L_x is honestly non-empty for every x, f is total. Hence f has an NPSV_t refinement g. Let C be the image of g. It is clear that C intersects each L_x exactly once. The following nondeterministic machine shows that C is in NP: on input y, it guesses x such that p(|x|) ≤|y| (so in particular |x|≤poly(|y|)), guesses an accepting path of g, simulates the execution of g(x) on that accepting path, and accepts if the output on that path is equal to y.

(2) We observe here how the preceding parts of the proof change for the second part. For f ∈NPMV_t, its graph (and modified graph as above) will be in NP. (*\(^{\prime }\)) then allows us to conclude existence of a C ∈NP as before, and the rest of the argument goes through. For the other direction of the argument, if L is only in NP, then f will still be in NPMV_t, so the assumption \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {NPSV}_{t}\) is still enough to get the NPSV_t refinement, and again the rest of the proof goes through. □

We note that it is only in the final step of the proof—in which a nondeterministic machine must guess a preimage x ∈ g^− 1(y)—that nondeterminism seems to be needed, which is the only obstacle standing in the way of an equivalence with PAC2.

The preceding results let us show that two NP versions of AC are equivalent:

Corollary 3.9 (“N P Axiom of Choice 1=N P Axiom of Choice 2”)

Every NP collection of honestly non-empty languages has an NPSV choice function iff every NP collection of pairwise disjoint honestly non-empty languages has an NP transversal.

Proof

Proposition 3.4(1) says that the first condition in the statement here is equivalent to \(\mathsf {NPMV}_{t} \subseteq _{c} \mathsf {NPSV}_{t}\), and Proposition 3.8(2) shows the latter is equivalent to the second condition in the statement here. □

Observation 3.10

PAC2 implies condition (*) from Proposition 3.8.

Proof

The conclusion of PAC2 implies existence of a P transversal, while the conclusion of (*) merely requires an NP transversal, but otherwise the two are the same. □

Classical AC 3 (See [53, AC5, p. 5]) For every function f there is a function g such that dom(g) = img(f) and for every x ∈dom(g), f(g(x)) = x.Polynomial-Time AC (PAC) 3 For every partial polynomial-time honest function f ∈PF, there is a g ∈PF with dom(g) = img(f) such that for every x ∈dom(g), f(g(x)) = x.

Recall that a (worst-case) one-way function is a one-one, honest function f ∈PF such that f^− 1∉PF, so PAC3 is simply the statement that one-way functions do not exist. This was one of the topics Selman worked on:

Theorem 3.11 (Grollman and Selman 30 and Ko [39])

PAC3 holds iff P = UP.

4.1 Definition and Basic Properties

Several formulations of the Axiom of Choice are based on cardinalities. Here we develop polynomial-time analogues of these. This development is also partially motivated by the quotation from Downey [12] in Section 1.

Let Σ,Γ be two finite alphabets. For \(A \subseteq {\Sigma }^{\ast }\) and \(B \subseteq {\Gamma }^{\ast }\), by a “partial function f : A → B” we mean a partial function f : Σ^∗→Γ^∗ such that \(A \subseteq \text {dom}(f)\) and \(f(A) \subseteq B\). For inputs x∉A, we impose no restrictions on f(x)—it might be in B, outside of B, or undefined. When we speak of properties of such a partial function—e. g., being computable in polynomial time, being injective, surjective, bijective, etc.—we only refer to these properties as they apply to inputs in A and outputs in B. For example, a partial function f : A → B is injective iff for all distinct x,y ∈ A, f(x) and f(y) are distinct. Even if f is defined on inputs outside of A, it may be non-injective on those inputs, or even have f(x) = f(a) for some x∉A,a ∈ A, and still be considered an injective partial function A → B. We say a partial function f : A → B is polynomial-time invertible, or p-invertible, if f^− 1: f(A) → A is single-valued (equivalently, f is injective) and polynomial-time computable on f(A). A partial function f is length-increasing if |f(x)| > |x| for all x ∈dom(f).

Definition 4.1

Two sets \(A \subseteq {\Sigma }^{\ast }, B \subseteq {\Gamma }^{\ast }\) have the same p-cardinality or are p-equipollent if there are partial polynomial-time computable functions f : A → B and g: B → A such that f ∘ g = id_B and g ∘ f = id_A. In this case we call f a p-equipollenceA → B.

We denote the p-cardinality of A—or, the same, its p-equipollence class—by ∥A∥_p, so ∥A∥_p = ∥B∥_p means that A and B are p-equipollent.

We say that the p-cardinality of A is at most that of B, denoted ∥A∥_p ≼∥B∥_p, if \(\|{A}\|_{p} = \|{B^{\prime }}\|_{p}\) for some subset \(B^{\prime } \subseteq B\). ∥A∥_p ≺∥B∥_p denotes ∥A∥_p ≼∥B∥_p and ∥A∥_p≠∥B∥_p.

The relation ≼ between p-cardinals is transitive and reflexive, but we will see in Proposition 4.4 that it is not a partial order, that is, there exist A,B for which ∥A∥_p ≼∥B∥_p and ∥B∥_p ≼∥A∥_p but ∥A∥_p≠∥B∥_p; however see Theorem 4.10 for a partial positive result. This is why we maintain the notation ≼ (rather than, say, ≤, as is typically done for cardinals). In Proposition 4.39 we will also see that it is not total (there are incomparable p-cardinals).

As we do with many-one reductions, it would make sense to introduce an equivalence relation ∥A∥_p ≡∥B∥_p defined by ∥A∥_p ≼∥B∥_p and ∥B∥_p ≼∥A∥_p; roughly speaking, the relationship between equivalence and equality of p-cardinals is analogous to the relationship between Karp equivalence and p-isomorphism of languages. The quotient relation ≤ on equivalence classes of p-cardinals is a partial order by construction, but Proposition 4.39 still shows it to be only partial, not total. We will not use ≡ much, though there is surely interesting theory to be explored there.

Notational note. We have tried to consistently use the superscript^p to denote a polynomial-time version of something, but in the case of cardinality, we wanted to use ||⋅|| as it is a standard symbol for cardinality, but wanted to avoid ||⋅||^p because of its possible confusion with raising to the p-th power.

Proposition 4.2

For languages \(A \subseteq {\Sigma }^{\ast }, B \subseteq {\Gamma }^{\ast }\), if ∥A∥_p = ∥B∥_p, then \(A {\equiv _{m}^{p}} B\) unless A = Σ^∗ or B = Γ^∗. In the latter case, both of A and B are in P.

Proof

Suppose that ∥A∥_p = ∥B∥_p, and first also suppose that A≠Σ^∗ and B≠Γ^∗. We will show that \(B {\leq _{m}^{p}} A\); the reverse follows by symmetry. Let \(a_{0} \in \overline {A}\).

Let f : A → B be a p-equipollence. Let p be a polynomial and M,N Turing machine transducers such that M computes f on inputs in A in polynomial time and N computes f^− 1 on inputs in B in time ≤ p(n). The following function r is a polynomial-time reduction from B to A: on input x, run N(x) for p(|x|) steps. If N rejects or makes no output by that time, then r(x) := a₀. For \(B \subseteq \text {dom} (f^{-1}) \subseteq \text {dom}(N)\). If N(x) = y by the time it has made p(|x|) steps, check that M(y) = x. If not, then output a₀ (for if x were in B then we have M(N(x)) = f(f^− 1(x)) = x). If so, then let r(x) = y, for at this point x ∈ B iff r(x) ∈ A. (Note that it is possible that dom(N) is strictly larger than B and that dom(M) is strictly larger than A, and that M(N(x)) = x for some x outside B, so the final check that r(x) ∈ A is needed.)

If A = Σ^∗, then there is no a₀ to use, but in those cases the above reduction can directly decide whether the input x was in B, so we get B ∈P. □

Note that in the above proof we really used the fact that we had access to (partial) polynomial-time computable functions that were inverses of one another. If one tried to extend Nerode & Remmel’s theory [50, 51] from unary languages to larger alphabets using only polynomial-time, bijective, honest functions, but without the stipulation of a polynomial-time inverse (even if one required such functions in both directions, but without requiring them to be inverses of one another) such a result seems much less likely to hold.

We note that the preceding result does not extend in the natural way to ∥A∥_p ≼∥B∥_p:

Proposition 4.3

There exist infinite, co-infinite sets A,B such that ∥A∥_p ≼∥B∥_p but \(A {\not \leq _{T}^{p}} B\).

Proof

Let A be an EXP-complete set and B = 0Σ^∗ (the prefix 0 is just to ensure that B is co-infinite). Then 0A = {0a : a ∈ A} is EXP-complete, and \(0A \subseteq B\), so ∥A∥_p = ∥0A∥_p ≼∥B∥_p. But by the Time Hierarchy Theorem, \(A {\not \leq _{T}^{p}} B\), for otherwise we would have A ∈P. □

We can use Proposition 4.2 to show that ≼ is not a partial order:

Proposition 4.4 (≼ is not a partial order on p-cardinals)

There exist languages \(A,B \subseteq {\Sigma }^{\ast }\) such that ∥A∥_p ≼∥B∥_p and ∥B∥_p ≼∥A∥_p (we might denote these together as ∥A∥_p ≡∥B∥_p), but ∥A∥_p≠∥B∥_p.

Proof

Let A = 1Σ^∗, \(B = 1({\Sigma }^{\ast } \oplus B^{\prime })\) for some \(B^{\prime } \notin \mathsf {P}\). First, we have \(\|A\|_{p} = \|10{\Sigma }^{\ast }\|_{p}\), and \(10{\Sigma }^{\ast } \subseteq 1({\Sigma }^{\ast } \oplus B^{\prime })\) (for any \(B^{\prime }\)), so we get ∥A∥_p ≼∥B∥_p. In the opposite direction, since \(B \subseteq A\), we get ∥B∥_p ≼∥A∥_p. But if ∥A∥_p = ∥B∥_p, Proposition 4.2 would then give \(A {\equiv _{m}^{p}} B\) (since neither is Σ^∗), implying that B ∈P, contradicting the fact that \(B {\equiv _{m}^{p}} B^{\prime } \notin \mathsf {P}\). □

4.2 Comparison with p-isomorphism

Note that, a priori, having the same p-cardinality is a weaker condition than being p-isomorphic, since the bijections required for p-cardinality need not be total, nor be bijections on all of Σ^∗. Our first two results in this direction help clarify the relationship between the two.

Proposition 4.5

If A≅^pB, then ∥A∥_p = ∥B∥_p and \(\|\overline {A}\|_{p} = \|\overline {B}\|_{p}\). The converse holds if A is in P.

After the fact, we discovered that our argument for the converse here is very similar to, but more general than, one from Goldsmith, Hemachandra, and Kunen [27], reproduced below as Corollary 4.19(2).

Proof

Suppose f : Σ^∗→Γ^∗ is a p-isomorphism A → B. Then f|_A: A → B is a p-equipollence, and similarly \(f|_{\overline {A}}\colon \overline {A} \to \overline {B}\) is a p-equipollence.

Suppose conversely that f : A → B is a p-equipollence (on A) and \(g\colon \overline {A} \to \overline {B}\) is a p-equipollence, and furthermore that A ∈P. Then the following is a p-bijection ϕ: Σ^∗→Γ^∗ that is a p-isomorphism witnessing A≅^pB. On input x, first we use the poly-time machine to decide whether x ∈ A. If so, then output f(x), and if not, then output g(x). Since Σ^∗ is the disjoint union of A and \(\overline {A}\), ϕ is a total polynomial-time bijection.

The following algorithm computes ϕ^− 1 in polynomial time. Let t(n) be a polynomial upper bound on the running time of some algorithm computing f^− 1|_B and also of some algorithm computing \(g^{-1}|_{\overline {B}}\). On input x ∈Γ^∗, try computing both f^− 1(x) and g^− 1(x) for t(n) steps. If only one of them finishes in that amount of time, then we know whether x was in B or \(\overline {B}\), and we use that as our output. However, note that the algorithm computing f^− 1 may have domain larger than B, and the algorithm computing g^− 1 may have domain larger than \(\overline {B}\), so it is possible that both f^− 1(x) and g^− 1(x) output strings y,z, respectively, within t(|x|) steps. If y = z then the algorithm may unambiguously output y without having determined whether x ∈ B or not. If y≠z, then we compute ϕ(y) and ϕ(z). Since ϕ is a bijection and y≠z, we have ϕ(y)≠ϕ(z), so only one of them can be equal to x. (And at least one of them must equal x, since x must be in at least one of \(B, \overline {B}\).) If ϕ(y) = x, then output y; if ϕ(z) = x, then output z. □

Proposition 4.6

1. 1.

   There is a p-cardinal containing infinitely many distinct p-isomorphism classes.

2. 2.

   There exist non-p-isomorphic sets A,B of the same p-cardinality in which \(\overline {A}, \overline {B}\) are both infinite and in EXP.

Note that there are no such examples where A,B are finite, for in that case ∥A∥_p = ∥B∥_p implies A≅^pB.

Proof

1. For each \(n \in \mathbb {N}\), let S_n be the set of the lexicographically first n strings. Define \(A_{n} := {\Sigma }^{\ast } \backslash S_{n}\). Then all A_n are p-equipollent to \(A_{0}={\Sigma }^{\ast }\): the p-equipollence A₀ → A_n simply shifts every string “up n” in terms of the corresponding |Σ|-ary numbers. But if \(n \neq n^{\prime }\), then \(\overline {A_{n}}\) and \(\overline {A_{n^{\prime }}}\) are finite sets of different sizes, so they are not p-equipollent. Since \(\|\overline {A_{n}}\|_{p} \neq \|\overline {A_{n^{\prime }}}\|_{p}\) in this case, they cannot be p-isomorphic, hence neither can A_n and \(A_{n^{\prime }}\).

2. We give an example with \(\overline {A}, \overline {B}\) both infinite and in EXP. Recall that a set A is P-immune if it is infinite but contains no infinite subset in P. Let A be any co-P-immune set, that is, \(\overline {A}\) is infinite but contains no infinite subsets in P. For example, Ko & Moore [40] showed that P-bi-immune sets, in which both A and its complement are P-immune, exist in EXP. Let B = {1x : x ∈ A}. Then a p-equipollence is given by A ∋ a↦1a ∈ B, with inverse B ∋ 1x↦x ∈ A. But we claim that A≇^pB. The short version is: P-immunity is preserved by isomorphism, but \(\overline {B}\) contains 0Σ^∗ as an infinite subset in P. In more detail: suppose there is a polynomial-time computable bijection f : Σ^∗→Γ^∗ such that f(A) = B and with f^− 1 ∈FP as well. Since \(f^{-1}(\overline {B}) = \overline {A}\), we have that \(f^{-1}(0{\Sigma }^{\ast }) \subseteq \overline {A}\). But f^− 1(0Σ^∗) is in P, for x ∈ f^− 1(0Σ^∗) iff f(x) begins with a 0, which is easily checked. As 0Σ^∗ is infinite and f^− 1 is a bijection, this contradicts the P-immunity of \(\overline {A}\). □

Observation 4.7

Let L∉P. If \(L {\equiv _{m}^{p}} L^{\prime }\) implies \(L \cong ^{p} L^{\prime }\), then the p-isomorphism class of L is equal to its p-equipollence class.

Proof

Since L∉P, \({\Sigma }^{\ast } {\not \equiv _{m}^{p}} L\), so the p-isomorphism class of L does not include Σ^∗. Since p-isomorphism implies p-equipollence, and p-equipollence (avoiding Σ^∗) implies \({\equiv _{m}^{p}}\) (Proposition 4.2), the result follows. □

Corollary 4.8 (cf. Kurtz, Mahaney, Royer [41])

For every set A, there is a set \(B {\geq _{m}^{p}} A\) such that the p-isomorphism class of B is equal to its p-equipollence class. There exists a set that is \(\leq _{btt}^{p}\)-complete for EXP whose p-isomorphism class is equal to its p-equipollence class.

Proof

Kurtz, Mahaney, and Royer [41] showed for every A there is a set \(B {\geq _{m}^{p}} A\) such that the polynomial-time many-one degree of B was equal to its p-isomorphism class. Such B is necessarily not in P, since P is its own poly-time many-one degree, but contains pairs of non-p-isomorphic sets. So we may apply Observation 4.7. They similarly showed a collapse result for a \(\leq _{btt}^{p}\)-complete set for EXP, which is not in P by the Time Hierarchy Theorem, so again we may apply Observation 4.7. □

In Proposition 4.6 we exhibited a p-cardinal (that of Σ^∗) containing infinitely many p-isomorphism classes; we believe much more should be true, in fact, we expect such cardinals are dense in the \({\leq _{m}^{p}}\) ordering:

Conjecture 4.9

For every set A, there is a set \(B {\geq _{m}^{p}} A\) such that ∥B∥_p contains infinitely many distinct p-isomorphism classes.

We next observe that Berman & Hartmanis’s Cantor–Bernstein-like proof extends to p-cardinality:

Theorem 4.10

Let \(A \subseteq {\Sigma }^{\ast }, B \subseteq {\Gamma }^{\ast }\), and let p: A → B and q: B → A be length-increasing, p-invertible partial polynomial-time injective functions. Then A and B have the same p-cardinality.

A proof nearly identical to that in [5, Theorem 1] works; for expository purposes, we follow the terminology and proof described in [15, Section 2].

Proof

Define the following graph G_p,q on vertex set 0A ∪ 1B: for every x ∈ A, there is an edge 0x → 1p(x), and for every y ∈ B, there is an edge 1y → 0q(y). The graph is readily seen to be bipartite by construction. Since p and q are functions with \(\text {dom}(p) \supseteq A\) and \(\text {dom}(q) \supseteq B\), every vertex has out-degree exactly 1. Since p and q are invertible, every vertex has in-degree at most 1. The connected components of G_p,q are called chains. We call a vertex a source if it has in-degree 0. Thus the graph is a disjoint union of chains, each of which is one of: finite cycles, two-way infinite paths, a one-way infinite path with its source in 0A, or a one-way infinite path with its source in 1B. Since p and q are length-increasing, there can be no finite cycles. There also cannot be any two-way infinite paths, since in following the chain backwards, the length of the strings would have to be decreasing forever. Since every vertex has out-degree 1, every vertex is part of a chain.

Let C_A be the vertices that are part of a chain with source in 0A, and C_B be the vertices in that are part of a chain with source in 1B. We define

As is usual in such proofs, it is readily verified that ϕ and ψ are inverses of one another.

Since p^− 1 need not have domain all of B, and q^− 1 need not have domain all of A, it remains to verify that ϕ (resp., ψ) can be computed in PF on domain A (resp., B). We give the proof for ϕ, the proof for ψ being similar. Let t(n) be a polynomial such that p^− 1 can be computed in t(n) time on inputs in A and q^− 1 can be computed in t(n) time on inputs in B. For inputs in A, we modify q^− 1 to a function \(\widehat {q^{-1}}\) such that \(\widehat {q^{-1}}(x) = q^{-1}(x)\) if x ∈ q(B), and otherwise \(\widehat {q^{-1}}(x)\) outputs a special symbol ⊥. The latter can be computed in \(O(t(n)\log t(n))\) time by running a t(n)-time machine for q^− 1, with an additional clock, and if the clock ever hits t(n), then stopping and outputting ⊥. Similarly we modify p^− 1 to \(\widehat {p^{-1}}\).

The key to computing ϕ efficiently is to determine whether 0x ∈ C_A or 0x ∈ C_B. It does this by applying \(\widehat {q^{-1}}\) and \(\widehat {p^{-1}}\) alternately until it gets ⊥, at which point it has found a source of the chain and thus knows which of C_A or C_B the vertex 0x is in. Since p^− 1 and q^− 1 are length-decreasing, this takes no more than time polynomial in |x|. □

Remark 4.11

We see from the proof that the main use of the length-increasing condition was that any sequence of p^− 1,q^− 1 terminated after poly(|x|) steps. Thus the argument generalizes to any p-well-orderings (see Definition 6.1) ≺_A on A and ≺_B on B such that q(p(x)) ≻_Ax and p(q(y)) ≻_By for all x ∈ A,y ∈ B.

In fact, one can get away with further generalizations. If a sequence of p^− 1,q^− 1 forms a cycle of p-bounded length, this can be detected and easily handled. The real issue with the above proof is cycles or chains such that a polynomial-time algorithm cannot identify when a string is part of such a cycle or chain. (A necessary condition is that such a cycle or chain is super-polynomially long, but there could still be very long such chains/cycles that are easily identifiable for other reasons.)

4.3 P-Countability: Density, Rankability, Enumerabililty, and Compressibility

It is natural to consider Σ^∗ to be the p-cardinality analogue of ℵ₀, the cardinality of \(\mathbb {N}\), so here we examine sets that have the same p-cardinality as Σ^∗.

Definition 4.12 (p-countable)

A set is p-countable if it is finite or has the same p-cardinality as Σ^∗.

Before we get to interesting connections, we ensure that our exploration is not dependent on alphabet:

Observation 4.13

Let Σ,Γ be two finite alphabets of size at least 2. Then \(\|{\Sigma }^{\ast }\|_{p} = \|{\Gamma }^{\ast }\|_{p}\).

Proof

Let k = |Σ|,ℓ = |Γ|. The following is a p-equipollence Σ^∗→Γ^∗. Given x ∈Σ^∗, consider the natural number N associated to it (see Section 2), and then let y be the ℓ-ary string in Γ^∗ associated with N, and output y. We have that \(|x| \sim \log _{k} N\) and \(|y| \sim \log _{\ell } N\) (since both k,ℓ ≥ 2), so |y| = Θ(|x|). It is clear that the computations can be done in polynomial time. □

Because every language is a subset of Σ^∗, every A has \(\|A\|_{p} \preceq \|{\Sigma }^{\ast }\|_{p}\), so it would seem that Σ^∗ is the “largest” p-cardinal. But remember that ≼ is only a pre-order, not a partial order, and in the proof of Proposition 4.4, we saw that for \(B^{\prime } \not \in \mathsf {P}\), \(\|{\Sigma }^{\ast }\|_{p} \prec \|{\Sigma }^{\ast } \oplus B^{\prime }\|_{p}\) (even though we also have \(\|{\Sigma }^{\ast } \oplus B^{\prime }\|_{p} \preceq \|{\Sigma }^{\ast }\|_{p}\)) but the two cardinalities are not equal. So the ≡-equivalence class of ∥Σ^∗∥_p is indeed maximal in the quotient poset, but the p-cardinal itself is not maximal in the ≼ preorder.

4.3.1 Enumerability

Selman introduced the notion of p-enumerability:

Definition 4.14 (p-enumerable, Selman 56)

A language L is p-enumerable if there is a function f ∈FP such that img(f) = L and such that for all y ∈ L, there exists x such that f(x) = y and |x|≤poly(|y|).

Note that in Selman’s definition, f need not be injective.

Observation 4.15

A p-countable set is p-enumerable.

Proof

For finite sets this is clear. For an infinite p-countable set L, let f : Σ^∗→ L be a p-equipollence. Then L is p-enumerable via f; the honesty-like condition is guaranteed by the p-computability of f^− 1. □

This also follows from the fact that the p-enumerable sets are precisely those in NP [56, Corollary 2] and p-countable sets are in P (by Proposition 4.2). This simple observation will have an interesting consequence when we get to arithmetic of p-cardinals (Proposition 4.36).

Definition 4.16 (p-enumerable by iteration 32)

A language L is p-enumerable by iteration if there is a Turing machine M and polynomial p such that for all x ∈ L, M(x) halts within p(|x|) steps, and there is some x₀ ∈ L such that \(L = \{x_{0}, M(x_{0}), M(M(x_{0})), M(M(M(x_{0}))), \dotsc \}\). L is invertibly p-enumerable by iteration if it is p-enumerable by iteration as before, and the function computed by M has a polynomial-time inverse on its image.

Hemachandra, Hoene, Siefkes, and Young [32, Section 5], among other things, gave examples of languages that were invertibly p-enumerate by iteration, including computably enumerable P-cylinders, and sets with various forms of self-reducibility. Here we add another family of examples:

Proposition 4.17

If L is p-countable then L is invertibly p-enumerable by iteration. The converse does not always hold.

Proof

For finite L this is clear, the enumerator implements a finite cycle through all the elements of L.

For infinite L, let f : L →Σ^∗ be a p-equipollence. Let x₀ = f^− 1(𝜖), and for x ∈ L define M(x) by M(x) = f^− 1(f(x) + 1)). Since f,f^− 1 and addition by constants are all p-invertible, so is M.

Hemachandra et al. [32] give examples of languages invertibly p-enumerable by iteration that are not in P, but by Proposition 4.2, p-countable languages are in P. □

4.3.2 Compressibility

Goldsmith, Hemachandra, and Kunen [27] defined a language L to be P-compressible if there is an f ∈FP, f : Σ^∗→Σ^∗ such that \(f|_{L}\colon L \to {\Sigma }^{\ast }\) is a bijection.

Observation 4.18

If L is p-countably infinite, then L is p-compressible by a function that is p-invertible.

Proof

Given a p-equipollence f : L →Σ^∗, define \(\hat {f} \colon {\Sigma }^{\ast } \to {\Sigma }^{\ast }\) by

Since f ∈PF with \(f|_{L} \colon L \to {\Sigma }^{\ast }\) a bijection, and L ∈P (since it is p-countable), clearly \(\hat {f} \in \mathsf {FP}\) and \(\hat {f}|_{L} \colon L \to {\Sigma }^{\ast }\) is still a bijection. Moreover, f^− 1: Σ^∗→ L is an inverse of \(\hat {f}\) that is in FP. □

Several results and techniques of Goldsmith, Hemachandra, and Kunen thus have immediate implications for p-countable sets; we record a particularly interesting one here.

Corollary 4.19 (cf. Goldsmith, Hemachandra, Kunen [27, Proposition 3.18])

If \(A,\overline {A},B,\overline {B}\) are all p-countably infinite, then A≅^pB.

Proof

Goldsmith–Hemachandra–Kunen [27, Proposition 3.18] use Grollman & Selman’s result that P = UP iff one-way functions do not exist [30]. Here instead, we use the fact that the p-equipollences with Σ^∗ have inverses by definition. But the following construction is otherwise the same as [27]. We include it here for completeness and ease of reference.

Let \(f_{1}\colon A \to {\Sigma }^{\ast }\) and \(f_{2}\colon \overline {A} \to {\Sigma }^{\ast }\) be p-equipollences, with extensions \(\hat {f}_{1},\hat {f}_{2}\) to total FP functions. Define

Then we have

Since \(\hat {f}_{1}, \hat {f}_{2}, f_{1}^{-1}, f_{2}^{-1}\), and the characteristic function of A are all computable in polynomial time (the latter by Proposition 4.2), so are f and f^− 1. Furthermore, f,f^− 1 are total bijections Σ^∗→Σ^∗.

Define g similarly for B. Then h(x) = f^− 1(g(x)) is a total, p-equipollence Σ^∗ →Σ^∗ with \(h(B) = f^{-1}(g(B)) = f^{-1}(0\hat {g}_{1}(B)) = f^{-1}(0g_{1}(B)) = f^{-1}(0{\Sigma }^{\ast }) = f_{1}^{-1}({\Sigma }^{\ast })=A\), so h is the desired p-isomorphism B → A. □

4.3.3 Rankability

Suppose \(L \subseteq {\Sigma }^{\ast }\) is p-countably infinite. Then there is a polynomial-time computable and invertible bijection f : L →Σ^∗. For infinite languages, ranking functions [1, 25] are a special case of bijective maps to Σ^∗:

Definition 4.20 (Ranking function, p-rankability 1, 25)

The (strong) ranking function of a language L is the map rk_L(x) = |{y ∈ L : y ≤_lexx}|. A language L is strongly p-rankable if its strong ranking function can be computed in FP, and weakly p-rankable if the ranking function can be computed in PF on those inputs that are actually in L.

From p-countability, we don’t quite get p-rankability, but we get a version if we allow replacing the ordering ≤_lex by a different ordering that shares many properties with ≤_lex. We generalize rankability to arbitrary total orderings ≺. We define the strong ranking function of L with respect to ≺ as \(rk_{L,\prec }(x) = |\left \{y \in L : y \preceq x \right \}|\), and we say L is strongly (resp., weakly) p-rankable with respect to ≺ if rk_L,≺ is in FP (resp., in PF on inputs in L).

Definition 4.21 (Length-related 46)

A total ordering ≺ on Σ^∗ is length-related if x ≺ y implies |x|≤poly(|y|).

Observation 4.22

If L is p-countable, then L is weakly p-rankable under some length-related total (on L) ordering ≺∈PF.

Proof

For finite sets this is clear. Let L be an infinite p-countable set, and let f : L →Σ^∗ be a p-equipollence. Define x ≺ y by f(x) <_lexf(y). It is clear that ≺ is computable in PF on L. Since lexicographic ordering is total on Σ^∗, ≺ is total on L. Since f is p-invertible, it is honest, so we have |x|≤poly(|f(x)|) ≤poly(|f(y)|) ≤poly(|y|), where the final inequality follows from the fact that f is computable in polynomial time. □

Next we note that p-cardinality preserves density up to polynomial transformations. Recall that the census function of a language L is \(c_{L}(n) = |L \cap {\Sigma }^{\leq n}|\). We say that two functions \(f,g\colon \mathbb {N} \to \mathbb {N}\) are polynomially related if there are polynomials p,q such that f(n) ≤ g(p(n)) and g(n) ≤ f(q(n)) for all n.

Lemma 4.23

If ∥A∥_p = ∥B∥_p, then c_A(n) and c_B(n) are polynomially related.

Proof

Let f : A → B be a p-equipollence witnessing ∥A∥_p = ∥B∥_p. Let p be a polynomial bounding the running time of f on inputs in A, and similarly let q be a polynomial bound on the running time of f^− 1|_B. Then we have

The first implies c_A(n) ≤ c_B(p(n)) and the second implies c_B(n) ≤ c_A(q(n)). □

Corollary 4.24

If L is p-countably infinite, then L is exponentially dense, that is, L has at least \(2^{\Omega (n^{c})}\) strings of length ≤ n for some c > 0.

Since p-isomorphism preserves p-cardinality, but p-rankability is not p-isomorphism invariant, we recall Goldsmith & Homer’s notion of scalability [26]. A language is p-scalable if it is p-isomorphic to a strongly p-rankable set. (We would like to introduce the obvious notion of weakly p-scalable and say that p-countability implies weak p-scalability, but we still do not know if the latter in fact holds!)

Combining the preceding results we get

Theorem 4.25

For any exponentially dense language L,

for some length-related total ordering ≺ on L, computable in PF.

So exponential density is necessary to have the same p-cardinality as Σ^∗, and among exponentially dense languages, having the p-cardinality of Σ^∗ sits in between strong and weak p-rankability (for some orderings). We believe the converses of these implications do not hold.

Proof

We show the second arrow, the others having been shown above or previously. Goldberg & Sipser [25] noted that if a language is strongly p-rankable, then \(rk_{L}^{-1}\colon {\Sigma }^{\ast } \to L\) is computable by binary search in time polynomial in the length of its output. So it suffices to show that rk_L is honest. By assumption, we have \(rk_{L}(x) \geq 2^{|x|^{c}}\). Taking bit-lengths of both sides we get |rk_L(x)|≥|x|^c − 1, so |x|≤|rk_L(x)|^1/c, and thus rk_L is honest. □

Example 4.26

This allows us to give another interesting class of languages exhibiting a difference between p-isomorphism classes and p-cardinalities. Namely, any dense proper subset of Σ^∗ that is p-scalable has the same p-cardinality as Σ^∗, but is not isomorphic to Σ^∗. The reason for the latter is that isomorphic sets have isomorphic complements, but the complement of Σ^∗ is empty, while that of the other language is non-empty by assumption.

4.3.4 Finite Differences

We now show that finite differences preserve p-countability (for infinite sets, of course). The first part of this next result, on rankability, is surely known, but we could not find a reference, and its proof serves as a good warm-up for the second part; the second part we believe is new. We use the standard notation A =^∗B to mean that A and B differ by at most a finite set.

Theorem 4.27

If A =^∗B, then

1. 1.

   A is strongly (resp., weakly) p-rankable iff B is;

2. 2.

   A is p-countable iff B is.

Proof

Suppose A =^∗B. If they are finite they are both strongly p-rankable and both p-countable, so we may now assume they are infinite.

(1) We will define a “shift function” σ(x) which tells us how much to shift as we move from A to B. We define σ inductively by

where x − 1 denotes the immediate predecessor of x in length-lexicographic order, and in case x = 𝜖 (the empty string), we simply define by convention σ(“𝜖 − 1”) := 0.

Write B = (A ∪ P)∖N where P is a finite set disjoint from A, and N is a finite subset of A. Let \(\{z_{1}, \dotsc , z_{s+t}\} = P \cup N\) with z₁ ≤_lexz₂ ≤_lex⋯ ≤_lexz_s+t. First, σ is constant on each range \([\epsilon , z_{1}), [z_{1}, z_{2}), \dotsc , [z_{s+t-1}, z_{s+t}), [z_{s+t}, \infty )\). Next, σ can be computed in polynomial time: the z_i and the values of σ on each of the preceding ranges can be hardcoded, so that on input x an algorithm merely decides which of these O(1) ranges x is in, and then outputs the right (hard-coded) value. By construction, we have rk_B(x) = rk_A(x) + σ(x) for all strings x, giving the first statement.

(2) Suppose A is p-countably infinite (the finite case was handled in the first paragraph), and A =^∗B. Let \(f \colon \mathbb {N} \to A\) be a p-equipollence. We will define a p-equipollence \(g\colon \mathbb {N} \to B\) by shifting f, similar to the above. Let B = (A ∪ P)∖N, where P is a finite set disjoint from A and N is a finite subset of A.

First we show that \(B^{\prime } = A \cup P\) is p-countable. The idea is to first enumerate P, then shift up the enumeration of A by |P|. More formally, we define \(g^{\prime }(0), g^{\prime }(1), \dotsc , g^{\prime }(|P|-1)\) to bijectively enumerate P, and then \(g^{\prime }(i) = f(i-s)\) for all i ≥ s. It is readily verified that \(g^{\prime }\colon \mathbb {N} \to B^{\prime }\) is a p-equipollence (to see p-computability and p-invertibility, note that those first |P| values can be hard-coded).

Next, we show that \(B = B^{\prime } \backslash N\) is p-countable. Let \(N = \{g^{\prime }(j_{1}), \dotsc , g^{\prime }(j_{t})\}\) with j₁ < j₂ < ⋯ < j_t. The idea is to use the same p-equipollence \(g^{\prime }\), but to shift it at appropriate points to omit \(g^{\prime }(j_{1}), \dotsc , g^{\prime }(j_{t})\). Let \(h \colon \mathbb {N} \to \mathbb {N} \backslash \{j_{1}, \dotsc , j_{t}\}\) be the bijection such that h(i) is the i-th smallest element of \(\mathbb {N} \backslash \{j_{1}, \dotsc , j_{t}\}\). It is readily verified that \(g = g^{\prime } \circ h\) is an equipollence \(\mathbb {N} \to B\). To see that it is p-computable and p-invertible, it suffices to show these for h, since \(g^{\prime }\) is already a p-equipollence. For both of these, note that h is piecewise linear with only finitely many breakpoints. By hard-coding those breakpoints and their jump values (NB: it could jump more than one, if some of the j_k are consecutive integers), h is p-computable. Since h is also strictly increasing, computing its inverse amounts to figuring out which of the intervals of linearity the input is in, and then inverting the linear function on that interval. Again, as there are only finitely many such intervals, the necessary information can be hard-coded and the remaining computation is then easy. □

This raises the question of whether, for infinite sets, two sets that are finitely different must always be p-equipollent. We thank an anonymous reviewer for a suggested construction, a slight modification of which led us to the following resolution of this question in the negative:

Theorem 4.28

There is an infinite language A ∈P such that

1. 1.

   A is not p-equipollent with any of its proper subsets (it is Dedekind p-finite, see Definition 6.2);

2. 2.

   For any two languages \(B,B^{\prime }\) that are both finitely different from A, we have \(\|B\|_{p}=\|B^{\prime }\|_{p}\) if and only if \(|B \backslash A| - |A \backslash B| = |B^{\prime } \backslash A| - |A \backslash B^{\prime }|\). In particular, not all sets finitely different from A are p-equipollent to A; and

3. 3.

   For any two languages \(B,B^{\prime }\) that are both finitely different from A, we have \(\|B\|_{p} \preceq \|B^{\prime }\|_{p}\) iff \(|B \backslash A| - |A \backslash B| \leq |B^{\prime } \backslash A| - |A \backslash B^{\prime }|\).

In particular, for this A, the preorder ≼ on the p-cardinals of sets finitely different from A is in fact a total order of the same order type as the integers. Although part (1) of the theorem already answers the question of whether finite differences preserve p-cardinality, the other two parts follow a similar proof, and will have an interesting consequence below (Corollary 4.48).

Proof

Let \(A = \{1^{2^{2^{2^{k}}}} : k \in \mathbb {N} \}\). Note that if \(\ell = 2^{2^{2^{k}}}\) is the length of a string in A, the next longest string has length exactly \(\ell ^{\log _{2} \ell }\) (this is why we used a tower of three exponentials; if we only use a tower of two exponentials, instead of \(\ell ^{\log \ell }\), we get ℓ² here).

(1) Suppose \(f \colon A \to A^{\prime }\) is a p-equipollence to a proper subset \(A^{\prime } \subsetneq A\). Let n₀ be such that for all n ≥ n₀, the running time of f on strings of length ℓ is strictly less than \(\ell ^{\log \ell }\). Then f cannot map any string in A of length at most n₀ to a string of length > n₀, so we must have that f gives a bijection between \(A \cap {\Sigma }^{\leq n_{0}}\) and \(A^{\prime } \cap {\Sigma }^{\leq n_{0}}\), and since \(A^{\prime } \subseteq A\), in fact \(A^{\prime }\) must agree with A on \({\Sigma }^{\leq n_{0}}\).

But on strings of length ≥ n₀, f must be length non-increasing, since for such a string, f(x) does not have time to write out any longer string in A. But since f was already a bijection from the strings in A of length ≤ n₀ to themselves, any x ∈ A of length ≥ n₀ has nowhere to go but itself. Thus on strings of length ≥ n₀, f must be the identity. Therefore \(A^{\prime } = A\).

(2) Let \(B,B^{\prime }\) be finitely different from A.

(⇒) Suppose \(\|B\|_{p} = \|B^{\prime }\|_{p}\); let \(f \colon B \to B^{\prime }\) be a p-equipollence. Let n₀ denote one more than the maximum length of any string x such that B(x)≠A(x) or \(B^{\prime }(x) \neq A(x)\). Note that, above length n₀, \(B,B^{\prime }\) agree with A, so they have the same \(\ell ^{\log \ell }\) gap between their elements. Thus, as above, there exists some n₁ ≥ n₀ such that neither f nor f^− 1 can map any string of length ≤ n₁ to a string of length > n₁. But then f must map \(B \cap {\Sigma }^{\leq n_{1}}\) bijectively to \(B^{\prime } \cap {\Sigma }^{\leq n_{1}}\) (with inverse f^− 1 restricted to \(B^{\prime } \cap {\Sigma }^{\leq n_{1}}\).

Now, let P = B∖A,N = A∖B, and similarly define \(P^{\prime },N^{\prime }\) with \(B^{\prime }\) in place of B. Then \(f|_{{\Sigma }^{\leq n_{1}}}\) gives a bijection from \([(A \cup P) \backslash N] \cap {\Sigma }^{\leq n_{1}}\) to \([(A \cup P^{\prime }) \backslash N^{\prime }] \cap {\Sigma }^{\leq n_{1}}\). As \(P,N,P^{\prime },N^{\prime } \subseteq {\Sigma }^{\leq n_{1}}\)—as part of the definition of n₁—and these are finite sets, and \(P,P^{\prime }\) are disjoint from A and \(N,N^{\prime }\) are subsets of A, we necessarily have \(|P| - |N| = |P^{\prime }| - |N^{\prime }|\).

(⇐) Let \(n_{0}, P, P^{\prime }, N, N^{\prime }\) be as above, and suppose \(|P|-|N| = |P^{\prime }|-|N^{\prime }|\). The following map f is a p-equipollence \(B \to B^{\prime }\). On strings of length ≤ n₀, f implements an arbitrary, hard-coded bijection from \([(A \cup P) \backslash N] \cap {\Sigma }^{\leq n_{0}}\) to \([(A \cup P^{\prime }) \backslash N^{\prime }] \cap {\Sigma }^{\leq n_{0}}\), as these are both finite sets of the same cardinality. On strings of length > n₀, f is the identity.

(3) Similar to (2). For the (⇒) direction, let \(f \colon B \to B^{\prime \prime } \subseteq B^{\prime }\) be a p-equipollence. As above, f must be the identity map for all sufficiently long strings in B, say above some length n₁. But then f gives a bijection \(B \cap {\Sigma }^{\leq n_{1}} \to B^{\prime \prime } \cap {\Sigma }^{\leq n_{1}} \subseteq B \cap {\Sigma }^{\leq n_{1}}\). As before, counting these finite sets then tells us that \(|B \backslash A| - |A \backslash B| \leq |B^{\prime } \backslash A| - |A \backslash B^{\prime }|\). For the (⇐) direction, a construction similar to part (2) works, where the hard-coded part of f is now an injection rather than a bijection. □

Open Question 4.29

If A,B are infinite languages and A =^∗B with at least n^c strings of length ≤ n (for some c > 1 and all sufficiently large n), must ∥A∥_p = ∥B∥_p? What if additionally \(A \subsetneq B\) with B∖A finite? What if, additionally, A ∈P?

Actually, the set in Theorem 4.28 does not even have logarithmic density!

4.4 Arithmetic of p-cardinals

Since many versions of AC are about cardinal arithmetic, we develop arithmetic of p-cardinals.

Proposition 4.30 (p-cardinal arithmetic)

If \(\|A\|_{p} = \|A^{\prime }\|_{p}\) and \(\|B\|_{p} = \|B^{\prime }\|_{p}\), then \(\|A \oplus B\|_{p} = \|A^{\prime } \oplus B^{\prime }\|_{p}\) and \(\|A \times B\|_{p} = \|A^{\prime } \times B^{\prime }\|_{p}\). If \(\|A\|_{p} \preceq \|A^{\prime }\|_{p}\) and \(\|B\|_{p} \preceq \|B^{\prime }\|_{p}\), then \(\|A \oplus B\|_{p} \preceq \|A^{\prime } \oplus B^{\prime }\|_{p}\) and \(\|A \times B\|_{p} \preceq \|A^{\prime } \times B^{\prime }\|_{p}\).

Defining ∥A∥_p + ∥B∥_p = ∥A ⊕ B∥_p and ∥A∥_p ×∥B∥_p := ∥A × B∥_p, the p-cardinals form a pre-ordered semi-ring with additive identity ∥∅∥_p and multiplicative identity ∥{𝜖}∥_p.

Furthermore:

1. 1.

   For all A, ∥∅∥_p ×∥A∥_p = ∥∅∥_p.

2. 2.

   For all A, \(\|\emptyset \|_{p} \preceq \|A\|_{p} \preceq \|{\Sigma }^{\ast }\|_{p}\).

3. 3.

   If A is infinite, then ∥A∥_p ≻∥F∥_p for any finite set F.

4. 4.

   For all A,B, ∥A∥_p ≼∥A∥_p + ∥B∥_p.

5. 5.

   For all A and for all nonempty B, ∥A∥_p ≼∥A∥_p ×∥B∥_p.

6. 6.

   The p-cardinalities of finite sets form a totally ordered sub-semiring that is isomorphic as an ordered semiring to \((\mathbb {N},+,\times ,\leq ,0,1)\).

7. 7.

   For all finite non-empty languages n and all languages A, we have ∥n × A∥_p = ∥A ⊕ A ⊕⋯ ⊕ A∥_p, where the latter summation has |n| summands.

Proof

Suppose \(f\colon A \to A^{\prime \prime }\) is a p-equipollence for some \(A^{\prime \prime } \subseteq A^{\prime }\) and \(g\colon B \to B^{\prime \prime }\) is a p-equipollence for some \(B^{\prime \prime } \subseteq B^{\prime }\). Then f ⊕ g, defined by

is a p-equipollence \(A \oplus B \to A^{\prime \prime } \oplus B^{\prime \prime } \subseteq A^{\prime } \oplus B^{\prime }\), with inverse f^− 1 ⊕ g^− 1. Similarly, f × g, defined by (f × g)(x,y) = (f(x),g(y)), is a p-equipollence \(A \times B \to A^{\prime \prime } \times B^{\prime \prime } \subseteq A^{\prime } \times B^{\prime }\) with inverse f^− 1 × g^− 1. This gives us the desired statements for ≼; since ≼ is only a pre-order, the statements for = do not immediately follow. However, if in the proof we take \(A^{\prime \prime } = A^{\prime }\) and \(B^{\prime \prime }=B^{\prime }\) then we get the desired statements for =.

Finally, note that A ⊕∅ = {0x : x ∈ A}, which is easily seen to have the same p-cardinality as A. Similarly, A ×{b} = {(a,b) : a ∈ A} is again easily seen have the same p-cardinality as A.

We leave the further properties as exercises for the reader. □

Remark 4.31

Note that the arithmetic operations and comparisons are also well-defined on the ≡-equivalence classes of p-cardinals (where ∥A∥_p ≡∥B∥_p if ∥A∥_p ≼∥B∥_p and ∥B∥_p ≼∥A∥_p), in which case the result is a partially ordered semi-ring, not just pre-ordered.

Observation 4.32

\(\|{\Sigma }^{\ast }\|_{p} = \|{\Sigma }^{\ast }\|_{p} + \|{\Sigma }^{\ast }\|_{p}\) and \(\|{\Sigma }^{\ast }\|_{p} = \|{\Sigma }^{\ast }\|_{p} \times \|{\Sigma }^{\ast }\|_{p}\).

Proof

Let n_x denote the natural number associated to x (see Preliminaries), and let σ_n denote the string associated to the natural number n. The bijection Σ^∗ →Σ^∗⊕Σ^∗ is given by

with inverse

For the direct product, we use any of the standard bijections Σ^∗ →Σ^∗×Σ^∗ (for example, using the bijections n,σ above to translate to \(\mathbb {N}\) and using the standard bijections \(\mathbb {N} \to \mathbb {N} \times \mathbb {N}\)). □

Corollary 4.33

If A is p-countable, then

and if these hold, then A≅^pA ×Σ^∗ (i. e., A is a p-cylinder).

Open Question 4.34

What can be said if merely \(\|A\|_{p} = \|A \times {\Sigma }^{\ast }\|_{p}\) and \(\|\overline {A}\|_{p} = \|\overline {A} \times {\Sigma }^{\ast }\|_{p}\)?

Proof

Suppose A is p-countable. The forward direction follows from the fact that p-isomorphism preserves p-countability. The backward direction follows from Corollary 4.19 using A = B.

For the final statement, suppose that both \(A,\overline {A}\) are p-countable. The idea of the proof is similar to that of Goldsmith, Kunen, and Hemaspaandra [27] and Corollary 4.19. Since \(\|A\|_{p} = \|{\Sigma }^{\ast }\|_{p}\) and \(\|{\Sigma }^{\ast }\|_{p} = \|{\Sigma }^{\ast }\|_{p} \times \|{\Sigma }^{\ast }\|_{p}\), we may replace the LHS and one of the ones on the RHS with A to get \(\|A\|_{p} = \|A\|_{p} \times \|{\Sigma }^{\ast }\|_{p} = \|A \times {\Sigma }^{\ast }\|_{p}\). Similarly for \(\overline {A}\). Now let f : A → A ×Σ^∗ and \(g\colon \overline {A} \to \overline {A} \times {\Sigma }^{\ast }\) be p-equipollences. Then the function

is a p-computable bijection Σ^∗→Σ^∗×Σ^∗, since A ∈P. To see that it is a bijection, note that \(\overline {A \times {\Sigma }^{\ast }} = \overline {A} \times {\Sigma }^{\ast }\). The inverse of h is given similarly by the p-computable bijection

Thus A≅A ×Σ^∗, so A is a cylinder. □

We note that the set of all p-cardinalities is uncountably infinite: there are uncountably many subsets of Σ^∗, and each p-cardinality class has countably many representatives, since there are only countably many Turing machines (even ones that are only partial) to compute p-equipollences. However, even in interesting countable sets of p-cardinalities, we believe:

Conjecture 4.35

For any standard complexity class \(\mathcal {C} \supseteq \mathsf {P}\) (such as P,NP, PSPACE,EXP, etc.), the semiring of p-cardinalities of languages in \(\mathcal {C}\) is not finitely generated. The same for the semiring of equivalence class of p-cardinalities (see Remark 4.31).

For ordinary cardinals, ℵ₀ is the smallest infinite cardinal, and every infinite cardinal \(\mathfrak {c}\) satisfies \(\mathfrak {c} + \aleph _{0} = \mathfrak {c}\). However, for p-cardinals this is no longer the case:

Proposition 4.36

If A is P-immune, then \(\|A\|_{p} \not \succeq \|A\|_{p} + \|{\Sigma }^{\ast }\|_{p}\).

Proof

Suppose \(\|A\|_{p} + \|{\Sigma }^{\ast }\|_{p} \preceq \|A\|_{p}\). Since the left-hand side is equal to ∥A ⊕Σ^∗∥_p, we have a p-equipollence f from A ⊕Σ^∗ to a subset \(A^{\prime } \subseteq A\). Then the restriction of f to 1Σ^∗ gives a p-equipollence to a subset \(A^{\prime \prime } \subseteq A^{\prime } \subseteq A\). Thus \(A^{\prime \prime }\) is p-countable, thus by Proposition 4.2 is in P. So A contains an infinite P subset, contradicting its P-immunity. □

Proposition 4.37 (Non-cancellation of addition, Nerode & Remmel [50, Theorem 7])

There exist languages A,B,C with ∥A ⊕ B∥_p = ∥A ⊕ C∥_p but ∥B∥_p≠∥C∥_p.

Nerode & Remmel showed the result for unary languages, and using slightly different definitions, but their same construction works with our definitions.

Nerode & Remmel [50, Theorem 10] also showed that one does get cancellation of multiplication by finite sets of unary strings. Their argument used a back-and-forth construction that required them to compute their function on all predecessors of a string. Because they were using unary languages, there were only linearly many such predecessors and the entire argument could be carried out in polynomial time. When we attempt to do the same in our setting with, say, length-lexicographic ordering, a string has exponentially many predecessors (exponential in its length), so the same strategy doesn’t work. It is possible that such a strategy could work with a p-well-founded ordering (see Definition 6.1) in which immediate predecessors were computable in FP, but we have not been able to get this to work, so we leave it as a question:

Open Question 4.38

(Division by finite p-cardinals). Is it the case that for any finite non-empty language n and for any languages A,B, ∥n × A∥_p = ∥n × B∥_p implies ∥A∥_p = ∥B∥_p?

4.5 Polynomial-Time Axioms of Choice based on P-Cardinality

Classical AC 4 (See [53, CN6 and CN7, pp. 52–53]) For any cardinals m < n and p < q, m + p < n + q and mp < nq.

Compare to Proposition 4.30.Classical AC 5 (Tarski’s Theorem [65], see [53, CN 3, p. 52]) For every infinite set A, there is a bijection between A and A × A.Polynomial-Time AC (PAC) 4 For every infinite language L ∈P, ∥L∥_p = ∥L × L∥_p.Classical AC 6 (Law of Trichotomy [53, T, p. 9]) For all sets A,B, either A is in bijection with a subset of B or B is in bijection with a subset of A.

A straightforward polynomial-time version of this is false by density considerations:

Proposition 4.39

There are two languages in P whose p-cardinalities are not comparable.

Proof

Let tow(0) = 1 and tow(n + 1) = 2^tow(n) be the tower function. A₀ will consists of all strings x of length tow(2k) ≤|x| < tow(2k + 1) for all k ≥ 0, and A₁ will consist of all strings of length tow(2k + 1) ≤|x| < tow(2k + 2) for all k ≥ 0. Clearly both A₀,A₁ are in P. The idea is that their densities fluctuate between Θ(n) and 2^Θ(n) infinitely often, but at opposite times. Let us verify this.

For lengths in the range \([\frac {1}{2}tow(2k+2), tow(2k+2))\), all the strings in A₀ have length < tow(2k + 1), so there are at most \(2^{tow(2k+1)+1}-1 \sim tow(2k+2)\) of them. So in these ranges we have \(c_{A_{0}}(n) \in [n/2, n]\). In this same range, all strings are present in A₁, so we have \(c_{A_{1}}(n) \geq 2^{n}\), which is nearly maximal. For lengths in the range \([\frac {1}{2}tow(2k+1), tow(2k+1))\) the situation is reversed.

For the sake of contradiction, suppose \(B \subseteq A_{0}\) has ∥B∥_p = ∥A₁∥_p. Since A₀ is empty at lengths in the ranges [tow(2k + 1),tow(2k + 2)), so is B, and thus B has density at most O(n) for n in the range \([\frac {1}{2}tow(2k+2), tow(2k+2)]\). But A₁ has density at least 2ⁿ in this range, so the two are not polynomially related for arbitrarily large stretches of lengths, a contradiction. The analogous argument swapping the roles of A₀ and A₁ and using the ranges [tow(2k),tow(2k + 1)) instead rules out a subset of A₁ having the same p-cardinality as A₀. Thus ∥A₀∥_p and ∥A₁∥_p are incomparable. □

We thus propose a polynomial-time form of AC with density in its assumption.Polynomial-Time AC (PAC) 5 For all sets A,B ∈P of polynomially related densities, either ∥A∥_p ≼∥B∥_p or ∥B∥_p ≼∥A∥_p.

If we remove the restriction that both languages are in P, we believe the statement becomes false.Classical AC 7 (Law of Trichotomy [53, T’, p. 10]) For every two non-empty sets, there is a surjective mapping of one onto the other.Polynomial-Time AC (PAC) 6 For every two non-empty languages A,B with c_A(n) ≤ c_B(poly(n)), there is an honest surjective polynomial-time function A → B.

Classically, T implies T’. For the p-analogues, such an implication seems tantamount to Hypothesis Q, though formalizing this has proved tricky. We do have, however:Classical AC 8 Every surjective function has a right inverse.Polynomial-Time AC (PAC) 7 Every polynomial-time computable, honest, surjective function has a polynomial-time inverse. This is an exact restatement of Hypothesis Q.Classical AC 9 (See [53, Section 6, pp. 52–53]) Cardinal forms of the axiom of choice. Throughout, m,n,p,q denote infinite cardinals. When not quantified, universal quantification is assumed, e. g., the first condition is more precisely “For all infinite cardinals m,n, m ⋅ n = m + n.”

1. 1.

   m ⋅ n = m + n.

2. 2.

   There is a cardinal n such that m = n².

3. 3.

   If m² = n² then m = n.

4. 4.

   If m + p < n + p then m < n.

5. 5.

   If mp < np then m < n.

6. 6.

   Every cardinal has an immediate successor (m < n and if m < p then n ≤ p).

7. 7.

   If n < p and there is no cardinal between n and p (p “covers” n) then either mn = mp or mp covers mn. (If p is an immediate successor of n then p covers n. The converse is equivalent to AC.)

8. 8.

   If m < n then there is a p such that n = mp.

9. 9.

   If m < n then n/m exists (as in the previous point) and is unique.

10. 10.

    If m < n then n/m = n.

11. 11.

    If m + p = m + q then either p = q, or p ≤ m and q ≤ m.

12. 12.

    If m + m < m + n then m < n. (The converse is independent of AC.)

13. 13.

    If m < n then n − m exists, that is, there exist one and only one p such that n = m + p. (Existence alone is independent of AC.)

14. 14.

    If m < n then n − m = n.

15. 15.

    If p < n,q < n then p + q≠n.

16. 16.

    If p < n,q < n then pq≠n.

17. 17.

    Either mn = m or mn = n.

Many of the arguments that these are equivalent to one another and to the standard AC rely on the notion of the immediate successor of a cardinal (e. g., [53]). We show that such a construction is unlikely to exist for (infinite) p-cardinalities, by a Ladner-type diagonalization result.

Before coming to the result, our proof currently uses one additional assumption, essentially because of the issue raised by Theorem 4.28.

Definition 4.40 (Much smaller p-cardinality)

We say that ∥A∥_p is much smaller than ∥B∥_p, denoted ∥A∥_p ≪∥B∥_p, if ∥A∥_p ≺∥B∥_p and for any subset \(B^{\prime } \subseteq B\) such that \(\|A\|_{p} = \|B^{\prime }\|_{p}\), the difference \(B \backslash B^{\prime }\) is infinite.

The next proposition shows that ≪ is in fact a well-defined relationship on p-cardinality classes.

Proposition 4.41

If \(\|A\|_{p} = \|\hat {A}\|_{p}\) and \(\|B\|_{p} = \|\hat {B}\|_{p}\), then ∥A∥_p ≪∥B∥_p iff \(\|\hat {A}\|_{p} \ll \|\hat {B}\|_{p}\).

Proof

Suppose ∥A∥_p ≪∥B∥_p, we show that \(\|\hat {A}\|_{p} \ll \|\hat {B}\|_{p}\), with the reverse implication following by symmetry. If \(\|A\|_{p} = \|\hat {A}\|_{p}\), then for any subset \(B^{\prime } \subseteq B\), we have \(\|A\|_{p} = \|B^{\prime }\|_{p}\) iff \(\|\hat {A}\|_{p} = \|B^{\prime }\|_{p}\), so we have \(\|\hat {A}\|_{p} \ll \|B\|_{p}\). Now suppose \(\|B\|_{p} = \|\hat {B}\|_{p}\), and let \(\hat {B}^{\prime } \subseteq \hat {B}\) have the same p-cardinality as \(\hat {A}\). Let \(f\colon \hat {B} \to B\) be a p-equipollence, and define \(B^{\prime } = f(\hat {B}^{\prime })\). Then we have \(\|A\|_{p} = \|B^{\prime }\|_{p}\), and by assumption \(B \backslash B^{\prime }\) is infinite. But then \(f^{-1}(B \backslash B^{\prime }) = \hat {B} \backslash \hat {B}^{\prime }\) is infinite as well, since f^− 1 is injective on B.□

Obviously finite sets are much smaller than ∥A∥_p for any infinite A, but we also have less trivial examples.

Proposition 4.42

1. If A ⊂ B and \(A {\not \equiv _{m}^{p}} B\), then ∥A∥_p ≪∥B∥_p.

2. If \(A {\not \equiv _{m}^{p}} B \neq {\Sigma }^{\ast }\), then \(\|A\|_{p} \ll \|{\Sigma }^{\ast } \oplus B\|_{p}\).

Proof

1. If A ⊂ B then ∥A∥_p ≼∥B∥_p. If \(A {\not \equiv _{m}^{p}} B\), suppose \(B^{\prime } \subset B\) has the same p-cardinality as A. Since \(A,B^{\prime }\) are both proper subsets of B, neither can be Σ^∗, so Proposition 4.2 implies \(A {\equiv _{m}^{p}} B^{\prime }\). But since \(B {\not \equiv _{m}^{p}} A\), we must have \(B {\not \equiv _{m}^{p}} B^{\prime }\), and thus \(B \backslash B^{\prime }\) must be infinite.

2. Define \(\hat {B} = {\Sigma }^{\ast } \oplus B\) and \(\hat {A} = 0A\). As \(\hat {B} {\equiv _{m}^{p}} B\) and \(\hat {A} {\equiv _{m}^{p}} A\), we still have \(\hat {A} {\not \equiv _{m}^{p}} \hat {B}\), and now we have \(\hat {A} \subseteq \hat {B}\). Part 1 implies \(\|\hat {A}\|_{p} \ll \|\hat {B}\|_{p}\), and Proposition 4.41 then gives \(\|A\|_{p} \ll \|\hat {B}\|_{p}\) as well. □

Warning! “Much smaller” is, unfortunately, not transitive. Suppose \(A \not \equiv _{m}^ p B \neq {\Sigma }^{\ast }\). Applying part 2 of the preceding proposition a few times, we get \(\|A\|_{p} \ll \|{\Sigma }^{\ast } \oplus B\|_{p} \ll \|{\Sigma }^{\ast } \oplus A\|_{p} \ll \|{\Sigma }^{\ast } \oplus {\Sigma }^{\ast } \oplus B\|_{p} = \|{\Sigma }^{\ast } \oplus B\|_{p}\). But obviously ∥Σ^∗⊕ B∥_p is equal to itself, so it cannot be much less than itself. At first sight this seems to point to some error, but it is actually a natural consequence of the fact that p-cardinality mixes subsets and many-one degrees, while the poset of subset inclusion is not compatible with the poset of many-one reductions. Viz., there are sequences of languages L₁ ⊂ L₂ ⊂ L₃ with L₂ NP-complete but L₁,L₃ ∈P, e. g., \(0L_{1} \subseteq {\Sigma }^{\ast } \oplus SAT \subseteq {\Sigma }^{\ast }\) for any L₁ ∈P.

In contrast, the relation “≼ but not ≪” (“smaller, but not much smaller”) is transitive. For if A is p-equipollent to a cofinite subset of B, and B is p-equipollent to a cofinite subset of C, then composing the two gives a p-equipollence between A and a cofinite subset of C. We will use this fact (in contrapositive form) several times in the following proof.

Theorem 4.43

Let A,B be languages with ∥A∥_p ≪∥B∥_p. Then there exists an infinite language C with ∥A∥_p ≺∥C∥_p ≺∥B∥_p.

Because of Theorem 4.28, the assumption here is not equivalent to ∥A∥_p ≺∥B∥_p; we will see in Corollary 4.48 below that the same set constructed in Theorem 4.28 can be used to give an example of sets A,B with ∥A∥_p ≺∥B∥_p but with no p-cardinal strictly in between the two. In the vein of Question 4.29, it is interesting to ask for conditions under which Theorem 4.43 would hold with the weaker assumption ∥A∥_p ≺∥B∥_p, and/or with the stronger conclusion ∥A∥_p ≪∥C∥_p ≪∥B∥_p. As is, we necessarily have that at least one of ∥A∥_p ≺∥C∥_p and ∥C∥_p ≺∥B∥_p can be turned into ≪, for otherwise we could not have ∥A∥_p ≪∥B∥_p, but our construction does not control which one.

Proof

By assumption, there is a p-computable, p-invertible bijection from A to a co-infinite subset of B, but not vice versa. (Note that B cannot be finite.) To simplify notation in what follows, let us identify A with its image under this bijection, so that, without loss of generality, we may assume that in fact \(A \subsetneq B\) and B∖A is infinite. We will build C such that \(A \subsetneq C \subsetneq B\) and ∥A∥_p ≺∥C∥_p ≺∥B∥_p. Since \(A \subseteq C \subseteq B\), we have ∥A∥_p ≼∥C∥_p ≼∥B∥_p. So it suffices to build C in between A and B avoiding p-computable, p-invertible bijections C → A and B → C.

Let \(\hat {M}_1, \hat {M}_2, \hat {M}_3, \dotsc \) be an enumeration of Turing machine transducers, and for all c let M_c be the machine gotten from \(\hat {M}_c\) by restricting \(\hat {M}_c\) to run on each input of length n for no more than cn^c + c steps. If \(\hat {M}_c(x)\) has not made an output after c|x|^c + c steps, then M_c(x) rejects x (i. e., it makes no output). It is clear that \(M_1, M_2, \dotsc \) is thus an enumeration of all partial polynomial-time Turing machine transducers.

Construction. We build C in stages \(s=0,1,2,\dotsc \). We also build a set E of strings to be excluded from C. For each \(s \in \mathbb {N}\), C_s and E_s will be the parts of C and E, respectively, enumerated at the end of stage s. The construction will guarantee that, for each s, C_s ∩ E_s = ∅, \(A \subseteq C_s \subseteq C_{s+1} \subseteq B\), C_s will be finitely different from A, \(E_s \subseteq E_{s+1} \subseteq B\), and E_s will be finite.

We will have two sets of requirements to satisfy below; when s ≡ 0 (mod 3), we will add to C_s to ensure that C is infinite. The stages s + 1 where s ≡ 1 (mod 3) (resp. 2 (mod 3)) will ensure the first (resp., second) set of requirements are satisfied at this stage. We break the construction into numbered cases for reference in the verification below.

Stage s = 0. Set C₀ = A and E₀ = ∅.

Stage s + 1, where s ≡ 0 (mod 3). Let y be the least element of B∖(C_s ∪ E_s) (any element will do), and set C_s+ 1 := C_s ∪{y} and E_s+ 1 := E_s. (Such a y must exist since B∖A is infinite, C_s is finitely different from A, and E_s is finite.)

Stage s + 1, where s = 3〈α,β〉 + 1. (Here we use 〈∙,∙〉 to denote a bijection \(\mathbb {N} \times \mathbb {N} \to \mathbb {N}\).)

1. Case 1:

   M_α|_A: A → M_α(A) is not a p-equipollence, or \(M_{\alpha }(A) \not \subseteq B\), or M_β is not its inverse p-equipollence M_α(A) → A. In this case, set C_s+ 1 := C_s and E_s+ 1 := E_s, and continue to the next stage (s + 2).

2. Case 2:

   Otherwise. Note that in this case B∖M_α(A) must be infinite, since ∥A∥_p = ∥M_α(A)∥_p, but ∥A∥_p ≪∥B∥_p. Let Y = B∖E_s; since E_s is finite, Y is cofinite in B. Since ∥A∥_p ≪∥B∥_p by assumption, but Y is cofinite in B, ∥A∥_p cannot be equal to ∥Y ∥_p.

   1. Subcase 2.1:

      \(Y \not \subseteq \text {dom}(M_{\beta })\). In this subcase, let y be the least element of Y ∖dom(M_β) (any element will do), set C_s+ 1 := C_s ∪{y}, E_s+ 1 := E_s, and go to the next stage.

   2. Subcase 2.2:

      Not in the previous subcase, and M_β is not injective on Y. In this subcase, let y₁,y₂ ∈ Y be the least two distinct elements that M_β maps to the same place (any two will do). Set C_s+ 1 := C_s ∪{y₁,y₂} and E_s+ 1 := E_s and continue to the next stage.

   3. Subcase 2.3:

      Not in the previous subcases, and \(M_{\beta }(Y) \not \subseteq A\). In this subcase, let y be the least element of Y such that M_β(y)∉A (any will do), set C_s+ 1 := C_s ∪{y}, E_s+ 1 := E_s, and go to the next stage.

   4. Subcase 2.4:

      Not in the previous subcases. In this subcase, there must exist y ∈ Y such that M_α(M_β(y))≠y; for at this point we have that M_β|_Y is an injective function from Y into A, so if M_α were its inverse we would have ∥A∥_p = ∥Y ∥_p (for we already know that (M_β ∘ M_α)|_A = id_A), which we showed above was impossible. Let y be the least such (any such will do), set C_s+ 1 := C_s ∪{y}, E_s+ 1 := E_s, and go to the next stage.

Stage s + 1 where s = 3〈α,β〉 + 2.

1. Case 1:

   In any of the following subcases, set C_s+ 1 := C_s, E_s+ 1 := E_s, and go to the next stage.

   1. Subcase 1.1:

      \(M_{\alpha }(C_s) \not \subseteq B\).

   2. Subcase 1.2:

      It is not the case that \(M_{\alpha }|_{C_s} \colon C_s \to M_{\alpha }(C_s)\) is a p-equipollence with inverse M_β.

   3. Subcase 1.3:

      X := B∖(M_α(C_s) ∪ E_s) is not contained in dom(M_β).

   4. Subcase 1.4:

      Not in the above subcases, and \(M_{\beta }(X) \subseteq C_s\).

2. Case 2:

   Not in any of the above subcases. In this case, let x be the least element of X such that M_β(x)∉C_s (any such will do), set E_s+ 1 := E_s ∪{x}, C_s+ 1 := C_s, and go to the next stage. (Note that such an x must exist, for E_s is finite, and M_α is a p-equipollence from a set that is finitely different from A to a subset of B, but ∥A∥_p ≪∥B∥_p.)

This completes the description of stage s + 1, and thus of the construction.

Requirements. Below, we will show that, in addition to ensuring C is infinite, the construction satisfies two sets of requirements, and that these requirements imply the desired property of C. For the purposes of stating these requirements, define \(E = \bigcup _s E_s = \lim _{s \to \infty } E_s\). The requirements for (α,β) are as follows:

R1_α,β: At least one of the following holds (a) \(A \not \subseteq \text {dom}(M_{\alpha })\) or M_α is not injective on A, or (b) \(C \not \subseteq \text {dom}(M_{\beta })\) or M_β is not injective on C, or (c) M_α(A) is not contained in B (sic!), or (d) M_β(C) is not contained in A, or (e) there is a ∈ A with M_β(M_α(a))≠a or there is c ∈ C with M_α(M_β(c))≠c.

R2_α,β: At least one of the following holds (a) \(C \not \subseteq \text {dom}(M_{\alpha })\) or M_α is not injective on C, or (b) \(B \not \subseteq \text {dom}(M_{\beta })\) or M_β is not injective on B, or (c) M_α(C) is not contained in B, or (d) M_β(B) ∩ E is nonempty, or (e) there is c ∈ C with M_β(M_α(c))≠c or there is b ∈ B with M_α(M_β(b))≠b.

The requirements suffice. First let us see that the requirements, plus C being infinite, suffice for the theorem. The requirement R1_α,β implies that M_α is not a p-equipollence A → C with inverse M_β, and R2_α,β implies that M_α is not a p-equipollence C → B with inverse M_β (note that R2_α,β(d) ensures \(M_{\beta }(B) \not \subseteq C\), since E is disjoint from C). Since (α,β) run over a complete list of polynomial-time Turing machines, these requirements will establish that ∥A∥_p ≺∥C∥_p ≺∥B∥_p.

The stages with s + 1 ≡ 0 (mod 3) add elements to C infinitely often, ensuring that C is infinite even if A was finite.

Verification of the requirements. We begin by noting that this is an “injury-free” argument, in the sense that once a requirement is satisfied, it never becomes unsatisfied (“is never injured”). This is because each requirement is a \(({\Sigma }^0_1)^{A \oplus B}\) statement, that is, it is of the form \((\exists \vec {x})[P(\vec {x})]\) where P is a predicate that is computable with an oracle for A and B. Thus, it suffices to show that at the end of stage s + 1 = 3〈α,β〉 + b, if C^′,E^′ are any two sets satisyfing \(C_s \subseteq C' \subseteq B\), \(E_s \subseteq E' \subseteq B \backslash C'\), then Rb_α,β is satisfied with C^′ (resp., E^′) in place of C (resp., E).

Remark 4.44

To ensure this \(({\Sigma }^0_1)^{A \oplus B}\) property, we note that R1_α,β is slightly stronger than is needed to ensure M_α is not a p-equipollence A → C with inverse M_β, and similarly R2_α,β is slightly stronger than is needed to ensure M_α is not a p-equipollence C → B with inverse M_β. In particular, if R1_α,β(c) were merely “M_α(A)≠C” and R1_α,β(d) were “M_β(C)≠A,” it would suffice to avoid p-equipollences, but then these statements would not be \({\Sigma }^0_1\) in A ⊕ B, for it would then be possible that later additions to C would violate such a condition. Similarly, if R2_α,β(c) were merely “M_α(C)≠B” and R2_α,β(d) were merely “M_β(B)≠C,” it would suffice to avoid p-equipollences, but again, would not so clearly avoid injuries from future additions to C.

Stage s + 1 with s = 3〈α,β〉 + 1 ensures R1_α,β is satisfied. We break the verification into cases according to the cases in the construction.

1. Case 1.

   If M_α|_A: A → M_α(A) is not a p-equipollence to a subset \(M_{\alpha }(A) \subseteq B\) with inverse M_β, then Case 1 of the construction tells us to move onto the next stage. We must thus show that in this case, without any further changes to C_s,E_s, it is already the case that R1 is satisfied.

   In this case, one of the following must hold:

   1. (A)

      \(A \not \subseteq \text {dom}(M_{\alpha })\) or M_α is not injective on A.

   2. (B)

      \(M_{\alpha }(A) \not \subseteq B\).

   3. (C)

      \(M_{\alpha }(A) \not \subseteq \text {dom}(M_{\beta })\)

   4. (D)

      M_β is not injective on M_α(A)

   5. (E)

      \(M_{\beta }(M_{\alpha }(A)) \not \subseteq B\)

   6. (F)

      M_α and M_β are not inverses on A, M_α(A), respectively. That is, there is some a ∈ A such that M_β(M_α(a))≠a or some b ∈ M_α(A) such that M_α(M_β(b))≠b. The latter is equivalent to the existence of an a ∈ A such that M_α(M_β(M_α(a)))≠M_α(a).

   Suppose (A) holds. (A) is the same as R1_α,β(a), so R1_α,β is satisfied.

   Suppose (B) holds. (B) is the same as R1_α,β(c).

   Suppose (C) holds. Then there is an a ∈ A such that M_α(a)∉dom(M_β) and thus M_β(M_α(a))≠a since the LHS is undefined, so R1_α,β(e) holds.

   Suppose (D) holds. Then there are distinct a₁,a₂ ∈ A such that M_β(M_α(a₁)) = M_β(M_α(a₂)). But then at least one of M_β(M_α(a_i)) = a_i for i = 1,2 must fail, so R1_α,β(e) holds.

   Suppose (E) holds. Since \(M_{\beta }(M_{\alpha }(A)) \not \subseteq B\), there is some a ∈ A such that \(M_{\beta }(M_{\alpha }(a)) \notin B \supseteq A\), so we must have M_β(M_α(a))≠a, so R1_α,β(e) holds.

   Suppose (F) holds. Then it must be the case that there is an a ∈ A such that M_β(M_α(a))≠a. For if not, then by the second part of (F) we get that there is an a such that

   $$ \begin{array}{@{}rcl@{}} M_{\alpha}(M_{\beta}(M_{\alpha}(a))) \neq M_{\alpha}(a). \end{array} $$

   But if M_β(M_α(a)) = a for all a ∈ A, then the displayed equation simplifies to M_α(a)≠M_α(a), which is absurd. Thus R1_α,β(e) is satisfied.

   Thus, case 1 ensures R1_α,β, as claimed.

2. Case 2.

   Suppose instead we are in case 2, in which M_α|_A: A → M_α(A) is a p-equipollence to a subset of B with inverse M_β. Following the notation in the construction, let Y = B∖E_s.

   1. Subcase 2.1.

      If the condition of subcase 2.1 is satisfied (\(Y \not \subseteq \text {dom}(M_{\beta })\)), then we add a y ∈ Y ∖dom(M_β) to C, thus satisfying R1_α,β(b).

   2. Subcase 2.2.

      In subcase 2.2, if the relevant condition is satisfied, we add to C distinct y₁,y₂ ∈ Y such that M_β(y₁) = M_β(y₂). This satisfies the second part of R1_α,β(b).

   3. Subcase 2.3.

      In subcase 2.3, if the relevant condition is satisfied, we add to C a y ∈ Y such that M_β(y)∉A, thus satisfying R1_α,β(d).

   4. Subcase 2.4.

      In subcase 2.4, if the relevant condition is satisfied, we add to C a y ∈ Y such that M_α(M_β(y))≠y, thus satisfying the second part of R1_α,β(e).

Since the cases and subcases exhaust all possibilities (case 2 is the “otherwise” of case 1, and subcase 2.4 captures all cases not in the previous cases by construction), this stage ensures that R1_α,β is satisfied.

Stage s + 1 = 3〈α,β〉 + 2 ensures R2_α,β. Following the notation in the construction, let X = B∖(M_α(C_s) ∪ E_s).

1. Case 1.

   We must show that in this case, without any further changes to C_s,E_s, it is already the case that R2 is satisfied.

   1. Subcase 1.1:

      \(M_{\alpha }(C_s) \not \subseteq B\). Thus we have that \(M_{\alpha }(C) \not \subseteq B\), which is precisely R2_α,β(c).

   2. Subcase 1.2:

      \(M_{\alpha }|_{C_s} \colon C_s \to M_{\alpha }(C_s)\) is not a p-equipollence with inverse M_β. In this case, one of R2_α,β(a), (b), or (e) must be satisfied (since together they are the definition of a p-equipollence), and thus R2_α,β is satisfied already.

   3. Subcase 1.3:

      \(X \not \subseteq \text {dom}(M_{\beta })\). Since \(X \subseteq B\) by definition, R2_α,β(b) is satisfied.

   4. Subcase 1.4:

      Not in the above subcases, and \(M_{\beta }(X) \subseteq C_s\). In this case, we claim that M_β cannot be injective on B. To see that M_β is not injective on B, first note that since we are not in subcase 1.2, we have that M_β is the p-equipollence M_α(C_s) → C_s that is inverse to \(M_{\alpha }|_{C_s}\). Thus M_β maps M_α(C_s) bijectively onto C_s. Now let x ∈ X, and let b = M_α(M_β(x)). Since \(M_{\beta }(X) \subseteq C_s\) by assumption, we have b ∈ M_α(C_s). But X is disjoint from M_α(C_s) by definition, so b≠x. But since M_β,M_α are inverses on M_α(C_s),C_s respectively, and \(M_{\beta }(X) \subseteq C_s\) by assumption, we have M_β(b) = M_β(M_α(M_β(x))) = (M_β∘M_α)(M_β(x)) = (id)(M_β(x)) = M_β(x). Thus M_β is not injective on B, satisfying the second part of R2_α,β(b).

2. Case 2.

   In this case, E_s gets extended to E_s+ 1 by adding some x ∈ X such that M_β(x)∉C_s. Since \(X \subseteq B\), this ensures that M_β(B) ∩ E is not empty, satisfying R2_α,β(d).

Since the cases and subcases exhaust all possibilities, at the end of this stage the requirements R2_α,β are satisfied.

Putting these all together, the construction indeed produces an infinite set C such that ∥A∥_p ≺∥C∥_p ≺∥B∥_p, completing the proof of the theorem. □

Remark 4.45

In addition to R1 and R2 being stronger than needed (see Remark 4.44), the reader may also wonder why R1 and R2 are not perfect analogues of one another. The answer is that we actually first wrote a proof with them being more symmetric, then pared them down to the only parts of the requirements we actually ended up needing.

Finally, we note that the argument is almost monotone in C. The only requirement that is not monotone in C is R2_α,β(d), and it was this requirement that forced us to keep track of the set E of excluded strings (R2_α,β(d) is monotone in E).

Given that ℵ₀ is the unique minimum infinite cardinal, it is natural to wonder whether minimal infinite p-cardinals exist. The following corollary answers this in the negative:

Corollary 4.46 (No minimal infinite p-cardinals)

For every infinite \(B \subseteq {\Sigma }^{\ast }\), there is an infinite set C such that ∥C∥_p ≺∥B∥_p.

Proof

Apply Theorem 4.43 with A = ∅. □

We suspect a modification of the above proof could be used to answer the following stronger question in the negative:

Open Question 4.47. Do there exist p-cardinals that are minimal(ly infinite) under ≡? That is, an infinite language \(B \subseteq {\Sigma }^{\ast }\) such that if ∥C∥_p ≺∥B∥_p, then either C is finite or ∥B∥_p ≼∥C∥_p?

We conclude this section by showing that the assumption ∥A∥_p ≪∥B∥_p in Theorem 4.43 cannot, in general, be replaced by ∥A∥_p ≺∥B∥_p, even for infinite languages (for finite languages this is clear, whenever |B| = |A| + 1), by the following corollary to Theorem 4.28:

Corollary 4.47 (Infinite p-cardinals can have immediate predecessors)

There exist infinite languages A,B with ∥A∥_p ≺∥B∥_p such that any language C with ∥A∥_p ≼∥C∥_p ≼∥B∥_p is p-equipollent to either A or B.

By Theorem 4.43, necessarily any such pair cannot have ∥A∥_p ≪∥B∥_p.

Proof

Let A be the set guaranteed by Theorem 4.28, let w∉A, and let B = A ∪{w}. Suppose C is such that ∥A∥_p ≼∥C∥_p ≼∥B∥_p, but C is not p-equipollent to B. We will show that C must be p-equipollent to A. Since ∥C∥_p ≼∥B∥_p by assumption, there is a p-equipollence \(f \colon C \to C^{\prime }\) to a proper subset \(C^{\prime } \subset B\). Since neither the conclusion nor the statement depends on the representative of ∥C∥_p chosen, without loss of generality let us replace C by \(C^{\prime }\).

Since B = A ∪{w} and \(C^{\prime } \subseteq B\), \(C^{\prime }\) is either a subset of A, or is \(A^{\prime } \cup \{w\}\) for a subset \(A^{\prime } \subseteq A\). But by assumption, there is a p-equipollence from A to a subset of \(C^{\prime }\). By Theorem 4.28(1), \(C^{\prime }\) cannot be a proper subset of A. If \(C^{\prime }=A\), then we are done.

So all that is left is to handle the case that \(C^{\prime } = A^{\prime } \cup \{w\}\) for some \(A^{\prime } \subseteq A\). If \(A^{\prime } = A\), then \(C^{\prime } = B\), contradicting our assumption that ∥C∥_p≠∥B∥_p. Thus \(A^{\prime }\) must be a proper subset of A. If \(|A \backslash A^{\prime }| \geq 2\), then let \(w_{1} \in A \backslash A^{\prime }\). Then we have \(\|C^{\prime }\|_{p} = \|A^{\prime } \cup \{w\}\|_{p} = \|A^{\prime } \cup \{w_{1}\}\|_{p}\). But \(A^{\prime } \cup \{w_{1}\}\) is a proper subset of A, contradicting Theorem 4.28(1). So \(|A \backslash A^{\prime }| \leq 2\), and since \(A^{\prime }\) is a proper subset of A, we must have \(|A \backslash A^{\prime }| = 1\). Thus \(|C^{\prime } \backslash A| - |A \backslash C^{\prime }| = |\{w\}| - |A \backslash A^{\prime }| = 1-1=0\), so by Theorem 4.28(2), \(\|C^{\prime }\|_{p} = \|A\|_{p}\). □

Here we consider statements that are implied by the Axiom of Choice over ZF, but that are not known to be equivalent to AC (or are known to be strictly weaker), because their polynomial-time analogues make interesting connections.Classical Result 1 Any union of countably many countable sets is countable.Polynomial-Time Analogue 1 If L is a P collection of languages L_x each of which is p-countable, then L is p-countable.

One might hope to build a p-equipollence L →Σ^∗ by using the individual p-equipollences \(L_{x} \to {\Sigma }^{\ast }\) together with the fact that \(\|{\Sigma }^{\ast }\|_{p} = \|{\Sigma }^{\ast } \times {\Sigma }^{\ast }\|_{p}\). However, one runs into the issue that if \(f_{x}\colon L_{x} \to {\Sigma }^{\ast }\) is a p-equipollence, there may not be a uniform polynomial upper bound on the runtimes of all the f_x. In the opposite direction, the fact that L itself is in P means there is a uniform polynomial upper bound on the times to decide each L_x, so perhaps there is still some hope that this is unconditionally true. We leave it as an open questionOpen Question 5.1 Prove or disprove the PTA1. Does one of the polynomial-time versions of AC imply PTA1?Classical Result 2 If A is infinite, there is an injection from \(\mathbb {N} \to A\).

A natural p-analogue of this fails:

Corollary 5.1

There is an infinite language L ∈P such that ∥Σ^∗∥_p≰∥L∥_p.

This is a corollary to the proof of Proposition 4.39.

Proof

Let L be one of the languages constructed in Proposition 4.39. ∥Σ^∗∥_p ≼ L would imply L is exponentially dense, but L is infinitely-often linearly sparse, so the result follows. □

Classical Result 3 (The Axiom of Uniformization) If R ⊂ X × Y where X and Y are Polish spaces, then there is a subset \(f \subseteq R\) that is a partial function f : X → Y and such that \(\text {dom}(f) = \left \{x \in X | \exists y \in Y (x,y) \in R\right \}\).Polynomial-Time Analogue 2 If X,Y ∈P and \(R \subseteq X \times Y\) is in P as well, then there is a refinement f of R such that f is a partial function that is polynomial-time computable and whose domain is exactly \(\text {dom}(f) = \left \{x \in X : \exists y \in Y (x,y) \in R\right \}\).

This is a restatement of \(\mathsf {NPMV}_{g} \subseteq _{c} \mathsf {PF}\), studied by Blass & Gurevich [6] about a decade before Selman introduced the NPMV notation [63]. Note that some of our polynomial-time versions of AC are about NPMV_t or NPMV_gt, but collapses of NPMV_t are generally not known to imply collapses of NPMV, in contrast to the classical, unbounded situation where AC implies the Axiom of Uniformization.

Beyond the many questions and conjectures already stated (Questions 1.2, 3.7, 4.29, 4.34, 4.38, 4.47, 4.51, questions around Theorem 4.25, Conjectures 4.9 and 4.35), here we raise a few more that we think would be interesting avenues of exploration.

Around the Isomorphism Conjecture. Are Joseph & Young’s creative sets [38], proposed as counterexamples to the Isomorphism Conjecture [5], p-equipollent to each other? To SAT? (See, e. g., the introduction of [42] for a survey of developments around this.) Recall that a language A is a cylinder if A≅^pA ×Σ^∗; this is equivalent to A being paddable, and cylinders play an important role more generally in investigations around the Isomorphism Conjecture [5]. One of the main theorems of Berman & Hartmanis [5] is that an NP-complete set is p-isomorphic to SAT iff it is a cylinder. Note that if A is a cylinder then \(\|A\|_{p} = \|A \times {\Sigma }^{\ast }\|_{p} \succeq \|{\Sigma }^{\ast }\|_{p}\). Note that A is a cylinder iff \(\overline {A}\) is. What can be said about the cardinalities of cylinders? If A and \(\overline {A}\) both have p-cardinalities equal to their product with Σ^∗, must A be cylinder-like in some way (cf. Question 4.34)?

Connections to other complexity notions. Can some of our open questions about p-cardinality or polynomial-time axioms of choice be resolved assuming μ_p(NP)≠ 0 [43]?

It seems there should be interesting connections to be had between p-cardinality and several of Selman’s other interests, such as p-selectivity [34, 48, 57,58,59], disjoint pairs [17, 22,23,24], and mitoticity [18,19,20].

Several versions of AC use well-orderings. In the context of studying self-reducibility, Meyer & Paterson introduced some definitions that could be useful for polynomial-time analogues of these versions of AC:

Definition 6.1 (Meyer & Paterson [46, Definition 4])

A partial order ≺ on Σ^∗ is polynomially well-founded if there is a polynomial p such that every finite ≺-decreasing chain has at most p(|x|) elements in it, where |x| is the maximal length of any element in the chain.

A language \(L \subseteq {\Sigma }^{\ast }\) is self-reducible if there is a polynomial-time oracle TM \(M^{\square }\) and an p-well-founded, length-related ordering ≺ such that L(M^L) = L and for any input x, M^L(x) only queries the oracle on strings that are strictly ≺ x.

Selman studied this notion of self-reducibility in (at least) [33, 59, 60].Classical AC 10 (See [53, WE1, p. 1]) Every set can be well-ordered.Polynomial-Time AC (PAC) 8 Every language in P admits a p-well-ordering computable in P.

More generally, aside from the use of well-orderings in relation to AC, an anonymous reviewer has suggested, and we agree, that it would be interesting to develop a theory of p-ordinals, similar to the development of p-cardinals here. We point out that this could either be in terms of total orders on Σ^∗ computable in FP, or in terms of total orders on subsets \(A \subseteq {\Sigma }^{\ast }\), where the order relation is computable in PF on A × A. It is unclear to us at this point which would fit more naturally with our development of p-cardinals here.

Recall that a set is said to be Dedekind finite iff it does not have a bijection onto any of its proper subsets. In classical set theory, “finite” and “Dedekind finite” are equivalent, but in other settings this need not be the case. Dekker [10] and Dekker–Myhill [11] were originating works on isols as models of Dedekind-finite sets.

Definition 6.2 (Dedekind p-finite)

A language \(L \subseteq {\Sigma }^{\ast }\) is Dedekind p-finite if it does not have the same p-cardinality as any of its proper subsets.

The set constructed in Theorem 4.28 is an infinite set that is Dedekind p-finite. How do Dedekind p-finite sets relate to the p-finite sets of Nerode & Remmel [51, Definition 6]? What can Dedekind p-finite sets tell us about p-cardinality more generally? Do they have a nice theory of arithmetic? Can they be used to realize Downey’s suggestion [12] (see the quote in Section 1)?

Lastly, one could also consider finite axioms of choice, in which one starts with a collection consisting of finite sets—here one may think correspondingly of a language L, where a single element of L represents a binary set by considering the binary encoding of x as the characteristic function of a finite subset of \(\mathbb {N}\). Finite AC are discussed in [37, Section 2.2] and [66].