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?

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).

  • 1
    $\begingroup$ 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. $\endgroup$ – Mees de Vries Jan 9 at 13:56

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.