Formally how do we view finite sets

Question

This might be silly, but I have been thinking about how we would work with finite sets very formally.

So, $\{1,2,3,\cdots,n\} = \{k \in \mathbb{Z}^+ \mid k \leq n\}$ gives a representee for which any set in bijective correspondence with it are said to be $n$ element sets. Mechanically, I could write out each of the symbols on paper. So, I suppose I could say that I can exhaust the list of symbols with an algorithm of some sort.

Would we say that starting from 1 we take the successor and get $1,S(1),S\circ S(1),S\circ S\circ S(1),\cdots$ and when we get to $S(n - 1) = n$ we terminate. So, this algorithm needs to terminate otherwise we would enumerate $\mathbb{Z}^+$ which contradicts our set not being in bijective correspondence with all positive integers.

I guess what I'm wondering is if finiteness corresponds to types of sets in formal set theory where quantification isn't needed. I have never delved too deeply into mathematical logic, so this question comes from a mathematical logic novice.

I'm sorry if all of this is too vague, but I would really enjoy any literature references to learn more about the underlying metamathematics behind finite sets.

Answer 1

This is actually very subtle, in fact IMO one of the most underrated subtleties to come out of mathematical logic.

To get the unsurprising part out of the way first, the way we do it is, as you suggest, to define the natural numbers first, and then define the finite sets as those that can be put into bijective correspondence with a proper initial segment of the natural numbers.

The way we define the natural numbers is also similar to your suggestion of 'termination of the successor operation'. We take $0$ to be the empty set, and define $S(x) = x\cup\{x\}.$ So, e.g. $1 = \{0\},$ $2 = \{1,0\},$ $3 = \{2,1,0\},$ etc. To formalize the 'etc.', we say that the natural numbers are the smallest set that contains $\emptyset$ and is closed under $S.$ (The usual nomenclature is we call such a set 'inductive'.. the axiom of infinite says there is an inductive set, then we take the intersection of all inductive sets and call that the natural numbers.)

But note, we couldn't just say 'it terminates after some finite number of applications' without it being circular (we're trying to define finiteness)... and this is where the subtle part starts. Is the notion that it is the smallest such set enough to capture the idea that every natural number can be expressed as a term of the form $S^n(\emptyset)$?

The answer is no! On quite general grounds, first order logic is not strong enough to enforce such a constraint. This is a consequence of the compactness theorem. Essentially, there will always be interpretations of set theory (or more basically, Peano arithmetic, or the full first order theory of natural number arithmetic) in which the natural numbers aren't all "reachable" from $0$ via the successor function.

We can obtain this constraint by using stronger (i.e. infinitary or higher-order) logic, but that just smuggles in our background set theory's notion of finiteness into the theory, and who's to say (besides us by fiat) that this is the "real finiteness"... formalizing our background set theory is the exact same problem.

On top of all this, purely mathematically speaking, finiteness is just a bit more entertaining (again IMO) than it may seem to have any right to be... I'd suggest for starters reviewing some of the many equivalent conditions (some of which become inequivalent in the absence of the axiom of choice) on the wikipedia page, where you can also find some references.

Answer 2

In modern mathematics, there's nothing but sets (well, we have proper classes which aren't sets but they just appear in category theory or NBG set theory). That is to say, we discuss things under Zermelo-Fraenkel's axiomatic set theory.

If you want to define finiteness under such a first-order axiomatic system, it won't be done. You'll need some higher-order axiomatic system, or something even further and deeper in philosophy, I personally recommend Hegel and a French guy called Alain Badiou, you may could try his book Being and Event where there are lots of reflectives of him on ZFC system.

Under Zermelo-Fraenkel axiomatic set theory, we have the existence of empty set $ \varnothing $ ensured by the axiom of infinite; and according to axiom of power set, we got immediately the existence of the set $ \left\{ \varnothing \right\} $, the power set of $\varnothing$, which is already a finite set who has already ONE element. And the axiom of infinite ensures again the existence of inductive sets, whose intersection is indeed the $\mathbb{N}$. So you see, the finiteness, or the concept of quantity, has already embedded in the axioms themselves, thus it can't be defined under them without quantification if we agree that the elements of the inductive set (or the $ \mathbb{N} $) are in a sense quantities or finite numbers.

By the way, the way that we define $ \mathbb{N} $ is:

$$ 0 := \varnothing $$ $$ 1 := \left\{\varnothing\right\} $$ $$ 2 := \left\{\varnothing,\left\{\varnothing\right\}\right\} $$

etc. That is called ordinal numbers.