# Express that a set is finite using symbols

Two related questions:

1. What's the most elegant way to express that the set $S$ is finite using logical symbols? Obviously this will depend to some extent on what you allow yourself to quantify, so this is a soft question. Here is one way to write the desired statement: $$\exists (n\in\mathbb{N}) \exists (f:S\rightarrow \{1,2,\dots,n\}) \forall(x,y\in S) x\neq y \implies f(x)\neq f(y)$$ This just says that there is an injective function from $S$ to a finite subset of the natural numbers, which is equivalent to finiteness of $S$. Can one do much better than this? (I have allowed myself to quantify a function here. If that was not allowed, I'd have to instead take $f$ to be a subset of some powerset of $S$ and add some extra symbols to indicate that $f$ is a function. For the purposes of this question, I don't care about such technicalities.)
2. Is it possible to express that a set $S$ is finite (in logical symbols as above) without reference to any other sets, such as $\mathbb{N}$?

[This question is motivated by the transfer principle from non-standard analysis.]

• For 2, there is the notion of a Dedekind finite set, which in the context of mild Choice principles is equivalent to the usual one. – Malice Vidrine Jul 15 '16 at 8:02
• If sets cannot be elements of themselves then using cardinality $|S| \not = |S \cup \{S\}|$ implies $S$ has a finite number of elements – Henry Jul 15 '16 at 11:22

## 1 Answer

Finiteness can be expressed by several approaches, all of which are equivalent with the axiom of choice assumed. I will not write the formal statements, but rather the human-readable formulation.

1. There is an injection from $S$ into a bounded initial segment of the natural numbers.

However, we can replace the natural numbers by the finite ordinals. It might seem a bit circular to define finite in terms of finite ordinals. But we can say that an ordinal is finite if and only if it is $0$ or that it is a successor ordinal, and everyone smaller is also zero or a successor ordinal.

2. Every non-empty set of subsets of $S$ has a $\subseteq$-minimal element.

In other words, $\mathcal P(S)$ is well-founded.

3. Every injective function from $S$ to itself is a bijection.

This is known as Dedekind-finiteness.

4. Every linear ordering of $S$ is a well-ordering.

Along with the following principle,

5. Every well-ordering of $S$ satisfies that the reverse order is also a well-ordering of $S$.

These two will have the caveat (without the axiom of choice) that $S$ might not be well-orderable or linearly orderable to begin with.

There are many more ways to formulate finiteness. Philosophically speaking, Dedekind-finiteness is the "maximal notion", as without the axiom of choice we can prove that Dedekind-infinite sets are exactly those with injections from $\Bbb N$ into them; so a Dedekind-infinite set cannot possibly be called "finite" in any reasonable context.

Interestingly, (2) is equivalent to (1) which is the usual notion of finiteness.