Definitions of finiteness

Perhaps the most intuitive definition of finiteness as a property of sets is that a set {A} is finite if and only if its cardinality is a natural number. Unfortunately, the most intuitive definition of the natural numbers, at least to me, is that the natural numbers are the cardinalities of finite sets. Therefore, in order to define both of these notions properly, one of these definitions must be altered. I think the most natural one to alter is the definition of finiteness, since, at least to me, finiteness seems like a more fundamental notion than the notion of the natural numbers.

The alternative definition which I’m most satisfied with is Kuratowski’s, given below. The essential idea behind it is that finite sets are sets that can be formed from the empty set by making a finite number of adjoinments (i.e. additions of a single object). The formal statement may seem a little peculiar if you haven’t seen this kind of definition before.

Definition 1 For every set {A}, {A} is Kuratowski finite if and only if it is a member of every family {\mathcal F} of sets such that {\emptyset \in \mathcal F} and for every member {B} of {\mathcal F} and every object {x}, {B \cup \{x\} \in \mathcal F}.

The key thing to notice here is that it immediately follows from the definition that a variant of mathematical induction can be performed on Kuratowski finite sets. Suppose you wish to prove that every Kuratowski finite set has a certain property. Well, if you let {\mathcal F} be the family of all sets with the property, you can see from the definition that one way to do this is to show that {\emptyset} has the property (i.e. {\emptyset \in \mathcal F}) and that if you adjoin an object to a set with the property, it will still have the property (i.e. for every member {B} of {\mathcal F} and every object {x}, {B \cup \{x\} \in \mathcal F}). Definitions similar to the one above turn up in quite a few places in mathematics, and they are always associated with a principle of induction. For example, consider the definition of the subgroup generated by a subset {H} of a group {G}. The intuitive definition of this subgroup is that it is the set of all objects of the form {a_1 a_2 \dotsm a_n}, where {n} is a natural number and {a_1}, {a_2}, … and {a_n} are members of {H} or inverses of members of {H}. However, this definition can be awkward to work with and it is complex to state as a logical formula (it involves a quantification over all finite sets). Alternatively, one can define this subgroup as the intersection of all subgroups {H'} of {G} such that {H \subseteq H'}. The corresponding principle of induction is that if every member of {H} has a certain property, and the set of all members of the group with the property is a subgroup of {G}, then every member of the subgroup generated by {H} has the property too.

I should note that this definition is not possible in ZF: {\mathcal F} must be allowed to range over proper classes as well as sets, because for every possible value of {\mathcal F}, we have that for every object {x}, {\emptyset \cup \{x\} = \{x\} \in \mathcal F}, so {\mathcal F} is a superclass of the class of all singletons, which is proper by the axiom of replacement, since {x \in V \mapsto \{x\}} is an injection. Quantifiers can only range over sets in ZF. However, a minor amendment makes the definition possible in ZF: we can just require {x} to be a member of {A}. It can be proven that this amended definition (definition 2) is equivalent to the definition as stated above (definition 1).

Proof: Suppose {A} is a finite set by definition 2 and {\mathcal F} is a family of sets such that {\emptyset \in \mathcal F} and for every member {B} of {\mathcal F} and every object {x}, {B \cup \{x\} \in \mathcal F}. Every member {x} of {A} is an object, so for every member {B} of {\mathcal F}, {B \cup \{x\} \in \mathcal F}, which means {A} is a member of {\mathcal F} (by definition 2). Therefore, {A} is finite by definition 1 as well.

As for the converse, well, {\emptyset} is clearly finite by definition 2. Now, suppose {A} is a finite set by definition 2, {x} is an object and {\mathcal F} is a family of sets such that {\emptyset \in \mathcal F} and for every member {B} of {\mathcal F} and every member {y} of {A \cup \{x\}}, {B \cup \{y\} \in \mathcal F}. Since {A} is finite by definition 2, {A \in \mathcal F}, and since {x} is a member of {A \cup \{x\}}, that means {A \cup \{x\} \in \mathcal F}. Therefore, {A \cup \{x\}} is finite by definition 2 as well. It follows by the principle of induction on finite sets by definition 1 that every set which is finite by definition 1 is finite by definition 2 as well. \Box

The reason I’ve chosen definition 1 is that it is easier to see the idea behind the definition.

Of course, we must ensure that Kuratowski finiteness is actually equivalent to ordinary finiteness. Since we can induct over natural numbers and we can induct over Kuratowski finite sets, the proof is straightforward.

Proof: {|\emptyset| = 0 \in \mathbb N}. Suppose {A} is a finite set, {|A| = n} and {x} is an object. What is {|A \cup \{x\}|}? Well, there is a bijection {f} from {A} to {\{0, 1, \dotsc, n - 1\}}, and it is easy to see that the extension {g} of {f} to {A \cup \{x\}} such that {g(x) = n} is a bijection onto {\{0, 1, \dotsc, n\}}. Therefore, {|A \cup \{x\}|} is {n + 1}. This completes the proof that the cardinality of every Kuratowski finite set is a natural number, i.e., every Kuratowski finite set is finite.

The only set whose cardinality is 0 is {\emptyset}, which is Kuratowski finite. Suppose {n} is a natural number, every set whose cardinality is {n} is Kuratowski finite, {A} is a set and {|A| = n + 1}. Then there is a bijection {f} from {A} to {\{0, 1, \dotsc, n\}}. Let {x} be {f^{-1}(n)}. It is easy to see that the restriction {g} of {f} to {A \setminus \{x\}} is a bijection onto {\{0, 1, \dotsc, n - 1\}}, so {|A \setminus \{x\}| = n}. Therefore, {A \setminus \{x\}} is Kuratowski finite. It follows that {(A \setminus \{x\}) \cup \{x\} = A} is Kuratowski finite as well. This completes the proof that every finite set is Kuratowski finite. \Box

The other commonly-seen definition of finiteness is due to Dedekind. The main advantage of this definition is that it is somewhat simpler to state than Kuratowski’s.

Definition 2 For every set {A}, {A} is Dedekind finite if and only if for every proper subset {B} of {A}, {|B| < |A|}.

It is probably possible to prove that every finite set is Dedekind finite by induction, but an easer way to prove this is to prove the contrapositive, that every Dedekind infinite set is infinite. This proof uses the fact that for every set {A}, {A} is infinite if {\aleph_0 \le |A|} ({\aleph_0} is the cardinality of {\mathbb N}), since {n < \aleph_0} for every natural number {n}, so {|A| \ne n}.

Proof: Suppose {A} is a Dedekind infinite set, so there is a proper subset {B} of {A} such that {|A| = |B|}. Since {B \subset A}, there is a member {a} of {B \setminus A}; since {|A| = |B|}, there is a bijection {f} from {A} to {B}. Consider the infinite sequence {a}, {f(a)}, {f^2(a)}, … We can show by induction that this sequence is an injection, so {\aleph_0 \le |A|}, and therefore, since {\mathbb N} is infinite, {A} is infinite.

  • For every positive integer {n}, {f^n(a) = f(f^{n - 1}(a))}, so {f^n(a) \in B}, which means {a \ne f^n(a)} since {a \not \in B}.
  • Suppose {m} is an integer and for every integer {n} such that {m < n}, {f^m(a) \ne f^n(a)}. Then for every integer {n} such that {m + 1 < n}, {m < n - 1}, so {f^m(a) \ne f^{n - 1}(a)}, which means {f^{m + 1} \ne f^n(a)}, since {f} is bijective.

\Box

Now, if the converse of the fact we used holds, i.e. for every infinite set {A}, {\aleph_0 \le |A|}, then we can prove the converse: that every infinite set is Dedekind infinite. The proof relies on the fact that {\mathbb N} has the same cardinality as its proper subset {\{1, 2, 3, \dotsc\}}.

Proof: Suppose {A} is an infinite set. Then {\aleph_0 \le |A|}, so there is an injection {f} from {\mathbb N} to {A}. Let {B} be the image of {f} under {\{1, 2, 3, \dotsc\}}. Then {\aleph_0 \le |B|}, so {B} is infinite, but {B} is a proper subset of {A}, since {f(0) \not \in B}. \Box

The problem with Dedekind’s definition is that one runs into trouble when one tries to prove that for every infinite set {A}, {\aleph_0 \le |A|}, in ZF. The proof can be done easily using the axiom of choice.

Proof: Suppose {A} is an infinite set. If the axiom of choice holds, there is a function {f} on {\mathcal P(A) \setminus \{\emptyset\}} such that for every non-empty subset {B} of {A}, {f(B) \in B}. Let {g} be the sequence such that for every natural number {n}, {g(n) = f(A \setminus \{g(0), g(1), \dotsc, g(n - 1)\})} (this is always defined, because if {A \setminus \{g(0), g(1), \dotsc, g(n - 1)\} = \emptyset}, {A \subseteq \{g(0), g(1), \dotsc, g(n - 1)\}}, so {|A| \le n}, which means {A} is finite). It is clear that {g} is an injection into {A}, so {\aleph_0 \le |A|}. \Box

This doesn’t necessarily mean that the statement is independent of ZF, but certainly it suggests the possibility, since there is no obvious way to amend this proof so that it does not require the axiom of choice.

Perhaps there is another way we could prove that every infinite set is Dedekind infinite? Unfortunately there isn’t, because if every finite set is Dedekind infinite, then for every infinite set {A}, there is a proper subset {B} of {A} such that {|A| = |B|}, so there is a member of {A \setminus B}, and {B} is infinite too, so there is a proper subset {C} of {B} such that {|B| = |C|}, so there is a member of {B \setminus C}, and so on. This allows us to construct an injective sequence of members of {A}, so {\aleph_0 \le |A|}.

Ideally, I would finish off here with a proof that the statement is independent. Unfortunately, I don’t know how to do this. It may be possible to derive the axiom of choice from the fact that every infinite set is Dedekind infinite, in which case this fact cannot be a theorem of ZF (otherwise the axiom of choice would be a theorem of ZF, and the axiom of choice is known to be independent of ZF). On the other hand, this may not be true, in which case I’m not sure what the best way to prove independence would be. The most straightforward way would be to construct a model of ZF in which there are Dedekind finite infinite sets, but I don’t know how you might go about doing that.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s