Linked Lists, Ordered Pairs?

Question

I would like to model linked lists using set theory similar to that in Scheme and LISP.

There is a set theoretic definition of the ordered pair:

$p = \{\{a, 1\}, \{b, 2\}\}$

My question is how does one distinguish a value from a pointer to another list? Should I just use more types like $3$ for value and $4$ for pointer?

So in LISP:

$l= ((('a').()), (('c'.'d').()))$

In set theory beginning of above list:

$l = \{\{h, 1\}, \{i, 2\}\}$

$h = \{\{a, 1\}\}$

$a = \{\{b, 4\}\}$

$b = \{\{'a', 3\}\}$

Without distinguishing pointer from value I'm not sure how a distinction can be made.

Answer 1

Now that you have defined ordered pairs, you can do what LISP does: $\operatorname{NIL}$ is a list and if you have a list $l = (a, b)$ then $a$ is a value and $b$ is a list. Of course, lists can be used as value themselves.

For example, the list $(a.b.c)$ is defined to be the ordered pair $(a, (b, (c, \operatorname{NIL})))$.

Thus $$l = ((('a') . ()) . (('c' . 'd'). ()) = (x_1, (y_1, \operatorname{NIL}))$$ where : $$x_1 = (('a') . ()) = (x_2, NIL)$$ $$x_2 = ('a', \operatorname{NIL})$$ $$y_1 = (('c' . 'd') . ()) = (y_2, (\operatorname{NIL}, \operatorname{NIL}))$$ $$y_2 = (c . d) = ('c', ('d', \operatorname{NIL}))$$