# Constructing lists from Ordered Pairs

I've been searching online for a way of constructing lists from sets, but to no avail. However, I am aware of how to define ordered pairs and, more generally, ordered n-tuples from sets. My first preference being the Kuratowski definition:

$$(a, b) := \big\lbrace\lbrace a\rbrace, \lbrace a,b\rbrace \big\rbrace$$

As I'm sure you are all aware, ordered pairs can then be used to define Cartesian products. Using Cartesian products, I believe I've find out how to construct/define lists using sets. It's essentially just repeated Cartesian products with sets containing only one constant member. E.g.

$$[10, 3, \emptyset] := \lbrace 10 \rbrace \times \lbrace 3 \rbrace \times \lbrace \emptyset \rbrace$$

What I'm stuck on is how to represent the list as a single set for any given number of members. For three members I'm guessing

$$[a,b,c] := \Big\lbrace \big\lbrace\big\lbrace \lbrace a \rbrace, \lbrace a,b \rbrace \big\rbrace \big\rbrace, \big\lbrace \big\lbrace\lbrace a\rbrace, \lbrace a,b\rbrace \big\rbrace, c \big\rbrace \Big\rbrace$$

based on the idea that $$(a,b) \times \lbrace c \rbrace = ((a,b),c)$$. If you're having difficulty understanding the repeated nested braces, I recommend replacing the ordered pair $$(a,b)$$ with some unused, arbitrary symbol, e.g. $$x$$, figure out the ordered triplet as an ordered pair of $$x$$ and $$c$$, then use substitution to replace the arbitrary letter with the ordered pair.

Just to be clear, I'm using the following definition of list: an ordered collection of well-defined objects.

Two questions:

1. Am I correct?
2. How does one define a list in terms of sets for any arbitrary number of members of that list?

## 1 Answer

The most commonly used convention is to define the natural numbers first and then say that a list is a function whose domain is an initial (finite) segment of the naturals. Then,

$$[a,b,c] = \{(0,a), (1,b), (2,c)\}$$

(This is convenient in set theory, e.g., because it lets you prove without Replacement that if $$A$$ is a set, then there is a set of all lists of elements from $$A$$).

If this is not to your liking you might also take a page from Lisp and represent the empty list as $$\varnothing$$, and a non-empty list as the ordered pair of the first element and the representation of the rest of the list:

$$[a,b,c] = (a,(b,(c,\varnothing)))$$

(This works because $$\varnothing$$ cannot be a Kuratowski pair).

• To add two small notes to this answer: 1. Another convention is to encode the length of the list as its first element, i.e. $[a, b, c] = (3, (a, (b, c)))$ -- with "special" case $[] = \emptyset$. 2. Ultimately it generally doesn't matter how you define this thing exactly, as there are bijections that are fiddly but not ultimately hard to write down directly. – Mees de Vries Jan 9 at 13:56