The Kuratowski definition of sequences

Sequences are one of the most fundamental kinds of objects dealt with in mathematics, along with sets, relations and functions. The standard definition of sequences is that they are simply functions on an ordered domain. Although this definition is quite nice and simple, it has a couple of flaws. First of all, it doesn’t capture the intuition most people have that a sequence is a kind of object which is ontologically distinct from a function. Secondly, the usual way to formally define a function in set theory is as a set of ordered pairs in which no two members are of the form (a, b) and (a, c) unless b = c. In order to use this definition, we have to define what an ordered pair is first. An ordered pair is simply the simplest kind of sequence; we would like to be able to define it as a function on a set of order type 2, but this is impossible if we haven’t already defined what a function is. Therefore, we have to define an ordered pair in some other way, which means ordered pairs are ontologically distinct from all other kinds of sequence, and that seems very untidy.

The standard definition of ordered pairs in set theory is credited to Kuratowski. By this definition, (a, b) is simply {{a}, {a, b}}. The intersection of the pair is then {a}, while its union is {a, b}, so its first term can be defined as the unique member of its intersection and its second term can be defined as the unique member of its union other than the first term. Well, actually the definition of the second term isn’t quite right. If the first term and the second term are the same, the union of the pair will have no members other than the first term. So the proper definition of the second term is that it is the unique member of the union, or, if there is more than one member of the union, the one which is not the first term.

This complication is the reason why the Kuratowski definition can’t be generalised to finite sequences of greater length. Suppose we made the following definition.

Definition 1 For every natural number n and every collection of n objects x0, x1, … and xn – 1, the sequence of length n whose terms are x0, x1, … and xn – 1 (in that order) is {{x0}, {x0, x1}, …, {x0, x1, …, xn – 1}}.

This would be fine if we only needed to deal with sequences whose terms are all distinct (i.e. injective sequences, if you view sequences as functions). But by this definition, the sequences (a, a and (a, a, a) would be identical: they would both just be (a). Similarly, and more seriously, perhaps, because the sequences are the same length, the sequences (a, b, a) and (a, b, b) would be identical: they would both just be (a, b). In general, you can remove duplicates from sequences defined this way just as you can with sets. The only reason the Kuratowski definition works for ordered pairs is that (a, a), which simplifies to (a), can be distinguished from the set {a}.

For this reason, I’m not really a fan of the Kuratowski definition. Another way of defining the ordered pair is somewhat similar to defining it as a function on a set of order type 2. We can define (a, b) simply as {{0, a}, {1, b}}. This is just as if it was a function on {0, 1}, save that the pairs are unordered. The first term of the pair can be defined as the unique object a such that {0, a} is a member of the pair. The second term of the pair can be defined as the unique object b such that {1, b} is a member of the pair. Unfortunately, we run into similar problems as we had with the Kuratowski definition if we try and extend this idea to define sequences of greater length. For example, we would have (1, 2, 0) = {{0, 1}, {1, 2}, {2, 0}} and (2, 0, 1) = {{0, 2}, {1, 0}, {2, 1}}, and these two sets are identical.

The problem is that the indices (0 and 1 in this case) need to be distinct from the terms in order for the definition to work. The solution, then, would be to find some way of making the indices always distinct. Anyway, today I had a shower thought about one possible solution.

Recall Von Neumann’s definition of the ordinals, in which each ordinal is defined as the set of all preceding ordinals. Let’s make a slight modification to this definition. Let ζ be an arbitrary object.

Definition 2 Ωa, whose members are called the ζ-ordinals, is the intersection of all the sets S such that the following three conditions are satisfied.

  • ζS.
  • For every member ζ of S, ζ ∪ {ζ} ∈ S.
  • For every subset T of S, the union of all the members of T is a member of S.

It’s just like the usual Von Neumann definition of the ordinals, except that we use ζ in place of the empty set. As long a is a well-founded set, these ordinals are, I think, isomorphic to the ordinary ordinals. Be warned that I haven’t checked this (I may do so tomorrow). If this is the case, we can make the following definition.

Definition 2 A sequence is a set of the form {0x0, 1x1, …, (n – 1)xn – 1}, where n is an ordinal called the length of the sequence and x0, x1, … and xn – 1 are objects called the terms of the sequence.

I suspect there may be problems with this definition too. Maybe it can be amended to make it work, but I’m going to have to leave this for some other day.

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