Finite set theory and the Axiom of the Power Set

Question

I've been thinking about set theory recently, and one of the things I noticed was that if we restrict to finite sets, then the power set can be constructed through repeated application of the axioms of separation, pairing, and union. And that made me wonder how ZFC looks when we replace the Axiom of Infinity with its negation.

So I have a few different questions. For this question, "finite set theory" refers to the Axioms of Extensionality, Empty Set, Pairing, Union, Separation, and the negation of Infinity.

• Can finite set theory to prove that no infinite sets exist? The negation of infinity cuts off the cumulative hierarchy at $V_\omega$, which might be enough given Foundation, but it's not entirely clear to me that the nonexistence of an inductive set implies the nonexistence of any infinite set.

• Of course, the cumulative hierarchy requires the power set operation, so this raises my initial question. Is the Axiom of Power Set a theorem of finite set theory?

• Are the Axioms of Replacement and Choice theorems of finite set theory? Since they both involve functions, a related question is whether functions can be constructed in finite set theory without the power set operation.

• Given responses below, it seems like the Axiom of Foundation may be more important than I thought. How does it affect the answers to these if added to "finite set theory"?

Answer 1

Here is a model of your "finite set theory" (including Foundation) in which there is an infinite set and Power Set and Replacement fail. Let $A=\{\emptyset,\{\emptyset\},\{\{\emptyset\}\},\{\{\{\emptyset\}\}\},\dots\}$ and let $M$ be the closure of $V_\omega\cup\{A\}$ under Pairing, Union, and taking subsets (so if $X\in M$ and $Y\subseteq X$ then $Y\in M$). It is clear that $M$ satisfies all of your axioms except possibly the negation of Infinity. To prove the negation of Infinity, note that if $X\in M$, then the transitive closure of $X$ contains only finitely many elements of cardinality $>1$ (since this is true of $A$ and for every element of $V_\omega$, and is preserved by taking pairs, unions, and subsets). So $M$ cannot contain any inductive set.

However, $M$ does contain an infinite set, namely $A$. It is also clear that $M$ fails to satisfy Power Set, since $M$ contains every subset of $A$ but $\mathcal{P}(A)\not\in M$ (either by the criterion mentioned above, or by noting that every element of $M$ is countable). Replacement also fails, since the usual recursive definition of the obvious bijection $A\to\omega$ can be implemented in $M$, so Replacement would imply $\omega$ is a set.

This model does satisfy Choice in the form "if $X$ is a set of disjoint nonempty sets then there is a set that contains one element from each of them" (since $M$ contains all subsets of $\bigcup X$). It does not satisfy Choice in the form "if $X$ is a set of nonempty sets then there exists a choice function $X\to\bigcup X$", basically because it is very hard to construct functions as sets in $M$ (for instance, if $X=A\setminus\{\emptyset\}$, the unique choice function for $X$ would have infinitely many 2-element sets in its transitive closure). Probably it is possible to build a model where any reasonable form of Choice fails, but I don't know how exactly to do that at the moment.

Answer 2

Since you don't include Foundation, we can get a very strange model indeed. Namely, consider an $\omega$-model $M$ of ZF-Foundation+"there is an infinite set $A$ of Quine atoms" (a Quine atom is a set satisfying $x=\{x\}$, and the existence of many Quine atoms is consistent with ZF-Foundation). Now look at the structure $W$ which is the closure of $$V_\omega^M\cup A\cup\{[A]^n: n\in\mathbb{N}\}$$ under Pairing, Union, and Separation. Here "$[X]^k$" denotes the set of $k$-element subsets of $X$.

$W$ satisfies finite set theory, but not Powerset ($\mathcal{P}(A)$ doesn't exist) or Choice (there is no choice function for the set of two-element subsets of $A$).

I am not sure whether $W$ satisfies Replacement, but I suspect it does, and I don't immediately see how to add a failure of Replacement. Meanwhile, incorporating Foundation seems difficult.

---

If we define $W$ as the Pairing/Union/Separation-closure of $$V_\omega^M\cup A\cup\mathcal{P}(A)\cup\{[\mathcal{P}(A)]^n: n\in\mathbb{N}\}$$ instead, where $M$ satisfies "$A$ is an amorphous set of Quine atoms", then I believe we get a model of finite set theory together with the negation of Replacement and Powerset; powerset fails since we don't have $\mathcal{P}^2(A)$, and Replacement fails since the image of the map sending each subset of $A$ to its cardinality if it is finite, or the cardinality of its complement otherwise, does not exist.