Consider ZFC with both powerset and infinity removed and collection and $\in$-induction included. The well-ordering principle is not assumed.
Does this theory prove that, for every set $X$, there is a set of all finite subsets of $X$?
$\begingroup$
$\endgroup$
11
-
1$\begingroup$ The answer is yes if we assume $\in$-Induction which is stronger than the usual Foundation without Infinity. (The combination of Infinity and Replacement implies the existence of a transitive closure of a set, which is equivalent to $\in$-induction over the remaining axioms.) The proof follows from the usual induction argument. I am not sure what happens without $\in$-Induction. $\endgroup$– Hanul JeonCommented May 12 at 18:59
-
1$\begingroup$ I don't how to implement your "usual argument" by $\in$-induction without this. If every set is finite, then induction on the finite ordinals shows every set has a power set. If there is an infinite set, then inductively for every $n$ we get the collection of size $n$ subsets of $X$ as a set, and then if $\omega$ exists by collection we can put them all together. But don't we need $\omega$ to do this? The argument I've sketched does not seem to use $\in$-induction, but it does use existence of $\omega$ if there is an infinite set. $\endgroup$– Joel David HamkinsCommented May 12 at 19:15
-
2$\begingroup$ The Finite Powerset statement is indeed equivalent to "If there is an infinite set, then $\omega$ exists". That equivalence holds even if both parts of $\in$-induction (i.e. Transitive Containment and Regularity) are excluded. For ($\Rightarrow$), let $X$ be an infinite set, then take the set of cardinalities of all finite subsets of $X$, and this is $\omega$. $\endgroup$– Paul Blain LevyCommented May 12 at 19:35
-
1$\begingroup$ @HanulJeon What was the argument you had in mind with "the usual argument" by $\in$-induction. I don't see it. (And regarding your earlier suggestion about $m<n$, yes, one can prove that every finite set has a power set even without $\in$-induction, but that doesn't help with the question if there are infinite sets, since one seems to need $\omega$ in order to get the set of all finite subsets of the set.) $\endgroup$– Joel David HamkinsCommented May 12 at 19:43
-
1$\begingroup$ You could probably get a counterexample to the original question (with the usual foundation axiom) by starting with a ZFA model with a strongly amorphous set of atoms A and taking all the sets hereditarily a quotient of some $A^n,$ and reintroducing Foundation with the tricks in mathoverflow.net/a/314490/109573 or arxiv.org/abs/2312.11902 $\endgroup$– Elliot GlazerCommented May 13 at 6:10
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
2
The answer is Yes.
In your theory, let us assume that "finite" means equinumerous with a finite von Neumann ordinal, where that means a transitive set that is well-ordered by $\in$ and having a largest element and no limit ordinals below.
We can prove that the finite ordinals are well-ordered, and therefore the principle of induction works on them. Using this, we can prove that every finite set has a power set, since the power set of a set of size $n+1$ is obtained from the power set of a size $n$ subset, by adding the extra element or not to every subset.
If every set is finite, it follows that every set has a power set, and in this case this power set is the set of finite subsets.
Otherwise, there is an infinite set $X$. By $\in$-induction, this set has an ordinal rank, which cannot be finite, since by induction every finite-rank set is finite. And so $\omega$ exists.
Now argue by induction that for every $n$, the collection of size-$n$ subsets of $X$ exists. This is easily true for $n=0$. If it is true for $n$, then we can prove that it is also true for $n+1$, since the size $n+1$ subsets of $X$ arise from a subset of the product of the size $n$ subsets with $X$ itself, adding an additional element in all possible ways to the size $n$ subsets. (Note: products exist by suitable instances of collection to get all the sections existing and then put them together.)
Finally, by an instance of collection using $\omega$, we can collect together all the size $n$ subset families over all finite $n$, and from this construct the set of finite subsets of $X$, as desired.
answered May 12 at 19:30
-
$\begingroup$ Thanks! But surely Replacement (rather than Collection) is sufficient for your argument? $\endgroup$ Commented May 12 at 19:47
-
1