6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ "Are there models of set theory that "think" one of its element is infinite when it is actually finite ?" Do you mean the other way around? It's easy to show that the answer to the question you've written is negative (given a model of set theory, consider the smallest size of a genuinely-finite set which the model thinks is infinite ...). $\endgroup$ Mar 8 '21 at 21:23
  • $\begingroup$ You might be interested in the property of being well-ordered as finite sets can be simultaneously well-ordered in both ascending and descending directions. $\endgroup$
    – hardmath
    Mar 8 '21 at 21:25
  • 1
    $\begingroup$ @hardmath Of course, being well-ordered is a $\Pi_1$ property. $\endgroup$ Mar 8 '21 at 21:55
7
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Alright, I'll look into this link of yours, thank you for this detailed answer, maybe it's too bad Heidegger ignored that it was indeed $\Delta_1$ ! $\endgroup$
    – Johan
    Mar 9 '21 at 16:15
  • 1
    $\begingroup$ @Johan I would be hesitant to link philosophical notions with mathematical ones too closely; such analogies tend not to hold up to scrutiny in my experience. $\endgroup$ Mar 9 '21 at 16:16
  • $\begingroup$ This last comment of mine was more of a joke but still I would tend to disagree with your hesitation. Analogies are not meant to hold against all winds and the breaking points are what is interesting ; mathematics robustness naturally leads to those aporia and they can be rich starting points for philosophy. $\endgroup$
    – Johan
    Mar 11 '21 at 11:20
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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