Xref: utzoo comp.theory:1464 sci.math:14784
Path: utzoo!censor!geac!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!samsung!usc!isi.edu!gremlin!charming.nrtc.northrop.com!johnson
From: johnson@charming.nrtc.northrop.com (Greg Johnson <gjohnson>)
Newsgroups: comp.theory,sci.math
Subject: A set F of functions from F to F ??
Message-ID: <16470@gremlin.nrtc.northrop.com>
Date: 23 Jan 91 00:50:01 GMT
Sender: news@gremlin.nrtc.northrop.com
Reply-To: johnson@charming.nrtc.northrop.com (Greg Johnson <gjohnson>)
Followup-To: comp.theory
Organization: Northrop Research & Technology Center, Palos Verdes, CA
Lines: 59

In `usual' set theory (that which is relied on in standard texts such as Rudin
and Munkres) is it possible to have a set which contains itself as a member?
Or does usual set theory (ZF for instance) preclude such a thing?

Here is an attempt to write a set containing itself:

  { { { ... } } }

The above `set' has a single element, which is equal to the set itself.  This
is by way of analogy with the following infinite tree, which is equal to some
of its (proper) subtrees:

      o
     /|\
    / | \
   (  o  )
     /|\
    / | \
   (  o  )
     /|\
    / | \
   (  o  )
      .
      .
      .

Another question, a variant of the above:  Is it possible to have a set
F of functions whose domain and range are F?  As a small example, F might
contain two functions f1 and f2, where f1 is the identity and f2 is a constant
function.  (Notice that F is not its own function space, which would be
impossible; F is a subset of its function space.)

Thinking of a function as a set of ordered pairs and using the usual trick to
encode ordered pairs as sets ( <1,2> = { {1}, {1,2} }, <3,3> = { {3} } ),
this `set' would correspond to the following infinite tree, where `f1' and
`f2' are copies of the left and right subtrees of the root:

             o
           /    \
         /        \
       /            \
      o               o
     / \             / \
    /   \           o   o
   o     o        /   \  \
   |     |       /     \  \
   o     o      o       o  o
   |     |      |      / \  \
   f1    f2     f1   f1  f2  f2


The function f1 is (as a set)   {  <f1,f1>, <f2,f2> }
The function f2 is              {  <f1,f2>, <f2,f2> }

Thanks for any answers -

Greg Johnson

p.s. - Please send responses to me, since I don't always read these groups.