[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 06:59

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

Dan
1479.2ALIEN::EDPAlways mount a scratch monkey.Wed Aug 14 1991 10:5016
1479.3ZFC::deramoI'll be back.Wed Aug 14 1991 12: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 16: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.