# Does it exist a “recursively infinite” set?

I was inspired by this question:

Does it exist an infinite set whose elements are all infinite sets?

This question received many excellent answers but made me wonder about the following in the context of set theory (say ZFC):

We say that a set has the property $P$ if it is infinite and each of its element also has the property $P$.

So, in order to satisfy $P$, a set $A$ has to be infinite, and its elements also have to be infinite. And the elements of the elements of $A$ too. And the elements of the elements of the elements...

Is there a set satisfying $P$?

I couldn't construct an example by hand, nor prove such a set couldn't exist. I am not even completely sure the property $P$ is well-defined...

• In ZF, there is a limit to how far "down" you can go into a set. What I mean is that given a set $x_0$, the chain $x_0\ni x_1\ni x_2\ni\cdots$ must end after a finite number of steps, as you reach the empty set, although it isn't difficult to construct examples of any finite length. Of course, if you remove the axiom of well-foundedness from ZF, or use some other non-well-founded set theory, then you can get around this constraint. – Arthur Mar 20 '18 at 10:26
• I think property $P$ is not well defined. The definition somehow makes use of property $P$ (so at a stage that it is not defined yet). – drhab Mar 20 '18 at 10:30
• I have to leave the house now. But I will write something later. There is some deep confusion here as to the role of recursion. – Asaf Karagila Mar 20 '18 at 10:39
• @Arthur: I choose ZFC "naively", because that the axioms of set theory I am familiar with. But, if we can make construct examples of sets satisfying $P$ by playing around the axioms, I would be very happy to hear about it :) – Taladris Mar 20 '18 at 10:48
• I think the property that you're after ("$x$ has property $P$") can be more rigorously phrased as "The transitive closure of x contains only infinite sets", and might be called something like "hereditarily infinite". An example could be given by describing a collection of sets $x_i$ for $i\in \Bbb N$ where each $x_i$ consists of all $x_j$ for $i\neq j$. Then each of the $x_i$ would have this property. I honestly don't know whether this specific approach makes sense, but a true example would go along these lines. – Arthur Mar 20 '18 at 10:48

## 2 Answers

There is a confusion here. Recursion goes up, based on a well-founded relation, it does not go down. When you define something by recursion it is a step-by-step definition. From assuming you could define it so far, you define it one step further.

Your definition seems to be co-well-founded, you postulate the property of a set and require it implies the property for its elements.

In $\sf ZF$ the $\in$ relation is well-founded, so this is not quite possible. But we can still get some sufficiently nice properties which will hold for the elements. For example being hereditarily ordinal definable, or constructible. Or being an ordinal. Or just being a set.

But in none of these cases you start by postulating the property for a set, and then require it implies the property for the elements of the set. Instead you start by construction some class, and taking its hereditary part, or you define something from bottom to top, and then you end up with a class satisfying your property.

When you tack on the requirement that the property implies that the set is infinite, then you quickly run into a contradiction. The bottom-up constructions start with the empty set—for a reason, too: it's the basis of the set theoretic universe—and go upwards. So at the root of every set, you will find the empty set. And so in every non-empty transitive set, you will find the empty set as an element.

If you require that $P$ is hereditary, then it implies that if $x$ has it, the transitive closure of $x$ has it. But if $x$ is non-empty, $\varnothing$ is an element of that transitive closure. So infinitude cannot be part of the definition of $P$.

I am not sure whether this answers your question.

If the axiom of foundation is accepted then no set exists such that it is infinite and that all elements of its transitive closure are infinite.

This because by induction on $\overline{\in}$ it can be proved that:$$\forall x[x=\varnothing\vee\varnothing\overline{\in}x]\tag1$$

Here $\overline{\in}$ stands for the transitive closure of relation $\in$ and $\varnothing\overline{\in}x$ can be read as $\varnothing\in\mathsf{Tc}(x)$ where $\mathsf{Tc}(x)$ stands for the transitive closure of $x$.

So in $(1)$ it is stated that a set that is not empty has a transitive closure that contains the empty set (which is not infinite).