# 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? Commented Jan 11, 2016 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}$. Commented Jan 11, 2016 at 13:21
• Commented Jan 11, 2016 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.
– user231101
Commented Jan 11, 2016 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 :) Commented Jan 11, 2016 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 form 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. Commented Jan 11, 2016 at 13:34
• Can you give an example of a set that is Dedekind-finite but not ZF-finite? Commented Jan 11, 2016 at 14:27
• @DanChristensen I don't understand your question. Every finite set is Dedekind finite. (What does "ZF-finite" mean?) Commented Jan 11, 2016 at 14:28
• @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". Commented Jan 11, 2016 at 14:41
• @user267839 Remember that "appear finite" just means "has an inejction into the thing the model thinks is $\omega$." The point is that we can have a "nonstandard $\omega$," with elements which are - externally - infinite (but internally finite by virtue of literally being elements of the model's $\omega$). E.g. any model of ZFC+"ZFC is inconsistent" must be such a model, since it will need to have a "number" which codes a proof of a contradiction in ZFC and no such truly finite number exists (hopefully!). Commented Jul 23 at 21:47

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! Commented Jan 11, 2016 at 13:31
• 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]. Commented Jan 11, 2016 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. Commented Jan 11, 2016 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. Commented Jan 11, 2016 at 18:05
• @Cameron: "Every total order is a well-order", what if it is a set which cannot be totally ordered? Commented Jan 11, 2016 at 18:06

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
Commented Jan 13, 2016 at 22:29
• Is this only talking about constructive logic? If so, you should emphasize that… Commented Jan 14, 2016 at 3:24
• Suppose that a set $X$ is finite, so that there is a natural number $n$ and a bijection $$f:X\to\{i\in\Bbb N:i<n\}.$$ Given any subset $Y$ of $X,$ letting $g$ be the restriction of $f$ to $Y,$ then $g$ is an injection into a finite well-ordered set, so its range is well-ordered, and there is a unique order-preserving injection $h$ from its range onto an initial segment of $\{i\in\Bbb N:i<n\}.$ Thus, there is some natural number $m\leq n$ such that $h\circ g:Y\to \{i\in\Bbb N:i<m\}$ is a bijection, and so $Y$ is finite. Please correct or clarify "subsets of finite sets may not be finite." Commented May 9 at 13:25

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.) Commented Jan 11, 2016 at 22:16