3
$\begingroup$

Is it possible to define a predicate in the first order language of set theory such that $F(x)$ is true iff $x$ is a finite set?

I understand that FOL cannot assert that the domain of discourse is finite, but what kind of predicates are definable about the cardinality of arbitrary sets? Is the notion of the existence of a bijection only expressible in second order logic?

$\endgroup$
  • $\begingroup$ I am almost sure there's no such predicate, but can't think how to prove it right now. The notion of a bijection $A\to B$ can be described in terms of the existence of a special element of the powerset of $A\times B$, so the issue's not here-it's easy to write formulae saying $|A|=n$, just not one saying $|A|>n$ for every $n$. $\endgroup$ – Kevin Carlson Sep 17 '14 at 2:08
5
$\begingroup$

The point is that set theory has its own definition of finite. An internal definition.

It's true that FOL can't truly define "finite", and if $\sf ZFC$ is consistent then it has a model $M$ such that $\{x\mid M\models x\text{ is a finite ordinal}\}$ is an uncountable set (although $M$ thinks that this set is countable); when we work in set theory we have the ability to use internal definitions for finiteness.

There are many many many ways to define finiteness of sets. Assuming the axiom of choice holds, those are all equivalent, but without it they don't have to be.

It should perhaps be pointed out that the notion "There is a bijection between $x$ and $y$" is again an internal notion in set theory, and not an external notion (for example, if $M$ is a countable model of $\sf ZFC$ then $M$ and $\{x\in M\mid M\models x\text{ is a finite ordinal}\}$ have a bijection between them, but this bijection is not an element of $M$).

These are just examples which show why set theory is such a wonderful foundational theory. It has a lot of internal expressive powers that allow us to define bijections, finiteness, and so on.

  1. (The standard definition) We can write a formula saying that $x$ is an ordinal which is either $0$ or a successor ordinal, and every element below $x$ is either zero or a successor ordinal. Now a finite set is a set which has a bijection with a finite ordinal.

  2. We can write a formula saying that if $y$ is a proper subset of $x$ then there is no bijection between $x$ and $y$. If $x$ satisfies this, then it is finite.

  3. We can write a formula saying that if $y$ is a proper subset of $x$ then there is no surjection from $y$ onto $x$. Again, $x$ satisfying this is finite.

  4. We can write a formula saying that there is no surjection from $x$ onto the collection of finite ordinals. In that case, $x$ is finite.

  5. We can write a formula saying that if $\cal U$ is a collection of subsets of $x$, then either $\cal U$ is empty, or it has a $\subseteq$-maximal element. In this case $x$ is finite (and the equivalence of this with the first definition does not use the axiom of choice!)

  6. We can write a formula saying that if $\cal U$ is a collection of subsets of $x$ which is linearly ordered by $\subseteq$, then either $\cal U$ is empty or it has a maximal element. In this case $x$ is finite (here we do make an appeal to the axiom of choice).

And there are other creative ways to define finiteness. But the point is that when working internally to set theory, we define finiteness as an internal notion, not as an external notion.

$\endgroup$
  • $\begingroup$ This is so awesome, thank you! My intent is to capture a proof of some other theories into set theory, and I ran into trouble when I got to something like 'Let $G$ be a finite group'. $\endgroup$ – Jonny Sep 18 '14 at 2:34
3
$\begingroup$

In set theory this might be expressed in a variety of ways.

Perhaps the simplest, most self-contained approach is to require a well-ordering of a set which is also a well-ordering if taken in the opposite direction. Finite sets have this property (by induction), and the converse is arguably then just a matter of definition. However the definition supports the usual uses of finiteness.

Alternatively one can develop a theory of ordinal numbers, and then define as finite those which are less than the first Dedekind-infinite ordinal, commonly called $\omega$. Finite sets more generally could then be those in 1-to-1 correspondence with a finite ordinal.

$\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.