# What's between the finite and the infinite?

I'm wondering if there are any non-standard theories (built upon ZFC with some axioms weakened or replaced) that make formal sense of hypothetical set-like objects whose "cardinality" is "in between" the finite and the infinite. In a world like that non-finite may not necessarily mean infinite and there might be a "set" with countably infinite "power set".

• Maybe if you remove the law of induction? – Shengjia Zhao Jan 11 '16 at 13:21
• Remark : using countable axiom of choice and the axiom of infinity, it can be shown that a set which is not finite contains $\mathbb{N}$. – Clément Guérin Jan 11 '16 at 13:21
• – Shengjia Zhao Jan 11 '16 at 13:22
• Good question with good answers, on hold just because some high-reputation people seem to think "not an exercise that admits a provable yes-or-no answer" means "unclear what you're asking." Oh well. – Mike Haskel Jan 11 '16 at 18:20
• Of course this is vague because it's the kind of question that cannot be made clearer without knowing the answer and I don't see what "specific" information I could add. At the same time, however, it seems to be clear enough to some, as the really good answers below show. So maybe, for future reference, the down-voters would be so kind as to leave a comment on what exactly should have been done differently. Thanks :) – Damian Reding Jan 11 '16 at 23:53

There's a few things I can think of which might fit the bill:

• We could work in a non-$\omega$ model of ZFC. In such a model, there are sets the model thinks are finite, but which are actually infinite; so there's a distinction between "internally infinite" and "externally infinite." (A similar thing goes on in non-standard analysis.)

• Although their existence is ruled out by the axiom of choice, it is consistent with ZF that there are sets which are not finite but are Dedekind-finite: they don't have any non-trivial self-injections (that is, Hilbert's Hotel doesn't work for them). Such sets are similar to genuine finite sets in a number of ways: for instance, you can show that a Dedekind-finite set can be even (= partitionable into pairs) or odd (= partitionable into pairs and one singleton) or neither but not both. And in fact it is consistent with ZF that the Dedekind-finite cardinalities are linearly ordered, in which case they from a nonstandard model of true arithmetic; see https://mathoverflow.net/questions/172329/does-sageevs-result-need-an-inaccessible.

• You could also work in non-classical logic - for instance, in a topos. I don't know much about this area, but lots of subtle distinctions between classically-equivalent notions crop up; I strongly suspect you'd find some cool stuff here.

• +1: Nice! I didn't even think about internal/external infiniteness distinctions. – Cameron Buie Jan 11 '16 at 13:34
• Can you give an example of a set that is Dedekind-finite but not ZF-finite? – Dan Christensen Jan 11 '16 at 14:27
• @DanChristensen I don't understand your question. Every finite set is Dedekind finite. (What does "ZF-finite" mean?) – Noah Schweber Jan 11 '16 at 14:28
• I edited my question. You said, "In ZF, we can have sets which are not finite but are Dedekind-finite." Can you give an example of such a set? – Dan Christensen Jan 11 '16 at 14:31
• @DanChristensen Countable choice (CC) is an axiom much weaker than AC - that is, CC does not imply AC, and in many precise ways the gap between the two is very large - and even ZF+CC proves that every Dedekind-finite set is finite. And even that's overkill - over ZF, CC is strictly stronger (again, "much" stronger in precise senses) than "every Dedekind-finite set is finite". – Noah Schweber Jan 11 '16 at 14:41

Well, there are a few notions of "infinite" sets that aren't equivalent in $\mathsf{ZF}.$ One sort is called Dedekind-infinite ("D-infinite", for short) which is a set with a countably infinite subset, or equivalently, a set which has a proper subset of the same cardinality. So, a set is D-finite if and only if the Pigeonhole Principle holds on that set. The more common notion is Tarski-infinite (usually just called "infinite"), which describes sets for which there is no injection into any set of the form $\{0,1,2,...,n\}.$

It turns out, then, that the following are equivalent in $\mathsf{ZF}$:

1. Every D-finite set is finite.
2. D-finite unions of D-finite sets are D-finite.
3. Images of D-finite sets are D-finite.
4. Power sets of D-finite sets are D-finite.

Without a weak Choice principle (anything that implies $\aleph_0$ to be the smallest infinite cardinality, rather than simply a minimal infinite cardinality), the following may occur:

1. There may be infinite, D-finite sets. In particular, there may be infinite sets whose cardinality is not comparable to $\aleph_0.$ Put another way, there may be infinite sets such that removing an element from such a set makes a set with strictly smaller cardinality.
2. There may be a D-finite set of D-finite sets whose union is D-infinite.
3. There may be a surjective function from a D-finite set to a D-infinite set.
4. There may be a D-finite set whose power set is D-infinite.
• Beat my literally by 5 seconds! – Noah Schweber Jan 11 '16 at 13:31
• Is this “Tarski-infinite” (actually, it's negation, Tarski-finite) equivalent to the definition appearing in Jech? I quote: A set $S$ is T-finite if every nonempty $X\subset \mathcal{P}(S)$ has a $\subset$-maximal element. – Pedro Sánchez Terraf Jan 11 '16 at 15:42
• An early but fairly comprehensive paper on these kinds of variations is Sur les ensembles finis by Alfred Tarski (1924). I made some comments about it in these sci.math posts: 1 May 2007 and 4 May 2007 and 5 July 2007. Also of relevance is Some aspects and examples of infinity notions by J. W. Degen [Mathematical Logic Quarterly 40 #1, 1994, pp. 111-124]. – Dave L. Renfro Jan 11 '16 at 15:59
• @Pedro: Yes, it is. Likewise, it is equivalent to "every inductive family of subsets of $S$ has $S$ as an element," "every total ordering relation of $S$ is a well-ordering relation on $S$," and others. – Cameron Buie Jan 11 '16 at 16:08
• @Pedro: I found this to be a cop-out on Jech's side. In the old Axiom of Choice book of his, T-finite sets were defined as "Every chain of subsets has a maximal element". This is indeed weaker than "finite" in ZF itself. I was disappointed that in the Set Theory book (at least in the third edition) he decided to opt out of this intermediate definition after all. – Asaf Karagila Jan 11 '16 at 18:05

Let me make a few remarks about the constructive aspects. The standard definition is the following: a set $X$ is finite if there is a natural number $n$ and a bijection between $X$ and $\{ i \in \mathbb{N} : i < n \}$. Some of the expected properties are true:

• The disjoint union of two finite sets is finite.
• The product of two finite sets is finite.
• The set of maps between two finite sets is finite.

On the other hand, there are some strange facts:

• Subsets of finite sets may not be finite.
• Quotients of finite sets may not be finite.

For example, given a proposition $\varphi$, $\{ i \in \mathbb{N} : \varphi \land i < 1 \}$ is finite if and only if $\varphi \lor \lnot \varphi$ holds. (This is because equality in $\mathbb{N}$ is decidable.) Thus one is tempted to look for weaker notions of finiteness.

Here is one alternative. The class of Kuratowski-finite sets is defined inductively as follows:

• The empty set is Kuratowski-finite.
• Every singleton set is Kuratowski-finite.
• The union of two Kuratowski-finite sets is Kuratowski-finite.

It is true that the quotient of a Kuratowski-finite set is automatically Kuratowski-finite. Indeed, every Kuratowski-finite set is in bijection with the quotient of some finite set – thus, one might call them finitely generated sets. In particular, Kuratowski-finiteness is strictly more general than finiteness. On the other hand, subsets of Kuratowski-finite sets may not be Kuratowski-finite.

• This is either incomprehensible or unbelievable. – Lehs Jan 13 '16 at 22:29
• Is this only talking about constructive logic? If so, you should emphasize that… – Akiva Weinberger Jan 14 '16 at 3:24

At the elementary level of the sum of a typical infinite series such as $\sum_{n=1}^\infty \frac{1}{n^2}$ one can illustrate the idea of infinities smaller than the superscript $\infty$ in the sum by using the hyperreal framework. Here a choice of a positive nonstandard hyperinteger $H$ gives a hyperfinite sum $\sum_{n=1}^H \frac{1}{n^2}$ which is infinitely close to the sum of the series but is not quite it. Namely, one has $\sum_{n=1}^H \frac{1}{n^2}<\sum_{n=1}^\infty \frac{1}{n^2}$ (strict inequality) but $\sum_{n=1}^H \frac{1}{n^2}\approx\sum_{n=1}^\infty \frac{1}{n^2}$. Another typical application is the hyperfinite sum $\sum_{n=1}^H \frac{1}{10^n}<1$. Writing the lefthandside as zero, dot, followed by more than any finite number of $9$s is risky; see e.g., here.

• This is directly related to Steve Schweber's first bullet point. (I mean, Noah.) – Akiva Weinberger Jan 11 '16 at 22:16