Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
    
Maybe if you remove the law of induction? – Shengjia Zhao Jan 11 at 13:21
2  
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
    
1  
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
6  
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.

share|cite|improve this answer
    
+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
3  
@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.
share|cite|improve this answer
1  
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
1  
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
1  
@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
1  
@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.

share|cite|improve this answer
    
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.

share|cite|improve this answer
1  
This is directly related to Steve Schweber's first bullet point. (I mean, Noah.) – Akiva Weinberger Jan 11 at 22:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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