Sonlu bir topolojik uzayda bir kümenin içini ve kapanışını bulan bir algoritma nasıl yazılır?

Question

$(X,\tau)$ sonlu bir topolojik uzay ve $A\subseteq X$ olmak üzere $A$ kümesinin içini $(A^{\circ})$ ve $(\overline{A})$ kapanışını bulan bir algoritma nasıl yazılır?

 

NOT: Bir $(X,\tau)$ topolojik uzayında bir $A$ kümesinin içi, $A$ kümesinin kapsadığı tüm açık kümelerin birleşimi; kapanışı ise $A$ kümesini kapsayan tüm kapalı kümelerin kesişimi olarak tanımlanır. Biçimsel olarak

$$A^{\circ}:=\cup \left\{U|U\subseteq A, U\in\tau\right\}  \ \text{ ve } \  \ \overline{A}:=\cap \left\{F|A\subseteq F, \setminus F\in\tau\right\}$$ şeklinde ifade edilir.

Comments

Kapanisin bicimsel tanimini tam anlamadim. Acaba parantezlerin yerinde mi sorun var ? $(\setminus F \in \tau)$ ne demek anlayamadim

---

$ \setminus F\in\tau$ : $F$ kümesinin tümleyeni açık $($yani $F$ kapalı küme$)$

$(F^c=\setminus F)$

---

Tesekkurler. Az onceki cevaptan yola cikarak yaziyorum simdi

Answer 1

Daha onceki cevapta kullandigimiz "Sonlu kumeler uzerindeki her topoloji icin biricik bir preorder vardir" onermesinden yararlanacagiz. Topolojiden preordera gitmek icin,  $x$ in bulundugu her acik kumede, $y$ de bulunuyorsa, $x \leq y$ diyecegiz. 

Bu preorderi bir matriks olarak ifade ettigimizde ( $x \leq y  \iff M_{x,y} = 1$) bu matriks bize topolojinin bir bazini veriyordu.

Genel olarak alexandrov topolojilerinde (sonlu kesisim sartinin sonsuz kesisim ile degistirin) sanirim soyle bir eslesme var gene

$Int(s) = \{ x \in X : \quad\forall y\in X , x\leq y\ \implies y \in S \}$

$Cl(s) = \{ x \in X : \quad\exists y\in S , x\leq y \}$

Bunlari kullanarak koda dokmek zor degil istenen iki fonksyonu

 

using LinearAlgebra


ise(x, y) = !x || y


function ailedenSiralama(aile::Set{Set{T}})
    esaskume = union(aile...)
    siralama = falses(length(kume),length(kume))
    for x in esaskume
        for y in esaskume
            if all(y ∈ kume for kume ∈ aile if x ∈ kume)
                siralama[x,y] = true
            end
        end
    end
end

function transitifmi(A::BitMatrix)
    xx, xy = axes(A)
    @inbounds  for i in xx, j in xy
        @inbounds h = ise(any(A[i, k] && A[k, j] for k in xy), A[i, j])
        if !h
            return false
        end
    end
    return true
end

topolojimi(x::BitMatrix) = transitifmi(x) && refleksifmi(x)
topolojimi(x::Set{Set{T}}) = topolojimi(ailedenSiralama(x))


refleksifmi(x::BitMatrix) = @inbounds all(x[i] for i in diagind(x))

bitMatriks(x, boyut) = reshape(digits(x, base=2, pad=boyut * boyut) .> 0, boyut, boyut)


function tumNboyutluTopolojilerInteger(n)
    digit = zeros(Int64,n*n)
    dVec = digit .> 0
    _tumNboyutluTopolojiler(n, digit, dVec)
end


function _tumNboyutluTopolojiler(n,digit,bitV)
     bitM = reshape(bitV,n,n)
    results::Array{Int64} = [];
    s = sum( 1<<i for i in 0:n:(n * (n - 1)-1))
    e = 2^(n * n) -1
    for i in s:e
        digits!(digit, i, base=2)
        bitV .= digit .> 0
        #bitM .= reshape(bitV, n, n)
        if (topolojimi(bitM))
            #display(bitM)
            append!(results, i)
        end
    end
    results
 end

#sum topoloji
function ⊕(x::BitMatrix, y::BitMatrix)
    xx, xy = size(x)
    yx, yy = size(y)
    [x falses(xx, yy); falses(yx, xy) y]
end

#product topoloji
⊗(x::BitMatrix, y::BitMatrix) = kron(x, y)

#subspace topoloji ??
function subspaceTopoloji(top::BitMatrix, altKume)
    sx, _ = size(top)
    range = filter(x->x ∉ altKume,collect(1:sx))
    result = copy(top[range,range])
    result
end

function glue(top::BitMatrix, x, y)
    if x > y
        temp = x
        x = y
        y = temp
    end
    sx, _ = size(top)
    range = filter(v -> v != y, collect(1:sx))
    t = copy(top[range, range])
    t[x, :] .= (top[x, :].|top[y, :])[range]
    t[:, x] .= (top[:, x].|top[:, y])[range]
    t
end

#quotient topology?
function quotientTopoloji(top::BitMatrix, quotientMap::Dict{Int,Int})
    sx, _ = size(top)
    #TODO glue kullanarak yaz burayi arkaya arkaya glue kullanmak gerekiyor sadece
end

function interior(top::BitMatrix, S)
    #Interior(s) = { x ∈ X :  ∀ y∈ X  x ≤ y ⟹ y ∈ S }


    sx, _ = size(top)
    results = []
    for x ∈ 1:sx
        if all(ise(top[x, y], y ∈ S) for y ∈ 1:sx)
            append!(results,x)
        end
    end
    results
end

function closure(top::BitMatrix,S)
    #Closure(s) = { x ∈ X :  ∃y∈ S : x≤y }$


    sx,_ = size(top)
    results = []
    for x ∈ 1:sx
        for y ∈ S
            if top[x,y]
                append!(results,x)
                break
            end
        end
    end
    results
end

 

Kodun icinde ayrica toplam, carpim, altuzay ve bolum topolojilerini veren algoritmalari bulabilirsiniz. 

Bunun disinda henuz kodda ifade etmeye zaman bulamadigim su tarz bulgularim var:

- $f : X \to Y \quad \text{surekli} \iff \forall x \in X x \leq y \iff f(x) \leq f(y)$

- $A,B$ iki tane topolojik uzayi / siralamayi tarif eden matrisler olsunlar.

$A$ ile $B$ homeomorf ise oyle iki permutasyon matrisi $P,Q$ var ki $A = PBQ'$

ancak bu sorunun cozumu yonlu cizge izmofizmasina denk (np hard olup olmadigi bilinmiyor en yakin quasi exponensiyel bir algoritma var elimizde). Belki Preorder izomorfizmasi kullanilip daha verimli bir cozum gelistirelebilir ???

- $A$ matrisinin determinanti $0$ yada $1$ olabiliyor, Bu altta yatan uzayin $T_0$ olup olmamasini ayird ediyor

Answer 2

Dogrulugunu test edemedim ama pythonda soyle bir algoritma yazdim. Gene cok verimsiz ama dogru calisacagini dusunuyorum

def kumenin_ici(alt_kume,kume,topoloji):
    ic = set()
    for acik_kume in topoloji:
        if(acik_kume.issubset(alt_kume)):
            ic =ic.union(acik_kume)
    return ic



def kapali_kumeleri_bul(kume:set,topoloji:set):
    kapalilar = set()
    for i in topoloji:
        kapalilar.add(frozenset(kume.difference(i)))
    return kapalilar

def kumenin_kapanisi(alt_kume:set,kume:set,topoloji:set):
    kapanis = kume
    kapalilar = kapali_kumeleri_bul(kume,topoloji)
    for i in kapalilar:
        if alt_kume.issubset(i) :
            kapanis  = kapanis.intersection(i)
    return kapanis

alt_kume = set({1})
kume = set({1,2})
topoloji = { frozenset() , frozenset({1}),frozenset({1,2})}

# a = {1} x = {1,2} t = {{},x,{1}}
print(kumenin_ici(alt_kume,kume,topoloji))      #{1}
print(kumenin_kapanisi(alt_kume,kume,topoloji)) #{1,2}

# a = {1} x = {1,2} t = {{},x}
alt_kume = set({1})
kume = set({1,2})
topoloji = { frozenset() , frozenset({1,2})}

print(kumenin_ici(alt_kume,kume,topoloji))     #{}
print(kumenin_kapanisi(alt_kume,kume,topoloji)) #{1,2}

# a = {1} x = {1,2} t = {{},x,{1},{2}}
alt_kume = set({1})
kume = set({1,2})
topoloji = { frozenset() , frozenset({1,2}) ,  frozenset({1}) ,  frozenset({2})}

print(kumenin_ici(alt_kume,kume,topoloji))        # {1}
print(kumenin_kapanisi(alt_kume,kume,topoloji))   # {1}

 

Comments

Kod python değil mi? Hangi dil olduğunu yazarsanız harika olur.

---

Degistirdim cevabi. Bu tur sorular ile ilgili project euclid de baslattigimiz gibi tag baslatsak guzel olabilir. Bu tur tanimlarin programlara donusturebilecegi bir cok konu var sonlu cisimler, sonlu topolojiler, cizgeler. Insa edilebilen matematigi programlar olarak insa etsek guzel olurdu. Formal matematiksel dili nasil somut bir programlama diline dokeriz hos bir soru bence.