0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Malice Vidrine Jul 15 '16 at 8:02
  • 1
    $\begingroup$ If sets cannot be elements of themselves then using cardinality $|S| \not = |S \cup \{S\}|$ implies $S$ has a finite number of elements $\endgroup$ – Henry Jul 15 '16 at 11:22
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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