[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1479.0. "topologies & relations" by HERON::BUCHANAN (object occidented) Mon Aug 12 1991 04:59

	Note 712 asked for the number of transitive relations which can be
defined on a set of N elements.   Several notes have examined formulae for
the number of partitions (ie: reflexive, symmetric, transitive relations)
on N elements.

	Here's an intermediate question that occured to me in the mountains at
the weekend.

	Show that the number of topologies which can be defined on a set of
N distinct elements is the same as the number of reflexive, transitive (but 
not necessarily symmetric) relations which can be defined on that set of N
elements.

	Computationally-inclined individuals with spare cycles might care
to calculate some precise values.   Theoretically-oriented folk might want
to see if they can come up with a recursion for the number of values.   Does
anyone (NRVANA::RAMANUJAN perhaps?) care to come up with a closed form.


	Reminder:
	A topology T on a set S is a set of subsets of S such that the union
of any bunch of elements of T lies in T, and the intersection of any finite
number of elements of T lies in T.   It follows that the empty set, �, and S
both lie in T.   Note that we assume that N is finite in this problem.

Andrew.
T.RTitleUserPersonal
Name		DateLines
1479.1ZFC::deramoConan the MathematicianMon Aug 12 1991 10:573
Must be some mountains. :-)

Dan
1479.2ALIEN::EDPAlways mount a scratch monkey.Wed Aug 14 1991 08:5016
    Re .0:
                                      
    > 	A topology T on a set S is a set of subsets of S such that the
    > union of any bunch of elements of T lies in T, and the intersection of
    > any finite number of elements of T lies in T.   It follows that the
    > empty set, �, and S both lie in T.   Note that we assume that N is
    > finite in this problem.
    
    Let S = { a, b }.  Let T = { { a } }.  The union or intersection of any
    number of elements of T is { a }, so T is a topology, yet it contains
    neither the empty set nor S.  If the intersection of zero sets is
    allowed, then it is the null set and that must be included in T, but I
    still do not see that S must be in T.  What am I missing?
    
    
    				-- edp
1479.3ZFC::deramoI'll be back.Wed Aug 14 1991 10:557
If one thinks of the empty union as the empty set (which is usual),
and the empty intersection as the full set (which is less usual),
then one can state that "it follows that the empty set and S both
lie in T".  Otherwise, just state the definition of a topology so
that it is required that the empty set and S both be in T.

Dan
1479.4answerDESIR::BUCHANANFri Jul 17 1992 13:0937
>	Show that the number of topologies which can be defined on a set of
>N distinct elements is the same as the number of reflexive, transitive (but 
>not necessarily symmetric) relations which can be defined on that set of N
>elements.

	Define the manor of an element x, manor(x), to be the intersection of
all open sets containing x.   Since the topology is finite, manor(x) is open.  
In fact, the topology is uniquely specified, once the manors are known.   This
is because any set is just the union of the manors of its elements, and so all
open sets can be arrived at just by taking unions of manors.

	Now for a particular topology T, define the relation M by:
xMy <=> x lies in manor(y).   Now this relation specifies completely the
manors, and hence completely specifies the topology.   It's obvious that M
is reflexive.   To see that M is transitive, suppose that xMy and yMz.   By
the definition of manor, x lies in any set containing y.   Since y lies in
manor(z), so must x.   Thus xMz.   So any topology corresponds to a reflexive,
transitive relation.

	Suppose now that M is an arbitrary reflexive, transitive relation.
Let's define manor(y) to be {x|xMy}.   Then define T to be the closure under
unions of the set of manors.   Is T a topology?   All that we have to check
is that the intersection of two manors is a union of manors.   If the two
manors are disjoint, then we have nothing to prove, since the empty set is
the empty union, and (a fortiori) a union.   Otherwise say x lies in manor(y)
and also in manor(z).   By the transitivity of M, manor(x) is a subset of 
manor(y) and also of manor(z).   So: 
	manor(y) \intersect manor(z)
=	\union (x in manor(y) \intersect manor(z)) manor(x).

	So we have a 1-1 correspondence between topologies and reflexive
relations over a finite set.   QED

	Note: the word "manor" in London (England) slang means "someone's 
native part of town".

Andrew.