@ Applied General Topology c© Universidad Politécnica de Valencia Volume 13, no. 1, 2012 pp. 91-102 Relative dimension r-dim and finite spaces A. C. Megaritis Abstract In [4] a relative covering dimension is defined and studied which is denoted by r-dim. In this paper we give an algorithm of polynomial order for computing the dimension r-dim of a pair (Q, X), where Q is a subset of a finite space X, using matrix algebra. 2010 MSC: 54F45, 54A05, 65F30. Keywords: Covering dimension, relative dimension, finite space, incidence matrix. 1. Introduction and preliminaries The “ relative dimensions ” or “ positional dimensions ” are functions whose domains are classes of subsets. By a class of subsets we mean a class consisting of pairs (Q, X), where Q is a subset of a space X. The class of finite topological spaces was first studied by P.A. Alexandroff in 1937 in [1]. A topological space X is finite if the set X is finite. In what follows we denote by X = {x1, . . . , xn} a finite space of n elements and by Ui the smallest open set of X containing the point xi, i = 1, . . . , n. The cardinality of a set X is denoted by |X| and the first infinite cardinal is denoted by ω. Let X = {x1, . . . , xn} be a finite space of n elements. The n × n matrix T = (tij), where tij = { 1, if xi ∈ Uj 0, otherwise is called the incidence matrix of X. We observe that Uj = {xi : tij = 1}, j = 1, . . . , n. 92 A. C. Megaritis We denote by c1, . . . , cn the n columns of the matrix T . Let ci = ⎛ ⎜⎜⎜⎝ c1i c2i ... cni ⎞ ⎟⎟⎟⎠ and cj = ⎛ ⎜⎜⎜⎝ c1j c2j ... cnj ⎞ ⎟⎟⎟⎠ be two n × 1 matrices. Then, by max ci we denote the maximum max{c1i, c2i, . . . , cni} and by ci + cj the n × 1 matrix ci + cj = ⎛ ⎜⎜⎜⎝ c1i + c1j c2i + c2j ... cni + cnj ⎞ ⎟⎟⎟⎠ . Also, we write ci ≤ cj if only if cki ≤ ckj for each k = 1, . . . , n. For the following notions see for example [2]. Let X be a space. A cover of X is a non-empty set of subsets of X, whose union is X. A cover c of X is said to be open (closed) if all elements of c is open (closed). A family r of subsets of X is said to be a refinement of a family c of subsets of X if each element of r is contained in an element of c. Define the order of a family r of subsets of a space X as follows: (a) ord(r) = −1 if and only if r consists of only the empty set. (b) ord(r) = n, where n ∈ ω, if and only if the intersection of any n + 2 distinct elements of r is empty and there exist n + 1 distinct elements of r, whose intersection is not empty. (c) ord(r) = ∞, if and only if for every n ∈ ω there exist n distinct elements of r, whose intersection is not empty. Definition 1.1 (see [4]). We denote by r-dim the (unique) function that has as domain the class of all subsets and as range the set ω ∪ {−1, ∞} satisfying the following condition r-dim(Q, X) ≤ n, where n ∈ {−1} ∪ ω if and only if for every finite family c of open subsets of X such that Q ⊆ ∪{U : U ∈ c} there exists a finite family r of open subsets of X refinement of c such that Q ⊆ ∪{V : V ∈ r} and ord(r) ≤ n. Finite topological spaces and the notion of dimension play an important role in digital spaces, computer graphics, and image analysis. In [5] the authors gave an algorithm for computing the covering dimension of a finite topological space using matrix algebra. In this paper we give an algorithm of polynomial order for computing the dimension r-dim of a pair (Q, X), where Q is a subset of a finite space X, using matrix algebra. Relative dimension r-dim and finite spaces 93 2. Finite spaces and dimension r-dim In this section we present some propositions concerning the dimension r-dim of a pair (Q, X), where Q is a subset of a finite space X. Proposition 2.1. Let X = {x1, . . . , xn} be a finite space and Q ⊆ X. Then, r-dim(Q, X) ≤ k, where k ∈ ω, if and only if there exists a family {Uj1, . . . , Ujm} such that {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ . . . ∪ Ujm and ord({Uj1, . . . , Ujm) ≤ k. Proof. Let r-dim(Q, X) ≤ k, where k ∈ ω. We prove that there exists a family {Uj1, . . . , Ujm } such that {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ . . . ∪ Ujm and ord({Uj1, . . . , Ujm) ≤ k. Let ν = min{m ∈ ω : there exist j1, . . . , jm ∈ {1, . . . , n} such that {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm} and c = {Uj1, . . . , Ujν } be a family such that {xj1, . . . , xjν } ⊆ Q ⊆ Uj1 ∪ . . . ∪ Ujν . Since r- dim(Q, X) ≤ k, there exists a family r = {V1, . . . , Vμ} of open subsets of X refinement of c such that Q ⊆ V1 ∪ . . . ∪ Vμ and ord(r) ≤ k. Clearly, it suffices to prove that {Uj1, . . . , Ujν } ⊆ r. Indeed, we suppose that there exists α ∈ {1, . . . , ν} such that Ujα /∈ r. Since xjα ∈ Q, there exists β ∈ {1, . . . , μ} such that xjα ∈ Vβ. By the fact that Ujα is the smallest open set of X containing the point xjα we have that Ujα ⊆ Vβ. Also, since Ujα /∈ r, we have Ujα �= Vβ. Therefore, Ujα ⊂ Vβ. Since r is a refinement of c, there exists γ ∈ {1, . . . , ν} such that Vβ ⊆ Ujγ . Hence, Ujα ⊂ Ujγ . We observe that Q ⊆ (Uj1 ∪ . . . ∪ Ujν ) \ Ujα, which is a contradiction by the choice of ν. Thus, c ⊆ r. Conversely, we suppose that there exists a family {Uj1, . . . , Ujm} such that {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ . . . ∪ Ujm and ord({Uj1 , . . . , Ujm) ≤ k. We prove that r-dim(Q, X) ≤ k. Indeed, let c be a finite family of open subsets of X such that Q ⊆ ∪{U : U ∈ c}. It suffices to prove that the family {Uj1, . . . , Ujm} is a refinement of c. For every i ∈ {1, . . . , m} there exists Vi ∈ c such that xji ∈ Uji ⊆ Vi. This means that the family {Uj1, . . . , Ujm} is a refinement of c. � Proposition 2.2. Let X = {x1, . . . , xn} be a finite space, where n > 1, and Q ⊆ X. Then, r-dim(Q, X) ≤ |Q| − 1. Proof. Let Q = {xj1, . . . , xjm}. The family {Uj1, . . . , Ujm} has m elements and, therefore, ord({Uj1 , . . . , Ujm}) ≤ m − 1. Thus, by Proposition 2.1, r-dim(Q, X) ≤ m − 1 = |Q| − 1. � 94 A. C. Megaritis Note 1. In the following propositions we suppose that X = {x1, . . . , xn} is a finite space with n elements, Q ⊆ X, T = (tij), i = 1, . . . , n, j = 1, . . . , n, the incidence matrix of X, and c1, . . . , cn the n columns of the matrix T . We denote by 1Q the n × 1 matrix ⎛ ⎜⎜⎜⎝ a1 a2 ... an ⎞ ⎟⎟⎟⎠ , where ai = { 1, if xi ∈ Q 0, otherwise. Example 2.3. Let X = {x1, x2, x3, x4, x5} and Q = {x1, x3, x4}. Then, 1Q = ⎛ ⎜⎜⎜⎜⎝ 1 0 1 1 0 ⎞ ⎟⎟⎟⎟⎠ . Proposition 2.4. If cj = 1Q and xj ∈ Q for some j ∈ {1, . . . , n}, then r-dim(Q, X) = 0. Proof. Since cj = 1Q, we have tij = 1 for every xi ∈ Q and, therefore, Q ⊆ Uj. Since ord({Uj}) = 0, by Proposition 2.1, we have r-dim(Q, X) = 0. � Proposition 2.5. Let cji, i = 1, . . . , m, be m columns of the matrix T . Then, cj1 + . . . + cjm ≥ 1Q if and only if Q ⊆ Uj1 ∪ . . . ∪ Ujm. Proof. Let cj1 +. . .+cjm ≥ 1Q. We prove that Q ⊆ Uj1 ∪. . .∪Ujm. Let xi0 ∈ Q. By the definition of the matrix T and by the assumption cj1 + . . . + cjm ≥ 1Q, there exists κ ∈ {1, . . . , m} such that ti0jκ = 1. Since Ujκ = {xi : tijκ = 1}, we have xi0 ∈ Ujκ . Thus, Q ⊆ Uj1 ∪ . . . ∪ Ujm. Conversely, we suppose that Q ⊆ Uj1 ∪ . . . ∪ Ujm. Then, for every xi ∈ Q there exists κ(i) ∈ {1, . . . , m} such that xi ∈ Ujκ(i) . Therefore, by the definition of the matrix T , tijκ(i) = 1. Thus, cj1 + . . . + cjm ≥ 1Q. � Proposition 2.6 (see Proposition 2.6 of [5]). Let cji, i = 1, . . . , m, be m columns of the matrix T and k = max(cj1 +. . .+cjm), that is k is the maximum element of the n × 1 matrix cj1 + . . . + cjm. Then, ord({Uj1, . . . , Ujm}) = k − 1. Definition 2.7. We define a preorder � on the set of all families {xj1, . . . , xjm} with {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm by {xj1, . . . , xjm1 } � {xj′1, . . . , xj′m2 } Relative dimension r-dim and finite spaces 95 if and only if {Uj1, . . . , Ujm1 } ⊆ {Uj′1, . . . , Uj′m2 }. Remark 2.8. The space X is T0 if and only if Ui = Uj implies xi = xj for every i, j (see [1]). Therefore, if the space X is T0, then the relation � is an order. We note that if the space X is T0, then there exists exactly one minimal family on the set of all families {xj1, . . . , xjm} with {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪· · ·∪Ujm . Proposition 2.9. Let {xi1, . . . , xiμ} ⊆ Q ⊆ {Ui1, . . . , Uiμ }, ν = min{m ∈ ω : there exist j1, . . . , jm ∈ {1, . . . , n} such that {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm}, and {xj1, . . . , xjν } ⊆ Q ⊆ {Uj1, . . . , Ujν }. Then, {xj1, . . . , xjν } � {xi1, . . . , xiμ}. Proof. The proof is similar to that of Proposition 2.1. � Proposition 2.10. Let {xj1, . . . , xjν } be a minimal family on the set of all families {xj1, . . . , xjm} with {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm. If ord({Uj1 , . . . , Ujν }) = k ≥ 0, then for every family {xr1, . . . , xrμ} with {xr1, . . . , xrμ} ⊆ Q ⊆ Ur1 ∪ · · · ∪ Urμ we have ord({Ur1, . . . , Urμ} ≥ k. Proof. Let {Ur1, . . . , Urμ} be a family such that {xr1, . . . , xrμ} ⊆ Q ⊆ Ur1 ∪ · · · ∪ Urμ. Then, {xj1, . . . , xjν } � {xr1, . . . , xrμ} and, therefore, {Uj1, . . . , Ujν } ⊆ {Ur1, . . . , Urμ}. Since ord({Uj1, . . . , Ujν }) = k, we have ord({Ur1, . . . , Urμ} ≥ k. � Proposition 2.11. Let {xj1, . . . , xjν } be a minimal family on the set of all families {xj1, . . . , xjm} with {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm. Then, r- dim(Q, X) = max(cj1 + . . . + cjν ) − 1. Proof. Let k = max(cj1 + . . . + cjν ). Then, by Proposition 2.6, we have ord({Uj1, . . . , Ujν }) = k − 1 and, therefore, by Proposition 2.1, r- dim(Q, X) ≤ k − 1. We prove that r- dim(Q, X) = k − 1. We suppose that r- dim(Q, X) < k − 1. Then, by Proposition 2.1, there exists a family {Ur1, . . . , Urμ} such that {xr1, . . . , xrμ} ⊆ Q ⊆ Ur1 ∪ · · · ∪ Urμ and ord({Ur1, . . . , Urμ}) < k − 1. 96 A. C. Megaritis Since ord({Uj1, . . . , Ujν }) = k − 1, by Proposition 2.10, we have ord({Ur1, . . . , Urμ}) ≥ k − 1 which is a contradiction. Thus, r- dim(Q, X) = k − 1. � Proposition 2.12. Let cji, i = 1, . . . , ν, be ν columns of the matrix T such that cj1 + . . . + cjν ≥ 1Q and {xj1, . . . , xjν } ⊆ Q. If cr1 + . . . + crq � 1Q for every {xr1, . . . , xrq } ⊆ Q and q < ν, then {xj1, . . . , xjν } is a minimal family on the set of all families {xj1, . . . , xjm} with {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪· · ·∪Ujm . Proof. Since cj1+. . .+cjν ≥ 1Q and cr1+. . .+crq � 1Q for every {xr1, . . . , xrq } ⊆ Q and q < m, by Proposition 2.5, we have ν = min{m ∈ ω : there exist j1, . . . , jm ∈ {1, . . . , n} such that {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm}. Thus, by Proposition 2.9, {xj1, . . . , xjν } is a minimal family on the set of all families {xj1, . . . , xjm} with {xj1, . . . , xjm} ⊆ Q ⊆ Uj1 ∪ · · · ∪ Ujm. � By Propositions 2.11 and 2.12 we have the following corollary. Corollary 2.13. Let cji, i = 1, . . . , ν, be ν columns of the matrix T such that cj1 + . . . + cjν ≥ 1Q and {xj1, . . . , xjν } ⊆ Q. If cr1 + . . . + crq � 1Q for every {xr1, . . . , xrq } ⊆ Q and q < ν, then r- dim(Q, X) = max(cj1 + . . . + cjν ) − 1. 3. An algorithm for computing the covering dimension In this section we give an algorithm of polynomial order for computing the dimension r-dim(Q, X), where Q is a subset of a finite space X, using the Propositions 2.11 and 2.5. Algorithm 3.1. Let X = {x1, . . . , xn} be a finite space of n elements, Q = {xλ1, . . . , xλl} ⊆ X, and T = (tij) the n × n incidence matrix of X. Our intended algorithm contains l − 1 steps: Step 1. Read the l columns cλ1, . . . , cλl of the matrix T . If some column is equal to 1Q, then print r-dim(Q, X) = 0. Otherwise go to the Step 2. Step 2. Find the sums cλj11 + cλj21 + . . . + cλj(l−1)1 for each {j11, j21, . . . , j(l−1)1} ⊆ {1, . . . , l}. If there exists {j011, j021, . . . , j0(l−1)1} ⊆ {1, . . . , l} such that cλ j0 11 + cλ j0 21 + . . . + cλ j0 (l−1)1 ≥ 1Q, then go to the Step 3. Relative dimension r-dim and finite spaces 97 Otherwise print r-dim(Q, X) = max(cλ1 + cλ2 + . . . + cλl) − 1. Step 3. Find the sums cλj12 + cλj22 + . . . + cλj(l−2)2 for each {j12, j22, . . . , j(l−2)2} ⊆ {j011, j021, . . . , j0(l−1)1}. If there exists {j012, j022, . . . , j0(l−2)2} ⊆ {j011, j021, . . . , j0(l−1)1} such that cλ j0 12 + cλ j0 22 + . . . + cλ j0 (l−2)2 ≥ 1Q, then go to the Step 4. Otherwise print r-dim(Q, X) = max(cλ j0 11 + cλ j0 21 + . . . + cλ j0 (l−1)1 ) − 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . Step l − 2. Find the sums cλj1(l−3) + cλj2(l−3) + cλj3(l−3) for each {j1(l−3), j2(l−3), j3(l−3)} ⊆ {j01(l−4), j02(l−4), j03(l−4), j04(l−4)}. If there exists {j01(l−3), j02(l−3), j03(l−3)} ⊆ {j01(l−4), j02(l−4), j03(l−4), j04(l−4)} such that cλ j0 1(l−3) + cλ j0 2(l−3) + cλ j0 3(l−3) ≥ 1Q, then go to the Step l − 1. Otherwise print r-dim(Q, X) = max(cλ j0 1(l−4) + cλ j0 2(l−4) + cλ j0 3(l−4) + cλ j0 4(l−4) ) − 1. Step l − 1. Find the sums cλj1(l−2) + cλj2(l−2) for each {j1(l−2), j2(l−2)} ⊆ {j01(l−3), j02(l−3), j03(l−3)}. If there exists {j01(l−2), j02(l−2)} ⊆ {j01(l−3), j02(l−3), j03(l−3)} such that cλ j0 1(l−2) + cλ j0 2(l−2) ≥ 1, then print r-dim(Q, X) = max(cλ j0 1(l−2) + cλ j0 2(l−2) ) − 1. Otherwise print r-dim(Q, X) = max(cλ j0 1(l−3) + cλ j0 2(l−3) + cλ j0 3(l−3) ) − 1. 98 A. C. Megaritis Example 3.2. Let X = {x1, x2, x3, x4} with the topology τ = {∅, {x2}, {x1, x2}, {x2, x3}, {x1, x2, x3}, X} and Q = {x1, x3}. Then, 1Q = ⎛ ⎜⎜⎝ 1 0 1 0 ⎞ ⎟⎟⎠ . We observe that U1 = {x1, x2}, U2 = {x2}, U3 = {x2, x3}, U4 = X. There- fore, T = ⎛ ⎜⎜⎝ 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 1 ⎞ ⎟⎟⎠ , c1 = ⎛ ⎜⎜⎝ 1 1 0 0 ⎞ ⎟⎟⎠ , c3 = ⎛ ⎜⎜⎝ 0 1 1 0 ⎞ ⎟⎟⎠ . Moreover, c1 + c3 = ⎛ ⎜⎜⎝ 1 2 1 0 ⎞ ⎟⎟⎠ ≥ 1Q and max(c1 + c3) = 2. Thus, r-dim(Q, X) = max(c1 + c3) − 1 = 1. 4. Remarks on the algorithm for computing the covering dimension of finite topological spaces Remark 4.1. Let A = (αij) be a n × n matrix and B = (βij) a m × m matrix. The Kronecker product of A and B (see [3]) is the mn × mn block matrix A ⊗ B = ⎛ ⎜⎝ α11B . . . α1nB ... ... ... αn1B . . . αnnB ⎞ ⎟⎠ . More explicitly, the Kronecker product of A and B is the matrix Relative dimension r-dim and finite spaces 99 ⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ α11β11 . . . α11β1m . . . α1nβ11 . . . α1nβ1m ... ... ... ... ... ... α11βm1 . . . α11βmm . . . α1nβm1 . . . α1nβmm ... ... ... ... αn1β11 . . . αn1β1m . . . αnnβ11 . . . αnnβ1m ... ... ... ... ... ... αn1βm1 . . . αn1βmm . . . αnnβm1 . . . αnnβmm ⎞ ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ . Let X = {x1, . . . , xn} be a finite space of n elements and Y = {y1, . . . , ym} a finite space of m elements. It is known that if TX is the incidence matrix of X and TY is the incidence matrix of Y , then the incidence matrix of X × Y = {(x1, y1), . . . , (x1, ym), . . . , (xn, y1), . . . , (xn, ym)} is the Kronecker product TX ⊗ TY of TX and TY (see [8]). Example 4.2. Let X = {x1, x2, x3} with the topology τX = {∅, {x2}, {x1, x2}, {x2, x3}, X} and Y = {y1, y2, y3, y4} with the topology τY = {∅, {y3}, {y1, y3}, {y2, y3}, {y1, y2, y3}, Y }. Also, let QX = {x1, x3} and QY = {y1, y2, y3}. Then, QX × QY = {(x1, y1), (x1, y2), (x1, y3), (x3, y1), (x3, y2), (x3, y3)} and 1QX = ⎛ ⎝ 10 1 ⎞ ⎠ , 1QY = ⎛ ⎜⎜⎝ 1 1 1 0 ⎞ ⎟⎟⎠ , 1QX×QY = ⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ 1 1 1 0 0 0 0 0 1 1 1 0 ⎞ ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ . The incidence matrix TX of X is TX = ⎛ ⎝ 1 0 01 1 1 0 0 1 ⎞ ⎠ 100 A. C. Megaritis and the incidence matrix TY of Y is TY = ⎛ ⎜⎜⎝ 1 0 0 1 0 1 0 1 1 1 1 1 0 0 0 1 ⎞ ⎟⎟⎠ . Therefore, the incidence matrix TX×Y of the product space X × Y is TX×Y = TX ⊗ TY = ⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 ⎞ ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ . We observe that c1 + c2 + c9 + c10 = ⎛ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝ 1 1 2 0 2 2 4 0 1 1 2 0 ⎞ ⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ > 1QX ×QY , cr1 + cr2 + cr3 � 1QX ×QY for every {r1, r2, r3} ⊆ {1, 2, 9, 10}, and max(c1 + c2 + c9 + c10) = 4. Thus, r-dim(QX × QY , X × Y ) = max(c1 + c2 + c9 + c10) − 1 = 3. Also, we observe that r-dim(QX, X) = 1 and r-dim(QY , Y ) = 1. Remark 4.3. Let X = {x1, . . . , xn} be a finite T0-space and Q ⊆ X. Then, there exists a finite space Y homeomorphic to X such that the incidence matrix TY of Y is an upper triangular matrix. Let h a homeomorphism from X to Y such that the incidence matrix TY of Y is an upper triangular matrix. In order to calculate the r-dim(Q, X) it suffices to calculate r-dim(h(Q), Y ). Relative dimension r-dim and finite spaces 101 Example 4.4. Let X = {x1, x2, x3} with the topology τX = {∅, {x2}, {x1, x2}, {x2, x3}, X} and Q = {x2, x3}. We consider the space Y = {y1, y2, y3} with the topology τY = {∅, {y1}, {y1, y2}, {y1, y3}, Y }. We observe that the map h : X → Y defined by h(x1) = y2, h(x2) = y1, and h(x3) = y3 is a homeomorphism from X to Y with h(Q) = {y1, y3}. The incidence matrix TY of Y is TY = ⎛ ⎝ 1 1 10 1 0 0 0 1 ⎞ ⎠ . Since c3 = ⎛ ⎝ 10 1 ⎞ ⎠ = 1h(Q), we have r-dim(h(Q), Y ) = 0. Therefore, r-dim(Q, X) = 0. Proposition 4.5. An upper bound on the number of iterations of the algorithm for computation of the dimension r-dim of a pair (Q, X), where Q is a subset of a finite space X, is the number 1 2 |Q|2 + 3 2 |Q| − 3. Proof. Let |Q| = l. We observe that the number of iterations the algorithm performs in Steps 1, 2, 3, 4, . . . , l − 2, l − 1 is l, l, l − 1, l − 2, . . . , 4, 3 respectively. Thus, the number of iterations the algorithm performs is l + l + (l − 1) + (l − 2) + . . . + 4 + 3 = l + (l − 2)(l + 3) 2 = 1 2 l2 + 3 2 l − 3 = 1 2 |Q|2 + 3 2 |Q| − 3. � 5. Problems In [9] (see also [6] and [7]) two relative covering dimensions are defined and studied which are denoted by dim and dim∗. The given two definitions below are actually the definitions of dimensions dim and dim∗ given in [9] for regular spaces. Definition 5.1. We denote by dim the (unique) function with domain the class of all subsets and range the set ω ∪ {−1, ∞}, satisfying the following condition dim(Q, X) ≤ n, where n ∈ {−1} ∪ ω if and only if for every finite open cover c of the space X there exists a finite open cover rQ of Q such that rQ is a refinement of c and ord(rQ) ≤ n. 102 A. C. Megaritis Definition 5.2. We denote by dim∗ the (unique) function with domain the class of all subsets and range the set ω ∪ {−1, ∞}, satisfying the following condition dim∗(Q, X) ≤ n, where n ∈ {−1} ∪ ω if and only if for every finite open cover c of the space X there exists a finite family r of open subsets of X refinement of c such that Q ⊆ ∪{V : V ∈ r} and ord(r) ≤ n. Problem 5.3. Find an algorithm for computing the dimension dim of a pair (Q, X), where Q is a subset of a finite space X, using matrix algebra. Problem 5.4. Find an algorithm for computing the dimension dim∗ of a pair (Q, X), where Q is a subset of a finite space X, using matrix algebra. Acknowledgements. The author would like to thank the referee for very helpful comments and suggestions. References [1] P. Alexandroff, Diskrete Räume, Mat. Sb. (N.S.) 2 (1937), 501–518. [2] R. Engelking, Theory of dimensions, finite and infinite, Sigma Series in Pure Mathe- matics, 10. Heldermann Verlag, Lemgo, 1995. viii+401 pp. [3] H. Eves, Elementary matrix theory, Dover Publications, Inc., New York, 1980. xvi+325 pp. [4] D. N. Georgiou and A. C. Megaritis, On a New Relative Invariant Covering Dimension, Extracta Mathematicae 25, no. 3 (2010), 263–275. [5] D. N. Georgiou and A. C. Megaritis, Covering dimension and finite spaces, Applied Mathematics and Computation 218 (2011), 3122–3130. [6] D. N. Georgiou and A. C. Megaritis, On the relative dimensions dim and dim∗ I, Ques- tions and Answers in General Topology 29 (2011), 1–16. [7] D. N. Georgiou and A. C. Megaritis, On the relative dimensions dim and dim∗ II, Questions and Answers in General Topology 29 (2011), 17–29. [8] M. Shiraki, On finite topological spaces, Rep. Fac. Sci. Kagoshima Univ. 1 1968 1-8. [9] J. Valuyeva, On relative dimension concepts, Questions Answers Gen. Topology 15, no. 1 (1997), 21–24. (Received November 2011 – Accepted March 2012) A. C. Megaritis (megariti@master.math.upatras.gr) Department of Accounting, Technological Educational Institute of Messolonghi, 30200 Messolonghi, Greece Relative dimension r-dim and finite spaces. By A. C. Megaritis