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).
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 superscriptp 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.
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:
We can use Proposition 4.2 to show that ≼ is not a partial order:
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.
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).
Note that there are no such examples where A,B are finite, for in that case ∥A∥p = ∥B∥p implies A≅pB.
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:
We next observe that Berman & Hartmanis’s Cantor–Bernstein-like proof extends to 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 Gp,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 Gp,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
CA be the vertices that are part of a chain with source in 0
A, and
CB be the vertices in that are part of a chain with source in 1
B. We define
$$ \begin{array}{@{}rcl@{}} \phi(x) = \left\{\begin{array}{ll} p(x) & \text{ if } 0x \in 0A \cap C_{A} \\ q^{-1}(x) & \text{ if } 0x \in 0A \cap C_{B} \end{array}\right. \qquad \psi(y) = \left\{\begin{array}{ll} p^{-1}(y) & \text{ if } 1y \in 1B \cap C_{A} \\ q(y) & \text{ if } 1y \in 1B \cap C_{B} \end{array}\right. \end{array} $$
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 ∈ CA or 0x ∈ CB. 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 CA or CB the vertex 0x is in. Since p− 1 and q− 1 are length-decreasing, this takes no more than time polynomial in |x|. □
4.3 P-Countability: Density, Rankability, Enumerabililty, and Compressibility
It is natural to consider Σ∗ to be the p-cardinality analogue of ℵ0, the cardinality of \(\mathbb {N}\), so here we examine sets that have the same p-cardinality as Σ∗.
Before we get to interesting connections, we ensure that our exploration is not dependent on alphabet:
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:
Note that in Selman’s definition, f need not be injective.
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).
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:
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.
Several results and techniques of Goldsmith, Hemachandra, and Kunen thus have immediate implications for p-countable sets; we record a particularly interesting one here.
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 Σ
∗:
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 rkL,≺ is in FP (resp., in PF on inputs in L).
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.
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
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.
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.
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
$$ \begin{array}{@{}rcl@{}} \sigma(x) = \sigma(x-1) + B(x) - A(x) \end{array} $$
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 z1 ≤lexz2 ≤lex⋯ ≤lexzs+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 zi 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 rkB(x) = rkA(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 j1 < j2 < ⋯ < jt. 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 jk 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:
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 ℓ2 here).
(1) Suppose \(f \colon A \to A^{\prime }\) is a p-equipollence to a proper subset \(A^{\prime } \subsetneq A\). Let n0 be such that for all n ≥ n0, 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 n0 to a string of length > n0, 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 ≥ n0, 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 ≤ n0 to themselves, any x ∈ A of length ≥ n0 has nowhere to go but itself. Thus on strings of length ≥ n0, 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 n0 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 n0, \(B,B^{\prime }\) agree with A, so they have the same \(\ell ^{\log \ell }\) gap between their elements. Thus, as above, there exists some n1 ≥ n0 such that neither f nor f− 1 can map any string of length ≤ n1 to a string of length > n1. 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 n1—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 ≤ n0, 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 > n0, 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 n1. 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. □
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.
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:
For ordinary cardinals, ℵ0 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:
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:
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:
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
cA(
n) ≤
cB(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.”
2.
There is a cardinal n such that m = n2.
4.
If m + p < n + p then m < n.
6.
Every cardinal has an immediate successor (m < n and if m < p then n ≤ p).
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.
If m < n then there is a p such that n = mp.
9.
If m < n then n/m exists (as in the previous point) and is unique.
11.
If m + p = m + q then either p = q, or p ≤ m and q ≤ m.
12.
If m + m < m + n then m < n. (The converse is independent of AC.)
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.)
15.
If p < n,q < n then p + q≠n.
16.
If p < n,q < n then pq≠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.
The next proposition shows that ≪ is in fact a well-defined relationship on p-cardinality classes.
Obviously finite sets are much smaller than ∥A∥p for any infinite A, but we also have less trivial examples.
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 L1 ⊂ L2 ⊂ L3 with L2 NP-complete but L1,L3 ∈P, e. g., \(0L_{1} \subseteq {\Sigma }^{\ast } \oplus SAT \subseteq {\Sigma }^{\ast }\) for any L1 ∈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.
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 Mc 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 cnc + c steps. If \(\hat {M}_c(x)\) has not made an output after c|x|c + c steps, then Mc(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}\), Cs and Es will be the parts of C and E, respectively, enumerated at the end of stage s. The construction will guarantee that, for each s, Cs ∩ Es = ∅, \(A \subseteq C_s \subseteq C_{s+1} \subseteq B\), Cs will be finitely different from A, \(E_s \subseteq E_{s+1} \subseteq B\), and Es will be finite.
We will have two sets of requirements to satisfy below; when s ≡ 0 (mod 3), we will add to Cs 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 C0 = A and E0 = ∅.
Stage s + 1, where s ≡ 0 (mod 3). Let y be the least element of B∖(Cs ∪ Es) (any element will do), and set Cs+ 1 := Cs ∪{y} and Es+ 1 := Es. (Such a y must exist since B∖A is infinite, Cs is finitely different from A, and Es is finite.)
Stage s + 1, where
s = 3〈
α,
β〉 + 1. (Here we use 〈∙,∙〉 to denote a bijection
\(\mathbb {N} \times \mathbb {N} \to \mathbb {N}\).)
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 Cs+ 1 := Cs and Es+ 1 := Es, and continue to the next stage (s + 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∖
Es; since
Es 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.
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 Cs+ 1 := Cs ∪{y}, Es+ 1 := Es, and go to the next stage.
Subcase 2.2:
Not in the previous subcase, and Mβ is not injective on Y. In this subcase, let y1,y2 ∈ Y be the least two distinct elements that Mβ maps to the same place (any two will do). Set Cs+ 1 := Cs ∪{y1,y2} and Es+ 1 := Es and continue to the next stage.
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 Cs+ 1 := Cs ∪{y}, Es+ 1 := Es, and go to the next stage.
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 = idA), which we showed above was impossible. Let y be the least such (any such will do), set Cs+ 1 := Cs ∪{y}, Es+ 1 := Es, and go to the next stage.
Stage s + 1 where
s = 3〈
α,
β〉 + 2.
Case 1:
In any of the following subcases, set
Cs+ 1 :=
Cs,
Es+ 1 :=
Es, and go to the next stage.
Subcase 1.1:
\(M_{\alpha }(C_s) \not \subseteq B\).
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β.
Subcase 1.3:
X := B∖(Mα(Cs) ∪ Es) is not contained in dom(Mβ).
Subcase 1.4:
Not in the above subcases, and \(M_{\beta }(X) \subseteq C_s\).
Case 2:
Not in any of the above subcases. In this case, let x be the least element of X such that Mβ(x)∉Cs (any such will do), set Es+ 1 := Es ∪{x}, Cs+ 1 := Cs, and go to the next stage. (Note that such an x must exist, for Es 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).
Stage s + 1
with s = 3〈
α,
β〉 + 1
ensures R1α,β is satisfied. We break the verification into cases according to the cases in the construction.
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 Cs,Es, it is already the case that R1 is satisfied.
In this case, one of the following must hold:
(A)
\(A \not \subseteq \text {dom}(M_{\alpha })\) or Mα is not injective on A.
(B)
\(M_{\alpha }(A) \not \subseteq B\).
(C)
\(M_{\alpha }(A) \not \subseteq \text {dom}(M_{\beta })\)
(D)
Mβ is not injective on Mα(A)
(E)
\(M_{\beta }(M_{\alpha }(A)) \not \subseteq B\)
(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 a1,a2 ∈ A such that Mβ(Mα(a1)) = Mβ(Mα(a2)). But then at least one of Mβ(Mα(ai)) = ai 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.
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∖
Es.
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).
Subcase 2.2.
In subcase 2.2, if the relevant condition is satisfied, we add to C distinct y1,y2 ∈ Y such that Mβ(y1) = Mβ(y2). This satisfies the second part of R1α,β(b).
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).
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α(
Cs) ∪
Es).
Case 1.
We must show that in this case, without any further changes to
Cs,
Es, it is already the case that R2 is satisfied.
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).
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.
Subcase 1.3:
\(X \not \subseteq \text {dom}(M_{\beta })\). Since \(X \subseteq B\) by definition, R2α,β(b) is satisfied.
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α(Cs) → Cs that is inverse to \(M_{\alpha }|_{C_s}\). Thus Mβ maps Mα(Cs) bijectively onto Cs. Now let x ∈ X, and let b = Mα(Mβ(x)). Since \(M_{\beta }(X) \subseteq C_s\) by assumption, we have b ∈ Mα(Cs). But X is disjoint from Mα(Cs) by definition, so b≠x. But since Mβ,Mα are inverses on Mα(Cs),Cs 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).
Case 2.
In this case, Es gets extended to Es+ 1 by adding some x ∈ X such that Mβ(x)∉Cs. 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. □
Given that ℵ0 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:
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:
By Theorem 4.43, necessarily any such pair cannot have ∥A∥p ≪∥B∥p.