It is known that the sum and the product of two Dedekind-finite cardinals are also Dedekind-finite cardinals. What about cardinal exponentiation ? Question: Let A and B be two Dedekind-finite cardinals, let C be the cardinal A power B (i.e:let x be a set with cardinal A and y be a set with cardinal B and let C be the cardinal of the set of functions with domain y and range a subset of x). Is it true that C is a Dedekind-finite cardinal ? Gérard Lang

up vote 12 down vote accepted

The answer is no, not necessarily, because if there are infinite Dedekind finite sets, then the class of Dedekind finite sets is not closed under power set, and hence not closed under $A\mapsto 2^A$.

To see this, simply note that if $A$ is any infinite set, then $P(A)$ has the singletons, the doubletons, the subsets of size $3$, and so on. So we can find a countably infinite subset of $P(P(A))$, and so $P(P(A))$ is not Dedekind finite.

In particular, if $A$ is Dedekind finite but infinite, then $2^{2^A}$ is not Dedekind finite, and so it is consistent with ZF that the Dedekind finite sets are not closed under exponentiation.

It is a theorem of Kuratowski that the following holds:

There exists a surjection $f\colon A\to\omega$ if and only if there exists an injection $F\colon\omega\to\mathcal P(A)$.

As Joel says, the power set of an infinite set can always be mapped onto $\omega$, therefore the second-power set is always Dedekind-infinite. So if the first one is not, then the second one is.

It should be remarked that both cases can be realized in terms of consistency.

  1. Consider the case there $S=\bigcup P_n$ where $P_n$ are pairwise disjoint sets, and there is no infinite family $I\subseteq\omega$ such that a choice function for $\{P_i\mid i\in I\}$ exists. We call such $S$ a Russell set, and its consistency has been shown by Fraenkel (using atoms) and Cohen (using forcing).

    Then $S$ is Dedekind-finite, since otherwise pick any countably infinite subset it must either meet infinitely many pairs on a single point (thus defining a choice function for an infinite family of pairs), or include infinitely many pairs and then by induction on a fixed enumeration of this set we can choose from these pairs.

    But clearly $S$ can be mapped onto $\omega$. Therefore its power set, which is the exponentiation of two Dedekind-finite cardinals, is Dedekind-infinite.

  2. We say that $A$ is amorphous if $A$ cannot be written as a disjoint union of two infinite set. We can show that an amorphous set cannot be linearly ordered, and in fact if $P$ is a linearly ordered set, then any function $f\colon A\to P$ must have a finite range (which means it is almost everywhere constant).

    In particular this means that an amorphous set cannot be mapped onto $\omega$, and therefore its power set is also Dedekind-finite. But in fact $A^A$, all the functions from $A$ to itself is a Dedekind-finite set, because we can show that $A\times A$, while not amorphous, cannot be mapped onto $\omega$ and therefore $\mathcal P(A\times A)$ is Dedekind-finite, so $A^A$ which is a subset of $\mathcal P(A\times A)$ must be Dedekind-finite as well.

    Amorphous sets have been shown to be consistent by Fraenkel using atoms, and this result can be easily transferred to a context without atoms (either by forcing or by using the Jech-Sochor embedding theorem).

So we can say that Dedekind-finite cardinals are closed under exponentiation if and only if every Dedekind-finite set is finite. But given two infinite Dedekind-finite sets, we cannot necessarily say that their exponentiation is Dedekind-infinite.

  • Asaf, do you know if the power set of a D - finite set can be equipotent to the set of reals? If not, how about its double power set, and the power set of the reals? If yes, what if in addition we ask that the D - finite set be itself a power set? (Is there a reference for these themes?) (I owe you an email. Please give me a few hours.) – Andrés E. Caicedo Aug 26 '14 at 16:41
  • Andres, in the Cohen model, I believe the power set of the Dedekind finite set of reals should be equal to the reals. It is certainly as big. I'll have to think about an argument for the other direction, but I'm sure it's true. – Asaf Karagila Aug 26 '14 at 16:49
  • The other direction is the key, any D - infinite power set is at least as large as the reals. – Andrés E. Caicedo Aug 26 '14 at 17:00
  • 1
    Andres, here is a sketch, and you can tell me what's wrong with it. Let $\dot A$ be the name of the generic D-finite set. Then there is a name (for the full extension) of an injection from $2^A$ into $2^\omega$, since in the full Cohen model, $A$ is countable. Now consider a list in the ground model of all the names of subsets of $A$. Since the forcing is ccc, there are only continuum many, so we there are only continuum many symmetric ones (externally). Now by usual arguments build a name which $1$ forces to be an injection from all these sets into $\omega_1$. [...] – Asaf Karagila Aug 26 '14 at 21:56
  • 1
    [...] For example, list all the names in the ground model, and then map each name into a pair of countable ordinals $(\alpha,\beta)$, such that there is an antichain interpreting the name as an actual symmetric name, and then mapping it into \beta. You can do that, then choose equivalence classes under orbits of permutations (which move finitely many reals anyway) and create a name which is stable under automorphisms. By counting arguments you don't go above $\omega_1$ names, so everything is just peachy. – Asaf Karagila Aug 26 '14 at 22:00

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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