A question that troubles me:
Is there any obvious way to unambiguously record the following three values in a binary relation (ie, a two-column table)?
1. A
2. (A . nil)
3. (A . B)
for any sensible A and B (ie, finite values, but including both atoms and finite structures, ie sets/pairs/tables).
The naive idea, and the one that I think Dave Childs proposed in Extended Set Theory, is to record 'A' as (A . nil)
But as you can see, that doesn't work, because 2.
@natecull Sorry, would you mind explaining the notation? What does the dot mean?
@ayy An ordered pair, expressed in Lisp cons notation.
You could replace (A . B) with <A , B> if that helps make the meaning clear.
@ayy I mean the naive way of mapping an ordered pair onto two columns in a row would be to put the first element of the ordered pair in the first column and the second element in the second column.
And that would be sensible, except that you also have to account for how to represent the case of A, which is not an ordered pair but an single atomic value.
No, you don't get to say 'everything must be ordered pairs'. It is required that both atomic values and ordered pairs be unambiguously stored.
@ayy ... the complicating factor is that any value you put in any cell also has to, itself, be storable.
Ie, unrepresentable values are not a solution.
@ayy This is quite possibly impossible.
But if it is impossible, then that fact itself seems to have interesting implications for computer science which don't seem to be fully appreciated.
@natecull This seems similar to the problem of an escape character. Just let it escape itself. So a literal nil is transformed into (nil . nil)
Although maybe I'm misunderstanding the problem.
@ayy Right, so that's what at first I thought you could do: second column = nil means 'just the value in the first column'. Therefore (nil . nil) == just nil.
But that breaks down if you ask the query 'what is in the second column of A'. You will get a table with one row, ie one pair, '(nil . nil)' .
which is wrong because that's the answer for (A . nil), not A.
So it looks like we need a NULL value to be distinguished from NIL. And then things start to get tricky.
@natecull If B is a property of the object (or column in a DB table), in case 1 it's null. If you just have lists of stuff, Pythonic lists [A], [A, null], [A, B] represent those cases.
Have you read William Kent's Data & Reality? It deals with how unknowable things should be modelled.
@natecull well, for the first one the second column is uninhabited. So you either encode that with a distinguished (meta?) value, or you can't do it. And nil is the historical non-meta distinguished value. Is this not related to SQL NULL?
@alanz @ayy @mdhughes Yes, as a first approach I think a value of NULL (ie missing value) which is distinguishable from NIL (ie the empty set/relation) helps.
The question then becomes is NULL well-behaved. It probably acts like SQL NULL, which is unfortunate, because possibly NULL != NULL.
Let A == (A . NULL)
Then if we ask 'what are the contents of A' (ie what is in its right-column), we get:
{ (NULL . NULL) , (NIL . NULL), (B . NULL) }
And I wonder if that's fully consistent.
@natecull If you have separate symbols/concepts for "false", "unknown", "zero", "doesn't exist" and "end of list" instead of overloading the concept of "nil" then I think you can make it work.
@natecull I'm reminded of the distinction between zero and nothing.
https://books.google.com/books?id=i1vcZqkgIrgC&pg=PA77&lpg=PA77&dq=%22that's+zero%22+%22that's+nothing%22&source=bl&ots=ZCfY9ShDOQ&sig=zekbICSh62qNFunqkP-huEeNI08&hl=en&ei=hZmeTOiaG4zksQO95fzVAQ&sa=X&oi=book_result&ct=result&resnum=1&sqi=2&ved=0CBIQ6AEwAA#v=onepage&q=%22that's%20zero%22%20%22that's%20nothing%22&f=false
The troubling part isn't this question itself.
It's why nobody else seems to have asked it, when it seems so important.