🚀 go-pugleaf

In article <1992Sep29.161016.19533@ghost.dsi.unimi.it> chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) writes:
>A question for Recursion Theorists.
>
>If you take a partial recursive function phi and two sets I and J such that
> dom(phi) contains I and range(phi) is included in J, you can define an
> obvious set-theoretic function f:I->J.
>
>The question is: does EVERY surjective f admit a section, i.e. a g:J->I
> obtained in the same way from a partial recursive function, say psi, such
> that
>	for each j in J    f(g(j))=j       ?
>
>People-who-know will see I'm actually defining a category and asking "does
> every good (i.e surjective) epi split?"
>
>I suspect this to be false, but I can't manage to find a counter-example; the
> difficulties arise from the clumsiness of restricting arbitrarily the domain
> of a partial recursive function.

Thanks for the nice problem.  If I is recursively enumerable, there is
such a section.  In general, there is not, by the following finite-injury
priority argument.

Let f be the left projection function for some pairing function.
Let J be the set of natural numbers.

Note: the range of f is N, so the range of any section of f must be infinite.

We construct I by deleting elements from N; note that this makes I co-r.e.
In the construction, we will refer to certain requirements R_i:

R_i: range phi_i is finite or there is y in N such that phi_i(y) not in I.

We will also restrain some numbers into I for certain requirements.  These
restraints can be broken for higher-priority (lower-numbered) requirements,
but the standard finite-injury argument will establish that every requirement
gets met.

Stage s:
   Search for s steps for i such that requirement i is not met, and there
   are x,y such that phi_i(x) = y, f(y)=x, and y is not held in I for any
   requirement i'<i.  Let i0 be the least i so found; let x0 and y0 be
   corresponding values of x and y.

   Delete y from I.
   Find y'>y, not yet deleted from I (there will always be such), and
   restrain y' into I for requirement i0.

   Mark requirement i0 as being met.
   Unmark all requirements i with i>i0.
End state s.

I will leave the verification up to the reader.  The basic structure of
the proof is that every requirement will be met, either by default
(phi_i has finite range) or by being met in the construction.  The
latter will happen to each requirement at most a finite number of times
(2^(i-1) will do it).  Then note that meeting every requirement is enough
to establish that f|I has no section.

Mark
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu

In a previous article, chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) says:

>A question for Recursion Theorists.
>
>If you take a partial recursive function phi and two sets I and J such that
> dom(phi) contains I and range(phi) is included in J, you can define an
> obvious set-theoretic function f:I->J.
>
>The question is: does EVERY surjective f admit a section, i.e. a g:J->I
> obtained in the same way from a partial recursive function, say psi, such
> that
>	for each j in J    f(g(j))=j       ?
>
>People-who-know will see I'm actually defining a category and asking "does
> every good (i.e surjective) epi split?"
>
>I suspect this to be false, but I can't manage to find a counter-example; the
> difficulties arise from the clumsiness of restricting arbitrarily the domain
> of a partial recursive function.
>

	Surely it is true, unless I misunderstaood the question.  Given 
sets I and J and a partial recursive psi that maps I onto J here is an
algorithm for a section g:

	to find gn for n in J, start evaluating psi for each m in I.
Of course you can not just start with the first m in I and evaluate 
psi for it, since psi might be undefined for it.  So take a few steps 
on the first element of I, then a few on the second, then a few more 
on the first, a few more on the second and a few on the third, then a
few more on the first....  This way we would eventually find the value 
of psi for each element of I where it is defined.  Since psi maps I 
onto J we will eventually finish evaluating psi on some element of I 
that gives n.  Define gn to be that element.  

	This algorithm may work for values of n not in J.  Indeed
it can not be defined precisely on J unless J is r.e.  But it is
defined for all of J.

Colin McLarty 

In article <1aaaouINN9vp@usenet.INS.CWRU.Edu> cxm7@po.CWRU.Edu (Colin Mclarty) writes:
>
>In a previous article, chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) says:
>> (read earlier article for problem.)
>	to find gn for n in J, start evaluating psi for each m in I.
>Of course you can not just start with the first m in I and evaluate 
>psi for it, since psi might be undefined for it.  So take a few steps 
>on the first element of I, then a few on the second, then a few more 
>on the first, a few more on the second and a few on the third, then a
>few more on the first....  This way we would eventually find the value 
>of psi for each element of I where it is defined.  Since psi maps I 
>onto J we will eventually finish evaluating psi on some element of I 
>that gives n.  Define gn to be that element.  

This argument requires that I be r.e.  Otherwise, one could not
carry out the first step: ``start evaluating psi for each m in I''.
A little thought indicates that failing to exclude N-I from the
computation can lead to failure.  In fact, it is easy to construct
co-r.e. I satisfying chinnici's conjecture; see my earlier post.

Mark
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu

My previous post on this matter was poorly worded, and contained some
mistakes in the presentation of the proof.  Herewith an improvement:

Let f be the left projection function for some pairing function.
Let J be the set of natural numbers.

We construct I by deleting elements from N; note that this makes I co-r.e.
In the construction, we will refer to certain requirements R_i:

R_i: range phi_i is finite or there is y in N such that phi_i(y) not in I.

We will also restrain some numbers into I for requirements R_i.  These
restraints can be broken for higher-priority (lower-numbered) requirements,
but the standard finite-injury argument will establish that every requirement
gets met.  The point of these restraints is that the range of f restricted
to I (f|I) will still be N; this forces any section of f|I to have an
infinite range, since a section must be in injection.

Stage s:

   Search for s steps for all i such that: requirement i is not met,
   and there are x,y such that phi_i(x) = y, f(y)=x, and y is not
   restrained into I for any requirement i'<i.

   Let i0 be the least such i found; let x0 and y0 be corresponding
   values of x and y.

   Delete y0 from I.

   find y'>y0 such that y' has not yet been deleted from I, and such that
   f(y') = f(y0) = x0, 

   Mark requirement i0 as being met.

   For all requirements i>i0 that are marked as met, remove the mark
   (that is, start treating them as unmet).

End stage s.

I will leave the verification up to the reader.  The basic structure of
the proof is that every requirement will be met, either by default
(phi_i has finite range) or by being met in the construction.  The
latter will happen to each requirement at most a finite number of times
(2^(i-1) will do it).  Then note that meeting every requirement is enough
to establish that f|I has no section.

Mark
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu

In article <1992Sep30.140356.9401@cs.rochester.edu> fulk@cs.rochester.edu (Mark Fulk) writes:
>My previous post on this matter was poorly worded, and contained some
>mistakes in the presentation of the proof.  Herewith an improvement:

Wherein I still left a gap.

>Let f be the left projection function for some pairing function.
>Let J be the set of natural numbers.
>
>We construct I by deleting elements from N; note that this makes I co-r.e.
>In the construction, we will refer to certain requirements R_i:
>
>R_i: range phi_i is finite or there is y in N such that phi_i(y) not in I.
>
>We will also restrain some numbers into I for requirements R_i.  These
>restraints can be broken for higher-priority (lower-numbered) requirements,
>but the standard finite-injury argument will establish that every requirement
>gets met.  The point of these restraints is that the range of f restricted
>to I (f|I) will still be N; this forces any section of f|I to have an
>infinite range, since a section must be in injection.
>
>Stage s:
>
>   Search for s steps for all i such that: requirement i is not met,
>   and there are x,y such that phi_i(x) = y, f(y)=x, and y is not
>   restrained into I for any requirement i'<i.
>
>   Let i0 be the least such i found; let x0 and y0 be corresponding
>   values of x and y.
>
>   Delete y0 from I.
>
>   find y'>y0 such that y' has not yet been deleted from I, and such that
>   f(y') = f(y0) = x0, 

and restrain y' into I for requirement i0.

>
>   Mark requirement i0 as being met.
>
>   For all requirements i>i0 that are marked as met, remove the mark
>   (that is, start treating them as unmet).
>
>End stage s.
>
>I will leave the verification up to the reader.  The basic structure of
>the proof is that every requirement will be met, either by default
>(phi_i has finite range) or by being met in the construction.  The
>latter will happen to each requirement at most a finite number of times
>(2^(i-1) will do it).  Then note that meeting every requirement is enough
>to establish that f|I has no section.
>
>Mark
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu

In a previous article, fulk@cs.rochester.edu (Mark Fulk) says:

>In article <1992Sep29.161016.19533@ghost.dsi.unimi.it> chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) writes:
>>A question for Recursion Theorists.
>>
>>If you take a partial recursive function phi and two sets I and J such that
>> dom(phi) contains I and range(phi) is included in J, you can define an
>> obvious set-theoretic function f:I->J.
>>
>>The question is: does EVERY surjective f admit a section, i.e. a g:J->I
>> obtained in the same way from a partial recursive function, say psi, such
>> that
>>	for each j in J    f(g(j))=j       ?
>>
>
>Thanks for the nice problem.  If I is recursively enumerable, there is
>such a section.  In general, there is not, 

	Well, I walked right into that one (with my alleged algorithm
for findng the section, which began by sneaking in an enumeration 
of I).

Colin McLarty

	I am not an expert in set theory or the predicate
calculus, but I was leafing through a book on the subject and the
following informal "proof" occured to me.  Could any of you experts out
there tell me if this contains a major flaw -- and if so, what it
is?  Thanks.

	The proposition to be proven is: A set can never contain
itself as a member.
	Suppose X is an arbitrary set which contains itself as a
member.  All other members within the set can be symbolized as
'g'; therefore,

		X = {g,X}		(1)

(Of course, g may be the empty set.)
	Eq. 1 can be expanded as follows:

		X = {g, X'}
		        /\
		       {g,X''}
		          /\
			 {g,X'''}

...and so on forever.  (The ' symbol is merely meant to
distinguish an X of one iteration from that of another.)  X'',
for example, is equivalent to {g,X'''}; X''' is equivalent to
{g,X''''}, etc etc.
	The number of X's below X'' is infinite; nonetheless, it
is certainly true that X' contains X'' as well as all the X's
contained by X''; therefore X' contains one more X than X''!  It
follows that X' != X'', for X' contains an X not contained in X''. 
By the same reasoning, X != X', because X contains one more X
than does X'.  Therefore, for any arbitrary set X, X cannot
contain itself as a member.

Steve

In article <Oct05.201328.96457@yuma.ACNS.ColoState.EDU> sa114984@longs.lance.colostate.edu
(Steven Arnold) writes:

>	I am not an expert in set theory or the predicate
>calculus, but I was leafing through a book on the subject and the
>following informal "proof" occured to me.  Could any of you experts out
>there tell me if this contains a major flaw -- and if so, what it
>is?  Thanks.
>
>	The proposition to be proven is: A set can never contain
>itself as a member.
>	Suppose X is an arbitrary set which contains itself as a
>member.  All other members within the set can be symbolized as
>'g'; therefore,
>
>		X = {g,X}		(1)
>
>(Of course, g may be the empty set.)
>	Eq. 1 can be expanded as follows:
>
>		X = {g, X'}
>		        /\
>		       {g,X''}
>		          /\
>			 {g,X'''}
>
>...and so on forever.  (The ' symbol is merely meant to
>distinguish an X of one iteration from that of another.)  X'',
>for example, is equivalent to {g,X'''}; X''' is equivalent to
>{g,X''''}, etc etc.
>	The number of X's below X'' is infinite; nonetheless, it
>is certainly true that X' contains X'' as well as all the X's
>contained by X''; therefore X' contains one more X than X''!  It
>follows that X' != X'', for X' contains an X not contained in X''. 
>By the same reasoning, X != X', because X contains one more X
>than does X'.  Therefore, for any arbitrary set X, X cannot
>contain itself as a member.
>
>Steve

What you have just described is, I believe, what is called the
`unfolding' of the set x={x}.  It is a typical non-well-founded set.
A _non-well-founded set_ is a set that need not have an epsilon-minimal
element.  There will exist an infinite "descending" chain of the
epsilon-relation.  This is why it is called a non-well-founded set.  It
is not built out of pre-existing elements. The set x={x} can also be
represented by an infinite tree with a set assigned to each node.  
It would look like this, with an arrow indicating membership.

x-->x-->x-->x-->...

The existence of non-well-founded sets can be made into an axiom, the
Anti Foundation Axiom (AFA).  The resulting theory is very interesting
mathematically and has practical and theoretical applications.  See

Peter Aczel, _Non-Well-Founded Sets_.  CSLI Lecture Notes 14, (1988).

-- 
Marko Amnell
amnell@klaava.helsinki.fi
Graduate Student in Philosophy

In article <Oct05.201328.96457@yuma.ACNS.ColoState.EDU>, sa114984@longs.lance.colostate.edu (Steven Arnold) writes:
> [...some of proof deleted...]
>
>		X = {g,X}		(1)
>
>(Of course, g may be the empty set.)
>	Eq. 1 can be expanded as follows:
>
>		X = {g, X'}
>		        /\
>		       {g,X''}
>		          /\
>			 {g,X'''}
>
>...and so on forever.  (The ' symbol is merely meant to
>distinguish an X of one iteration from that of another.)  X'',
>for example, is equivalent to {g,X'''}; X''' is equivalent to
>{g,X''''}, etc etc.
>	The number of X's below X'' is infinite; nonetheless, it
>is certainly true that X' contains X'' as well as all the X's
>contained by X''; therefore X' contains one more X than X''!  It [...]

(I'm ignoring the fact that g should not be a single element, for we could
quite easily replace it by g1,...,gn with out affecting the rest.)

I think one mistake you've made here (and unfortunately it only takes one
to render a proof invalid :-) is saying:
	X' contains X'' as well as all the X's contained by X''
If we expand X (partially) using formal notation rather than your tree
diagram we get:
	X = {g, {g, {g, {g, X}}}}
	                -X'''-
	            -----X''---
	        --------X'------
	    --------X------------

So it is true that X' contains X'' but it does not contain X'''. What is
true is that X'' contains X'''. So by saying X(m) contains any X(n) (where
(X(p) is X with p dashes) is not true unless n=m+1). So you can't then go
on to say that X' contains more than one copy of X.

--
Nik ``nik@scs.leeds.ac.uk'' Silver

sa114984@longs.lance.colostate.edu (Steven Arnold) writes:
>	Suppose X is an arbitrary set which contains itself as a
>member.  All other members within the set can be symbolized as
>'g'; therefore,
>
>		X = {g,X}		(1)

As somebody else did, I'll take it Steven meant "X = g U {X}".

>	Eq. 1 can be expanded as follows:
>
>		X = {g, X'}
>		        /\
>		       {g,X''}
>		          /\
>			 {g,X'''}
>...
>	The number of X's below X'' is infinite; nonetheless, it
>is certainly true that X' contains X'' as well as all the X's
>contained by X'';

What does "contains" mean?  If "X contains Y" means "Y is an element
of X", then I'll simply point out that "is an element of" is NOT
transitive (consider the sets {a}, {{a}}, and {{{a}}}).  If on the
other hand he means "there is a finite chain of 'is-an-element-of'
relationships from Y to X" (a nonstandard definition) we can go on.

>therefore X' contains one more X than X''!

This comment only makes sense for "sets with multiplicity" (i.e. the
set {a,b} is different from the set {a,b,b,b,b}).  If this nonstandard
definition is what he means, we can go on.

The statement "X' contains one more X than X''!" is no contradiction,
since both numbers are infinite (as Steven had already pointed out).
So let's go on.

>It
>follows that X' != X'', for X' contains an X not contained in X''. 

But I thought all these X's were assumed to be identical.  To prove
X'!=X by this method, you'd need to be able to point out one object
that's in one but not in the other.

Yes, there are several flaws in the argument.  And each of them is
interesting in a way; they point out several of the ways standard set
theory violates the intuitions one develops by dealing with finite
(not to mention well-founded!) sets.

-- 
					Stephen Bloch
				sbloch@silver.cs.umanitoba.ca

In article <Oct05.201328.96457@yuma.ACNS.ColoState.EDU> sa114984@longs.lance.colostate.edu (Steven Arnold) writes:
>
>	I am not an expert in set theory or the predicate
>calculus, but I was leafing through a book on the subject and the
>following informal "proof" occured to me.  Could any of you experts out
>there tell me if this contains a major flaw -- and if so, what it
>is?  Thanks.
>
>	The proposition to be proven is: A set can never contain
>itself as a member.

One more point about this "proof":

If in your proof you replace "set" by "list", and write X = [g,X] in
place of X = {g,X} to denote a list instead of a set, then you will
have proved that such lists cannot exist.  This contradicts what
happens in Lisp.  Lisp lists are necessarily finite, but may contain
cycles.  Peter Aczel's treatment of AFA does in careful detail for sets
what Lisp long ago did for lists, albeit without the mandatory
agonizing over whether this would blow the universe's fuse.

-- 
=================================================== In short, I am floundering
Vaughan Pratt   pratt@cs.Stanford.EDU  415-494-2545 around and don't take what
=================================================== I say seriously.