COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Who first realized that n-tuples can be emulated as nested 2-tuples?

• Email
• Follow

```Some time long before Lisp and lambda-calculus were invented,
before even the first computer was invented, probably before there
was even the concept of how a automatic digital computer might be
designed, there must have been a formal invention/definition of
fixed-sized ordered lists (tuples), and the realization that tuples
of size larger than 2 can be emulated as nested 2-tuples. For
example:
<a b c> emulated as <a <b c>>
<a b c d> emulated as <a <b <c d>>>
This of course, translated from formal "nesting" to operational
"objects" and "pointers", is the basis of Lisp emulating lists as
CDR-chained CONS-cells, and likewise standard libraries in just
about any programming language that equate arbitrary trees and
binary trees via the same mapping.

So I'm curious: Who was that very first mathematician to publish
(or write in a letter that is documented) this essential concept?
```
 0

See related articles to this posting

```seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) writes:
><a b c> emulated as <a <b c>>

This �emulation� is not perfect. For example, by this
�emulation�, the following assertions are true:

�<a b c> is a 2-tuple.�
�The second component of <a b c> is <b c>.�

>So I'm curious: Who was that very first mathematician to publish
>(or write in a letter that is documented) this essential concept?

I know that Kuratowski came up with the representation of the

However, not all mathematicians use this definition, some
also use tuples as entities different from sets IIRC. And
thus, I assume, that also some will use 3-tuples that are
/not/ 2-tuples.

```
 0
Reply ram (2987) 9/17/2009 1:05:01 PM

```Stefan Ram wrote:
> seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) writes:
>> <a b c> emulated as <a <b c>>
>
>   This �emulation� is not perfect. For example, by this
>   �emulation�, the following assertions are true:
>
>       �<a b c> is a 2-tuple.�
>       �The second component of <a b c> is <b c>.�

Another way in which the emulation is not perfect: indexed access is
O(n) instead of O(1) (or with a balanced binary tree of pairs, O(log n)
```
 0
Reply searles (445) 9/17/2009 1:10:48 PM

```On Sep 17, 3:38=A0pm, seeWebInst...@rem.intarweb.org (Robert Maas,
http://tinyurl.com/uh3t) wrote:
> Some time long before Lisp and lambda-calculus were invented,
> before even the first computer was invented, probably before there
> was even the concept of how a automatic digital computer might be
> designed, there must have been a formal invention/definition of
> fixed-sized ordered lists (tuples), and the realization that tuples
> of size larger than 2 can be emulated as nested 2-tuples. For
> example:
> =A0 <a b c> emulated as <a <b c>>
> =A0 <a b c d> emulated as <a <b <c d>>>
> This of course, translated from formal "nesting" to operational
> "objects" and "pointers", is the basis of Lisp emulating lists as
> CDR-chained CONS-cells, and likewise standard libraries in just
> about any programming language that equate arbitrary trees and
> binary trees via the same mapping.
>
> So I'm curious: Who was that very first mathematician to publish
> (or write in a letter that is documented) this essential concept?

Ancient Greek philosophers "knew" about the one and the many, and I
think CONS (the glue that ties two items together) comes down to this
concept. This doesn't answer your question but I don't think there's a
meaningful answer to your question, as this is a concept humans apply
to their daily life, so presumably, it was realized en masse a long
time ago. If some mathematician has used this concept to prove
something, I wouldn't know about that either.
```
 0
Reply vippstar (1211) 9/17/2009 3:25:52 PM

```seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) writes:
>
> Some time long before Lisp and lambda-calculus were invented,
> before even the first computer was invented, probably before there
> was even the concept of how a automatic digital computer might be
> designed, there must have been a formal invention/definition of
> fixed-sized ordered lists (tuples), and the realization that tuples
> of size larger than 2 can be emulated as nested 2-tuples. For
> example:
>   <a b c> emulated as <a <b c>>
>   <a b c d> emulated as <a <b <c d>>>
> This of course, translated from formal "nesting" to operational
> "objects" and "pointers", is the basis of Lisp emulating lists as
> CDR-chained CONS-cells, and likewise standard libraries in just
> about any programming language that equate arbitrary trees and
> binary trees via the same mapping.
>
> So I'm curious: Who was that very first mathematician to publish
> (or write in a letter that is documented) this essential concept?

It may be Peano, who first realized the importance of pairing.
See below from one of my prior sci.math posts, see esp [1]

It wasn't until the much later development of set-theory that
the fundamental nature of the pairing construction was explicitly
realized. Indeed, as Kanamori wrote on p.289 (17) of [1] in
his interesting article on the history of set theory:

In 1897 Peano explicitly formulated the ordered pair using
"(x;y)" and moreover raised the two main points about the
ordered pair: First, equation 18 of his Definitions stated
the instrumental property which is all that is required of
the ordered pair:

(x,y) = (a,b)  iff  x = a and y = b

Second, he broached the possibility of reducibility, writing:
"The idea of a pair is fundamental, i.e., we do not know how
to express it using the preceding symbols."

--Bill Dubuque

[1] Akihiro Kanamori. The Empty Set, the Singleton, and the Ordered Pair
The Bulletin of Symbolic Logic, Vol. 9, No. 3. (Sep., 2003), pp. 273-298.
PS  http://www.math.ucla.edu/~asl/bsl/0903/0903-001.ps
PDF http://ifile.it/87wb214
```
 0
Reply wgd (8) 9/17/2009 5:51:51 PM

```Bill Dubuque <wgd@nestle.csail.mit.edu> writes:
>"The idea of a pair is fundamental, i.e., we do not know how
>to express it using the preceding symbols."

Kuratowskis attempt was already mentioned. (It has problems,
such as identities between certain sets and pairs that one
might not want to be the same.)

Another later means to define a pair is the �product� in
category theory. See

http://reperiendi.wordpress.com/2007/09/19/the-problem-of-evil-and-cartesian-categories/

```
 0
Reply ram (2987) 9/17/2009 6:07:37 PM

```ram@zedat.fu-berlin.de (Stefan Ram) wrote:
>
>BD <wgd@nestle.csail.mit.edu> writes:
>>"The idea of a pair is fundamental, i.e., we do not
>>know how to express it using the preceding symbols."

The above was written by Kanamori, quoting Peano.
Please learn how to quote properly.
```
 0
Reply BD228 (1) 9/17/2009 6:21:13 PM

```On Thu, 17 Sep 2009 05:38:09 -0700, seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) said:
> ...
> there must have been a formal invention/definition of
> fixed-sized ordered lists (tuples), and the realization that tuples
> of size larger than 2 can be emulated as nested 2-tuples. For
> example:
>   <a b c> emulated as <a <b c>>
>   <a b c d> emulated as <a <b <c d>>>
> ...
> So I'm curious: Who was that very first mathematician to publish
> (or write in a letter that is documented) this essential concept?

I believe any historical analysis of this should also include how,
in combinatorial calculus,

(a) if t_1 and t_2 are terms, then (t_1 t_2) is also a term,

and

(b) by convention, some parentheses can be omitted.

By the way, isn't the usual mathematical definition of an n-tuple a
mapping whose domain is {1, ..., n}, which, of course, is based on
pairs, but in a completely different way?

---Vassil.

--
"Even when the muse is posting on Usenet, Alexander Sergeevich?"
```
 0
Reply vnikolov1 (276) 9/18/2009 3:39:14 AM

```Vassil Nikolov <vnikolov@pobox.com> writes:
>By the way, isn't the usual mathematical definition of an n-tuple a
>mapping whose domain is {1, ..., n}, which, of course, is based on
>pairs, but in a completely different way?

Such a mapping is an �family�.

http://en.wikipedia.org/wiki/Indexed_family

```
 0
Reply ram (2987) 9/18/2009 8:11:14 AM

```ram@zedat.fu-berlin.de (Stefan Ram) writes:
>http://en.wikipedia.org/wiki/Indexed_family

�An n-tuple is a family indexed by n�

But I do not agree with this.

I only grant that there is an �isomorphism� between
n-tuples and families indexed by n.

```
 0
Reply ram (2987) 9/18/2009 8:14:16 AM

```On 17 Set, 14:38, seeWebInst...@rem.intarweb.org (Robert Maas,
http://tinyurl.com/uh3t) wrote:
> ..I'm curious: Who was that very first..

He tupled himself with his assigned wife, to make the primary CAR of
all the CARs and CDRs following...

It's all in the Bible, which is nothing else than concentrated wisdom,
which is nothing else than concentrated intelligence, which is nothing
else than deeply knowing human hearts and souls, which is not possible
to be discovered by humans themselves, therefore the need of
Revelation.

Got it? I thought so.

(And now you have enough stuff to meditate over the weekend.)
```
 0
Reply java.oke (196) 9/19/2009 12:33:33 PM

10 Replies
36 Views

Similar Articles

12/5/2013 2:54:27 AM
[PageSpeed]