# 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 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 at 13:21
– Shengjia Zhao Jan 11 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 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 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 http://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 at 13:34
Can you give an example of a set that is Dedekind-finite but not ZF-finite? – Dan Christensen Jan 11 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 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 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 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 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 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 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 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 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 at 22:29
Is this only talking about constructive logic? If so, you should emphasize that… – Akiva Weinberger Jan 14 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 at 22:16
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9327653050422668, "perplexity": 577.713138046256}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2016-26/segments/1466783395560.69/warc/CC-MAIN-20160624154955-00173-ip-10-164-35-72.ec2.internal.warc.gz"}