Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In ZFC, a good way of ordering sets by cardinality is by leveraging the notion of an injection. We define: $$X \lesssim Y \leftrightarrow \mbox{ there exists an injection } X \rightarrow Y.$$

Alternatively, we can leverage the notion of a partial surjection, by which I mean a partial function that hits every point of its codomain at least once.

$$Y \succsim X \leftrightarrow \mbox{ there exists a partial surjection } Y \rightarrow X.$$

Now in ZFC, these approaches are equivalent, in the sense that $$X \lesssim Y \iff Y \succsim X.$$

But if we just consider ZF (that is, we drop choice) then the equivalence breaks down. However, we've still got the forward implication, because the converse of an injection is always a partial surjection.

A specific question. Define that two sets are weakly equipotent iff $X \succsim Y$ and $Y \succsim X$. Question: does weak equipotence imply genuine equipotence? I'm guessing "no."

A general question: In broad terms, how would the structure of the cardinal numbers in ZF be altered by adopting $\succsim$ rather than $\lesssim$ as the fundamental order relation, and taking equality of cardinal numbers to correspond to weak equipotence of sets? I'm guessing this would hide a lot of the (usually very complicated) structure of the cardinal numbers in ZF.

Remark. The order symbols can be written \lesssim and \succsim.

share|improve this question
    
Note that if $X$ is not empty then a partial surjection is equivalent to a surjection. This ordering is commonly denoted $X\leq^* Y$, and have been referenced on this site more than several times (both your specific and general questions). –  Asaf Karagila Sep 20 '13 at 8:13
    
@AsafKaragila, thanks, does the ordering have a name? Its hard to find information about something when all its got is a symbol. –  goblin Sep 20 '13 at 20:13
    
There's no name to this relation, much like there's no actual name to the usual relation. –  Asaf Karagila Sep 21 '13 at 13:30

2 Answers 2

up vote 5 down vote accepted

Note that if there is a surjection $f:Z\to X$, and $Y\supseteq Z$, then either $X=\emptyset$ or there is a surjection $f:Y\to X$, so the use of partial functions does not give us any advantage (beyond not having to say "or $X$ is empty").

You may want to start by looking at this MO question. What I call the Dual Bernstein-Schroeder theorem (DBS) is the statement that if there are surjections from $A$ to $B$ and vice versa, then there is a bijection between $A$ and $B$. It is open whether this implies choice. As shown at the link, it implies that there are no infinite Dedekind finite sets, but not much more is known.

Your question is whether DBS is a theorem of $\mathsf{ZF}$, and the answer is definitely no. The note by Benjamin Miller mentioned at the MO question (and currently hosted here) gives several counterexamples. These are perhaps not the easiest counterexamples to attain in terms of forcing, but I like them because they involve natural sets that appear in work on descriptive set theory.

Notably:

1. It is provable in $\mathsf{ZF}$ that there is a surjection from $\mathbb R$ onto $\mathbb R\times\omega_1$, and viceversa. Here, $\omega_1$ is the first uncountable ordinal. If these two sets are equipotent, then there is an injection of $\omega_1$ into $\mathbb R$. But this is not provable in $\mathsf{ZF}$. For example, in the Feferman-Lévy model where the reals are a countable union of countable sets, there is no such injection.

To see that there is a surjection, note that the non-terminating decimal expansion of a real $x$ can be seen as coding a binary relation $R$ on the natural numbers: Fix a bijection $\langle\cdot,\cdot\rangle$ between $\mathbb N\times\mathbb N$ and $\mathbb N$, and set $n\mathrel{R} m$ iff the $\langle n,m\rangle$-th digit in the expansion of $x$ is $1$.

Now, use this to define a surjection $f$ from $\mathbb R$ onto $\omega_1$: If this relation $R$ is a well-order of type $\omega+\alpha$, map the real to $\alpha$. Else, map it to $0$.

2. There is an obvious surjection from $\mathbb R$ onto its quotient $\mathbb R/\sim$, where $\sim$ is Vitali's equivalent relation that identifies two reals iff their difference is in $\mathbb Q$. Less trivially, there is also (provably in $\mathsf{ZF}$ a surjection from $\mathbb R/\sim$ onto $\mathbb R$. However, it is not provable that these two sets have the same size. In fact, it is consistent that the quotient is strictly larger. See these nice slides by Mike Oliver on this phenomenon.

For more examples, I refer you to Miller's note. For additional remarks, see here. Definitely, as you suspect, adopting the surjective version of equipotency, leads to much interesting structure becoming invisible. For example, the partial order of cardinalities realized by quotients of $\mathbb R$ can already be quite varied, and all of this variety could just disappear: It is consistent with this great variety that all these quotients are either countable, or at least as large as $\mathbb R$, with the end result that after the identification we only see countable things, and the reals.

share|improve this answer

The order which you define is commonly denoted by $\leq^*$, and I will use that notation in my answer as well.

As Andres wrote in his excellent answer, without the axiom of choice not much is provable about $\leq^*$. We know that if $\leq^*$ is antisymmetric (on cardinals) then there are no Dedekind-finite sets. We also know that if it is a total ordering then the axiom of choice holds.

We don't know a whole lot more other than that. Certain choice principles such as the partition principle (which essentially states $\leq=\leq^*$) imply the antisymmetry of $\leq^*$.

Specific counterexamples can be found when Dedekind-finite sets exist, for example, one can have a Dedekind-finite set $A$ such that $A<A+A\leq^*A$, so trivially $A\leq^*A+A$ but because the set is Dedekind-finite we have $A\nsim A+A$.

Beyond that, one can show the following statement:

Theorem. Suppose that $V$ is a model of $\sf ZFC$. For every set $A$ there exists a symmetric extension of $V$ such that $\mathcal P(A)$ can be embedded into the cardinals ordered by $\leq^*$ and $\leq^*$. Moreover, one can preserve $\sf DC_\kappa$ for an arbitrary $\kappa$ while doing so.

One can extend this and show the even weirder statement is true:

Theorem. Suppose that $V$ is a model of $\sf ZFC$, then there is a class-symmetric extension such that $(\mathcal P(\sf Ord),\subseteq)$ can be embedded into $\leq$ and $\leq^*$, while preserving $\sf DC_\kappa$. If $V$ satisfies global choice then $V$ itself embeds into the cardinals as well.

One interesting consequence from these theorems is that $\sf DC_\kappa$ is completely orthogonal to any chaotic behavior in $\leq^*$ and $\leq$. Another interesting conclusion is that one can have a decreasing chain of cardinals of any ordinal length (although not of length $\sf Ord$) alongside $\sf DC_\kappa$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.