On Mon, May 26, 2025 at 06:48:39PM +0100, Martin Baker wrote:
> Hi Waldek,
> Thank you for your helpful reply, lots of issues here:
>
> On 26/05/2025 14:56, Waldek Hebisch wrote:
> > AFAICS _both_ can represent either topologies or isomorphism classes.
> > In both cases to get isomorphism classes you need to to some
> > filtering to choose a representaitve or form abstracition classes
> > (classes of equvalent topologies).
>
> The idea here is that:
> * topologies are sets of _labeled_ sets
OK.
> * isomorphism classes are sets of _unlabeled_ sets
> (both with the usual meet,join top and bottom axioms)
I do not think this will work well (at least not in a simple
way). In isomorphism class you allow arbitrary relabeling, so
at "absolute" level labels do not matter. But they
matter in relative sense. You need to know when two elements
are in fact one element (that is they are equal), you need
to know if for given p and q there is an open set containing
q but such that p is not in this set. Easiest way to
keep this information is to use labels. You could try to
encode elements of the set by their properties, but to
do this you need to know which combination of properties
are possible.
What you wrote above looks more like you would like to represent
lattice of open sets as an abstract lattice. AFAICS you still
would have to decide when two abstrace lattices are isomorphic
and it is not clear if isomorphism class of lattices gives you
isomorphism class of topologial spaces. Mathematical version of
Murphy principle says that if there is no reason for some property
to be true, then it is false. And ATM I see no reason to
have nice correspondence there (of course I may be missing
something).
> So when we go from labeled sets to unlabeled sets all we have left is the
> number of elements (cardinality) which looses the information about meets
> and joins so we have to put that explicitly back into the representation as
> a subset structure.
>
> Representing isomorphism classes in this way does not involve choosing a
> representative. Also I hope there should be a canonical way to represent the
> subset structure so that I can implement: equality(=) is isomorphic to
> isomorphism. (a bit like Voevodsky’s Univalence Axiom).
>
> I take your point that we can represent either with both representations but
> it seems a lot more efficient this way round.
> For instance, representing isomorphism classes with a labeled set and then
> using only representative members seems like creating arbitrary information
> that is not used (would the nice property that meets are intersections and
> joins are unions still be valid in this case?).
Well, sometimes discarding information is not easy. Concerning meets
and joins, correspondence that I have in mind is 1-1 correspondence
between topologies and pre-orders. Any pre-order has corresponding
topology, so there is no requrement for nice meets and joins.
> Or, this other way round, the following two topologies would have the same
> shape lattice, so how do you distinguish them from the substructure only?
> [{}, {3}, {1, 2}, {1, 2, 3}]
> [{}, {1}, {2, 3}, {1, 2, 3}]
First, minimal basis(es) are respectively
[{3}, {1, 2}]
[{1}, {2, 3}]
Denoting by <=_1 and <=_2 corresponding preoders we have 1 <=_1 2 and
2 <=_1 1. OTOH 1 <=_2 2 is false. So pre-orders are different.
> > Typicaly is is easier to work with partial pre-orders, as there is only
> > one pre-order corresponding to a given topology, while you can
> > take many different bases.
>
> I think that may be what I meant by 'subset structure'. I was thinking of
> implementing it as a list of (subset,superset) pairs. Since subset and
> superset are NNI indexes I was hoping there would be a way to force them in
> a canonical order.
You are thinking subsets, which potentially is quite bulky, there may
be (and probably typically is) exponentially many open subsets, while
pre-order needs matrix of size N^2 (where N is number of elements in
the base set).
> > > I want to be able to convert between these representations.
> >
> > Given a topology and a point p consider minimal open set contaning
> > p, call it U(p). Such a set exist, you can get it as intersection
> > of all open sets contaning p (since topology is finite this is a
> > finite family of open sets, so its intersection is open). You
> > can compute U(p) taking intersection of all elements of a basis
> > containing p. Once you know U(p) you know pre-order: q <= p
> > and only if q \in U(p). Conversly, when you know pre-order
> > you can get U(p) as {q : q <= p }. U(p) give you a basis of
> > topology (in fact a minimal basis, every other basis must
> > contain all U(p)).
>
> Yes, I have been experimenting with some code for converting topologies
> to/from basis. I need to do some more work on this.
>
> > > For instance,
> > > given a topology isomorphism class, I want a function that will list all
> > > topologies for that class and also a function to construct one
> > > representative topology. Also I would like a function to go in the reverse
> > > direction.
> >
> > You need to decide how you represent isomorphism class. If you
> > represent class using a representative, then going for topology
> > to class is trivial, any topology may serve as a representative.
> > But then you need code to compute equivalence, and you need to
> > deal with conseqences of fact that such representation is
> > noncanonical. You man try to put order on topologies, as say
> > take smallest topology in a class as a representative, then
> > you will need some work to compute representative, but equality
> > of classes will be easy.
>
> If you think what I said above is valid then I think I can represent an
> isomorphism class without using a representative.
It is not clear to me what _exactly_ you want to do, but it looks
tricky to make it work without using a representative of
something. Of course, in extreme case you could use set of
topologies isomorphic to a given topology, but done in a
simple way this is double exponential. You could try to prune
this, but usually taking a representative is a most efficient
way to get rid of bulk.
<snip>
> I have been thinking for some time now that the most efficient way to
> represent a topology would be to build it up from sub-topologies but I could
> not work out how to do this. However, I have just realised how to do it:
> build a big topology from smaller _discrete_ topologies.
>
> So this:
> [{1, 2, 3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {1, 2},
> {1, 3}, {2, 3}, {1, 4}, {1}, {2}, {3}, {}]
> could be coded like this:
> P{1, 2, 3}+{1, 4}+{1, 2, 4}+{1, 3, 4}+{1, 2, 3, 4}
>
> Where P means powerset.
Well, there is easy thing to do: each finite topological space
is a disjoint sum of connected componests. I the case above
one connected component is {1, 4} (with topology [{}, {1}, {1, 4}]),
there two other components: {2} and {3}. You can view {1, 4}
with the topology above as an extention of {1} by {4}, but in
general added part ({4} here) is "glued" to previous part in
a non trivial way. I think it is much clearer when you look
at corresponding pre-orders. Pre-order on {1, 4} is just
normal linear order, but it should be clear that you may have
much more "interesting" pre-orders. Let X be a topological
space. The set of minimal elements of X, call it M is just a
discrete space. X - M gives you smaller topology. But whole
topology is only determined once you now order relations between
elements of M and X - M.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/fricas-devel/aDTPsuFQD86zDtif%40fricas.org.
