johnson@charming.nrtc.northrop.com (Greg Johnson <gjohnson>) (01/23/91)
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.mjd@saul.cis.upenn.edu (Mr. Prolific) (01/23/91)
In article <16470@gremlin.nrtc.northrop.com> johnson@charming.nrtc.northrop.com (Greg Johnson <gjohnson>) writes: > 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? Although you're perfectly free to develop any theory of sets you like, the usual ones don't have any such sets. We might restrict our models with an axiom like this one: Foo: For any non-null set X, there is a member Y in X, such that X and Y are disjoint. From this, we can show that there is no set which is an element of itself, at least in the usual models. Here's the proof, which is simpler than it looks, because I wrote it out in hideous detail: 1. Suppose there were such a set, say Z, with Z an element of Z. 2. Then by another theorem we would like to have shown from other axioms, {Z} is a set. 3. `Foo' says that there is an element Y in {Z}, such that Y is disjoint from {Z}. 4. The only element of {Z} is Z, so the Y of step 3 must be equal to Z. 5. Since Y is disjoint from {Z} (Step 3.) and Y=Z (Step 4.) then Z is disjoint from {Z}. 6. Since Z is an element of Z (Step 1.) and of {Z} (Definition of `{Z}' in any reasonable theory), Z and {Z} are not disjoint. 7. Steps 5 and 6 contradict each other, so the supposition of step 1 is false and no set is an element of itself. So in `the usual theory' there are no sets that are elements of themselves. (Step 2 follows from the fact that I'm only talking about `the usual theory'; any reasonable and usual theory of sets will have as a theorem that {X} is a set when X is. For more details, see the appendix of John Kelley, _General Topology_.) The `foo' axiom above turns out to be pretty strong; once you have the induction axiom in place, you can use `foo' to prove no only that no set is an element of itself, but also that 1) There's no collection of sets {X1, X2, X3 ... Xn} with X1 an element of X2, X2 an element of X3, ... , and Xn an element of X1. 2) There's no sequence of sets {X1, X2, X3 ...} with X1 an element of X2, X2 an element of X3, ... In particular, (1) precludes having a `set' of functions like the one you describe. A pretty good reference for this stuff is the appendix to John Kelley's _General Topology_; that's where I cribbed most of this posting from. > Here is an attempt to write a set containing itself: > { { { ... } } } > The above `set' has a single element, which is equal to the set itself. Like I said, you can make up whatever you like, but it seems to me that confusing inkmarks on paper with sets is only going to get you confused in the long run. Ink marks on paper are not sets and you can't reason about them. An axiomatic system is supposed to describe in operational terms exactly what you can and can't do with a set, and what things are sets and what aren't. That is why we use axiomatic systems instead of waving our hands over little squiggles like `{'. You could of course make up axioms for little squiggles and show that there is a natural isomorphism between squiggles and sets, but if you were going to do all that work anyway then why did you need the squiggles in the first place? > Thanks for any answers - > Greg Johnson Sure 'nuff. > p.s. - Please send responses to me, since I don't always read these groups. Tough luck! -- Behold the riant anthropoid, beware its crooked thumbs! Mark-Jason Dominus mjd@central.cis.upenn.edu
hensm@csc2.essex.ac.uk (Henson M C) (01/23/91)
In ZF one has the axiom of foundation which rules out sets which have themselves as members. Levy's text [Springer Perspectives in Mathematical logic series: "Basic Set Theory" ] is a good presentation. In intuitionistic set theories like IZF this axiom gets replaced by epsilon-induction which is classically equivalent to foundation. This is done because foundation implies excluded middle which is not universally valid in intuitionistic theories. Beeson's text ["Foundations of Constructive Mathematics", Springer] is a good presentation. Peter Aczel has written a book on non-well founded sets which is very nice and published in the CLSI monograph series.
moss@cs.umass.edu (Eliot Moss) (01/24/91)
In the theory of semantics of programming languages work has been done on
domain equations such as F = F -> F and there are indeed useful solutions.
However, rather than F -> F being the set of ALL functions from F to F, it is
the set of all CONTINUOUS functions from F to F. Further, the domains are
lattices (or sometimes complete partial orders). A lattice is a set with a
partial order (usually written with a square version of the mathematical
less-than-or-equal symbol) such that every pair of elements has a unique least
upper bound and greatest lower bound, and every chain x1 <= x2 <= ..., finite
or infinite, has a unique limit (and likewise for the other direction).
Continuity is defined in terms of the ordering; a function G is continuous
provided whenever x <= y, G(x) <= G(y), which implies that as arguments go to
limits so do continuous function results.
Well, it turns out that the cardinality of the set of CONTINUOUS functions on
a domain D is not a higher order of infinity than D, so it is possible to
develop mappings between D and D -> D such that elements of D represent
continuous functions D -> D. Dana Scott proved this some years ago using what
is called the inverse limit construction. My understanding is that category
theoretic work follows in the same general vein.
Someone else (Joe Stoy?) developed a specific example called the P(w) (power
set of omega, i.e., the set of sets of natural numbers) construction, which
goes as follows. What we want is a way to represent a CONTINUOUS function from
P(w) to P(w) as an ELEMENT of P(w), i.e., as a set of integers. Well, for a
continuous function we need know only what it does to FINITE sets of integers,
since what it does on an infinite set is determined as the limit of its
operation on a chain of finite sets building up to the infinite set. (The
lattice ordering here is the ordinary set containment relation.) Somehow (I
don't recall) the functions are restricted to finite set results on finite set
arguments. Given that, we can think of the function as a set of pairs
{(x1,y1), (x2,y2), ...} where each xi and yi is a finite set of integers (a
finite element of P(w)). Since the number of FINITE sets of integers is
countable, the set repsenting the function is countable. Now the final trick:
use some unique encoding of finite sets of integers into integers (Godel
numbering, say) to encode the function as {(x1',y1'),(x2'y2'),...} where xi'
is the integer encoding of the set of integers xi. Now encode each pair of
integers (xi',yi') as a single integer zi using a unique encoding of paris of
intgers to integers. Encode the function as {z1,z2,...} which is an element of
P(w). In this way (certain) elements of P(w) can be understood to represent
continuous functions from P(w) to P(w). Note how crucial the continuity
property is: without it the set of pairs describing the function would not be
countable and the elements of the pairs not always encodable as integers.
Hope this adds to your understanding of the interesting aspects of functional
domains.
--
J. Eliot B. Moss, Assistant Professor
Department of Computer and Information Science
Lederle Graduate Research Center
University of Massachusetts
Amherst, MA 01003
(413) 545-4206, 545-1249 (fax); Moss@cs.umass.eduhensm@csc2.essex.ac.uk (Henson M C) (01/25/91)
Newsgroups: comp.theory Subject: Re: A set F of functions from F to F ?? Summary: Domain Theory Expires: References: <16470@gremlin.nrtc.northrop.com> <RAR.91Jan23010514@saturn.ads.com> Sender: Reply-To: hensm@essex.ac.uk (Henson M C) Followup-To: Distribution: Organization: University of Essex, Colchester, UK Keywords: In ZF it is possible to solve equations like D = D->D up to isomorphism. You need to impose conditions on the sets (various partial orderings work) and restrict the function space in some way (continuous wrt ordering). This is elementary domain theory and Dana Scott was reponsible for starting it in about 1970. Spaces like D are needed in order to provide a compositional semantics for the lambda calculus. The key is of course that the function space is so restricted. In general the set D->D always has strictly greater cardinality to D unless D has fewer than 2 elements. See the following: Barendregt, H., The lambda calculus, North Holland, 1984. Schmidt, D., Denotational semantics, Allyn and Bacon, 1986. Scott, D., Domains for denotational semantics, LNCS 140, Springer, 1982. The categorical remark is misleading : the questioner requires a bijection at the very least between elements of D and some set of functions from D to D. Identifying objects with their identities doesn't do this.
rar@saturn.ads.com (Bob Riemenschneider) (01/25/91)
In article <MOSS.91Jan24091600@ibis.cs.umass.edu> moss@cs.umass.edu (Eliot Moss) writes:
=> Someone else (Joe Stoy?) developed a specific example called the P(w) (power
=> set of omega, i.e., the set of sets of natural numbers) construction, which
=> goes as follows. ...
Not someone *else*, Dana Scott again. He's also developed a couple more
frameworks for solving "D = [D -> D]".
-- rar