Sunday, January 31, 2016

Topology

[Attention, this code is not included in the code site!]

The blog has become a little messy and I will try to clean it up. These simple implementations of sets and groups are limited but interesting. I believe in the idea of bundles on a stack, but the data stack is not perfect for the purpose: for the sake of portability the data stack can only be manipulated with a restricted number of words. With a special stack for bundles, stack manipulations can be made much more efficient.

While going on with the current implementation for a while, I will try to find out a faster implementation. With better algorithms: until now I have used sloppy straight forward brutal force algorithms or worse! Also the implementation of permutations and groups must be enhanced.


Topological spaces

Topology is very easy to understand in spite of it's often formalistic presentation for the students. In set theory the question is: does an element belong to the set or not. In topology the question is if the element is close to the set or not.

That's what a topological structure λ on a set X submit, the possibility to decide whether a point x in X belongs to the closure of a subset A of X or not. The set λ of open subsets of X brings the method: the point x is in the closure of A if and only if every open set O in λ that contain x, also contain a point in A.


Two subsets of X are obligatory in λ and that's ø and X. Beyond that there are two rules for λ to be a topology on X. (1) Given a subset B of λ, then the union of all sets in B should belong to λ. (2) given two sets O,Ô in λ, then the intersection of O and Ô should belong to λ.



Examples:


  • The topology of the real numbers (a topology which is a necessary part of the definition of the set of real numbers) consists of all unions of limited open intervalls, that is, open intervalls of the type {x|a<x<b} for real numbers a,b. Any union of such intervalls belongs to this topology. The point 1 belongs to the closure of {x|0<x<1}, without actually being a member of that set, because every open set that contains 1 also contains a point in {x|0<x<1}.
  • The set {ø,X} is a topology on X called the trivial topology and the set of all subsets of X is a topology called the discrete topology.
  • Any infinite set X has an obvious topology consisting of all complements of finite subsets of X plus the empty set.
  • Any set of subsets of a set X generates a minimal topology on X which contain those subsets.
A subset C of X is said to be closed if X\C is open, that is belong to λ. The closure of a subset A of X is the smallest closed set C such that A is a subset of C. The most interesting infinite topological spaces are the Hausdorff spaces, where all singleton sets {x} are closed. But for finite topological spaces all Hausdorff spaces are discrete. Finite spaces are determined by the closure function of all the singleton sets, because with that function it's possible to decide which points that are close to which sets.

In stack diagram for setcup s is a set of sets and s' is a set of points. And s" is the set of the unions of all elements of s ans s':


{ { 1 2 } { 2 3 4 } } { 3 4 5 } setcup cr set.
{{1,2,3,4,5},{2,3,4,5}} ok


: setcup ( s s' -- s")
  >>xst 0 >yst foreach
  ?do nxst@ union fence yst>> union >>yst
  loop nxstdrop yst>> ;



Similar for the word:

: setcap ( s s' -- s")
  >>xst 0 >yst foreach
  ?do nxst@ intersection fence yst>> union >>yst
  loop nxstdrop yst>> ;


The word capgen generates all intersections:

: capgen ( s -- s')
  ndup >>yst ndup >>xst foreach
  ?do nyst@ nswap setcap xst>> union >>xst
  loop nystdrop xst>> ;


The word cupgen generates the set of all unions os s. When first apply capgen and then cupgen all the non trivial open sets in the smallest topology that includes s are generated. And the word topology completes with ø and X, which might or might not be generated by capgen and cupgen.

: cupgen ( s -- s' )
  ndup >>yst ndup >>xst foreach
  ?do nyst@ nswap setcup xst>> union >>xst
  loop nystdrop xst>> ;


{ { 1 2 } { 2 3 4 } { 3 4 5 } } capgen ndup cr set.
{{2},0,{3,4},{1,2},{2,3,4},{3,4,5}} ok
cupgen ndup cr set.
{{1,2,3,4},{1,2,3,4,5},{2,3,4,5},{2},0,{3,4},{1,2},{2,3,4},{3,4,5}} ok
{ 1 2 3 4 5 } { { 1 2 } { 2 3 4 } { 3 4 5 } } topology cr set.
{{1,2,3,4},{2,3,4,5},{2},{3,4},{1,2},{2,3,4},{3,4,5},{1,2,3,4,5},0} ok


: topology \ X s -- λ
  nover nswap capgen
  cupgen nswap incl 0 incl ;



In the figure the rectangle correspond to X and the colored shapes to the set of sets generating a topology. The colored surfaces are the primitive intersections, and the topology is the set of all combinations of unions of those intersections.

The next word computes the closure to the singleton {x}.


: singlecl \ λ x -- s  
  0 false loc{ x y flag } >>yst 0 >xst
  nyst@ nunion foreach
  ?do to y true to flag nyst@ foreach
     ?do ndup y member
        if x member 0=
           if false to flag then
        else ndrop
        then
     loop flag if xst>> y incl >>xst then
  loop nystdrop xst>> ;


And the λ-closure for any set:


: closure ( λ s -- s')
  nswap >>xst 0 >yst foreach
  ?do >r nxst@ r> singlecl yst>> union >>yst
  loop nxstdrop yst>> ;


{ 1 2 3 4 5 } { { 1 2 } { 2 3 4 } { 3 4 5 } } topology   ok
{ 1 3 5 } closure cr set.
{1,4,3,5} ok


So except for the members 1,3,5 also 4 is close to {1,3,5}.
The word opsubs computes all open sets that are subsets of s.


: opsubs ( λ s -- s' )
  >>yst 0 >xst foreach
  ?do ndup nyst@ subset
     if fence xst>> union >>xst
     else ndrop
     then
  loop nystdrop xst>> ;


The interior of a set s is the set of all points which are members of an open set that is a subset of s. That is, s' is the union of all open subsets of s.


: interior ( λ s --- s')
  opsubs nunion ;


{ 1 2 3 4 5 } { { 1 2 } { 2 3 4 } { 3 4 5 } } topology ndup  ok
{ 1 3 5 } interior cr set.
0  ok
{ 2 3 } interior cr set.
{2} ok

2 comments:

  1. There is an error here. The topology isn't computed correct. Will fix.

    ReplyDelete
  2. Now I hope that everything is correct.

    ReplyDelete