From mboxrd@z Thu Jan  1 00:00:00 1970
X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/2188
Path: news.gmane.org!not-for-mail
From: <jvoosten@math.uu.nl>
Newsgroups: gmane.science.mathematics.categories
Subject: Re:  Realizability and Partial Combinatory Algebras
Date: Tue, 18 Feb 2003 12:48:48 +0100 (CET)
Message-ID: <200302181148.MAA14451@kodder.math.uu.nl>
NNTP-Posting-Host: main.gmane.org
X-Trace: ger.gmane.org 1241018476 2933 80.91.229.2 (29 Apr 2009 15:21:16 GMT)
X-Complaints-To: usenet@ger.gmane.org
NNTP-Posting-Date: Wed, 29 Apr 2009 15:21:16 +0000 (UTC)
To: categories@mta.ca
Original-X-From: rrosebru@mta.ca Thu Feb 20 12:23:40 2003 -0400
Return-path: <cat-dist@mta.ca>
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 20 Feb 2003 12:23:40 -0400
Original-Received: from Majordom by mailserv.mta.ca with local (Exim 4.10)
	id 18ltSL-0006Lp-00
	for categories-list@mta.ca; Thu, 20 Feb 2003 12:21:53 -0400
X-Sun-Charset: US-ASCII
X-Virus-Scanned: by AMaViS snapshot-20020300
Original-Sender: cat-dist@mta.ca
Precedence: bulk
X-Keywords: 
X-UID: 44
Original-Lines: 32
Xref: news.gmane.org gmane.science.mathematics.categories:2188
Archived-At: <http://permalink.gmane.org/gmane.science.mathematics.categories/2188>

Dear John,

> Note that we can find elements if,true,false \in A satisfying
> 	if true x y = x, 	if false x y = y,
> and furthermore we can arrange that true = k.
> (I'll use "if then else" syntax below).
> We want to construct S such that (in A),
>      Skxkykz ~ (xkz)k(ykz), and Skxky is always defined.
> Take S to be
> 	\lambda txuyvz. if v then (xkz)k(ykz) else false
> using the usual Curry translation of lambda terms. To see that
> Skxky is always defined, note that, provably, Skxky(false)z = false.

There is a point I don't understand. If I work out Skxky, then I find
a term which contains subterms of the form xk, yk. So how can this be
defined if x or y represent nowhere defined functions?

It looks to me, that you are using a form of Combinatorial Completeness
that is not valid with the weaker S-axiom. If I am correct, one has
the following form of Combinatorial Completeness:

For every term t and variable z, there is a term \lambda z.t with the
property:

If \lambda z.t is defined, then for each a, (\lambda z.t)a ~ t[a/z]

(of course, a really correct version has more than one variable)

Best, Jaap