Positive logical definition of finiteness

Question

In his debate with Cassirer and in some other writing, Heidegger tries to define positively the concept of finiteness for the beings. It is a novel and difficult approach as traditionally, in theology and metaphysic, finiteness of beings is negatively defined as an imperfection or a negation, the absence of infiniteness, as opposed to some perfect and infinite being like god.

I feel that this difficulty is strangely reflected in set theory. I reckon we can naturally associate positive definition with $\Sigma_1$ sets (it abides to our definition if there is one set such that... ) and negative definitions with $\Pi_1$ sets (it abides to our definition if there is not set such that...).

Now for example Dedekind definition of an infinite set is a positive definition, a set is infinite if there is a bijection between itself and a proper subset. Then the natural way of defining finite sets would be non-infinite set which is $\Pi_1$ or a negative definition.

We could also use $\omega$, the smallest set satisfying the axiom of infinity and say that another set is finite if there is no injection from $\omega$ in this set ; but once again its a negative definition.

So formally, what this boils down to is the following :

Is the definition of finiteness in set theory $\Pi_1$ or $\Delta_1$ ? I've just seen that it is $\Delta_1$ according to wikipedia, then what is a $\Sigma_1$ definition of it ?Also, have the philosophical implications of this already been discussed ?

And for a subsidiary questions :

Are there models of set theory that "think" one of its element is infinite when it is actually finite ? Akin to what happens between countable and non-countable sets with the Löwenheim-Skolem theorem.

Answer 1

Yes, finiteness is $\Delta_1$ in set theory.

A set $x$ is finite iff there are $f,\alpha$ such that:

• $f$ is a bijection from $x$ to $\alpha$;

• $\alpha$ is a nonzero ordinal; and

• every ordinal $<\alpha$ has an immediate predecessor.

This is a $\Sigma_1$ definition, the only subtle point being that ordinalhood is $\Delta_1$: to see this, use the "hereditarily transitive set" characterization of ordinals.

Note meanwhile that unlike the $\Sigma_1$ definition above, the $\Pi_1$ definition of finiteness coming from the $\Sigma_1$ definition of infiniteness you give assumes "Dedekind-finite = finite" (the definition of "finite" in $\mathsf{ZF}$ is "in bijection with an ordinal $<\omega$"). While easily provable in $\mathsf{ZFC}$ (or indeed vastly less), this is not a theorem of $\mathsf{ZF}$ alone.

Here's a $\Pi_1$ characterization of finiteness which works in $\mathsf{ZF}$ alone:

A set $x$ is finite iff there is no nonempty successor-closed set of ordinals $I$ together with a set of maps $\{f_a: a\in X\}$ such that each $f_a$ is an injection from $a$ to $x$.

The point is that in $\mathsf{ZF}$, a set is infinite iff every finite ordinal injects into it. In $\mathsf{ZF}$ this falls short of the existence of an injection from $\omega$ (= Dedekind-infiniteness), but is still fundamentally of the same "shape." EDIT: As Asaf shows, Dedekind-finiteness is not $\Delta_1$ in $\mathsf{ZF}$ alone, so we really have divergent complexity behaviors here.

As a coda, note that your question is in terms of the Levy hierarchy. Other notions of complexity can yield more complicated situations - see e.g. here.

---

As to your subsidiary question, models of $\mathsf{ZFC}$ can only be confused about finiteness in one way: $M\models\mathsf{ZFC}$ may have elements it thinks are finite which are actually infinite, but it cannot have elements it thinks are infinite which are actually finite.

The former point is a consequence of the compactness theorem, and the argument is identical to the existence of nonstandard models of arithmetic. To see the latter point, just note that $M$ is correct about the finiteness of all sets of size $0$ (there's only one of those) and if $M$ is correct about the finiteness of all sets of size $n$ (for $n$ finite) then $m$ is correct about the finiteness of all sets of size $n+1$ (think about what $M$ knows about the impact on cardinality of adding a single element to a set).

Answer 2

Let me add a remark to Noah's excellent answer.

While $\sf ZFC$ prove that "finite" is equivalent to "Dedekind-finite", and therefore both are $\Delta_1^{\sf ZFC}$ notions; this is not true for $\sf ZF$. Namely, the formula $\varphi(x)$ stating that $x$ is Dedekind-finite is not $\Delta_1^{\sf ZF}$.

If $M$ is a countable transitive model of $\sf ZFC$, then there is a generic extension of $M$, $M[G]$, and an intermediate model of $\sf ZF$, $N$, such that:

1. $M\subseteq N\subseteq M[G]$ are all transitive.
2. $x\in N$ and therefore $x\in M[G]$.
3. $N\models x$ is Dedekind-finite, but $M[G]\models x$ is countable (and therefore Dedekind-infinite).

So, if "Dedekind-finite" was $\Delta_1^{\sf ZF}$, it would be absolute between the transitive models $N$ and $M[G]$. But that's not true, of course. So it's worth keeping track of our assumptions when going between equivalent definitions.

---

Let me also throw in another $\Pi_1$ definition of finiteness, due to Tarski: $x$ is finite if and only if $(\mathcal P(x),\subseteq)$ is well-founded. Which is to say, for every non-empty $y\subseteq\mathcal P(x)$, there is some $z\in y$ which is $\subseteq$-minimal. Writing this definition out carefully will be $\Pi_1$.