# S-Approximation: A New Approach to Algebraic Approximation

Authors: M. R. Hooshmandasl; A. Shakiba; A. K. Goharshady; A. Karimi
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

We intend to study a new class of algebraic approximations, calledS-approximations, and their properties. We have shown that S-approximations can be used for applied problems which cannot be modeled by inclusion based approximations. Also, in this work, we studied a subclass of S-approximations, called S
ℳ-approximations, and showed that this subclass preserves most of the properties of inclusion based approximations but is not necessarily inclusionbased. The paper concludes by studying some basic operations on S-approximations and counting the number of S-min functions.


---

## Body

## 1. Introduction

Uncertainty is often present in real-life applications. Uncertainty in noncrisp sets is characterized by nonempty boundary regions, in which nothing can be said about their elements with certainty. In classical set theory, a subsetA of a universe U induces a partition {
A
,
U
-
A
} over that universe. This partition can be interpreted as a knowledge on elements of U; that is, elements in A are indiscernible to each other and also the same thing holds for items in U
-
A. This knowledge may be improved to another partition, for example, P, whose items in each partition are indiscernible to each other. In consequence, for a subset A of U, the problem of whether x belongs to A or not, with respect to knowledge P, may become undecidable; that is, some elements indiscernible to x with respect to knowledge P may be in A, whereas some other indiscernible elements to x with knowledge P may not belong to A. To cope with such uncertainty, some tools were invented such as the Dempster-Shafer theory of evidence [1], theory of fuzzy sets [2–5], and theory of rough sets [6–8]. Rough set theory and fuzzy set theory are two independent approaches for uncertainty. There is a connection between rough set theory and Dempster-Shafer theory. Strictly speaking, lower and upper approximations of rough set theory correspond to the inner and outer reductions from Dempster-Shafer theory [9].Rough set theory and its generalizations are all based on the inclusion relation [7, 8, 10–15], which is a limitation in approximations. In this work, we introduce a new concept named S-approximation set. This concept is independent of inclusion relation and contains rough sets and their generalizations as special cases. We provide some examples of approximations using this new concept, which cannot be obtained by rough set theory.This paper is organized as follows. The notion ofS-approximation sets is proposed in Section 2, followed by considering some operations on them. The definition of S
M conditioned rough sets is proposed in Section 3 and the number of such sets is counted. Then we conclude the paper.


## 2.S-Approximation

In this section, with regard to Dempster’s multivalued mappings [16], we propose a new mathematical approach to study approximation spaces and we will show that this concept can be independent of inclusion relations and the rough set and its generalizations are all special cases of this concept.Definition 1.
AnS-approximation is the quadruple G
=
(
U
,
W
,
T
,
S
), where U and W are finite nonempty sets, T is a mapping of the form T
:
U
→
P
⋆
(
W
), and S is a mapping of the form S
:
P
⋆
(
W
)
×
P
⋆
(
W
)
→
{
0,1
}.
For a nonempty subsetX of W, the upper and lower approximations of X are defined as follows:
(1)
apr
¯
G
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
c
)
=
0
}
,
apr
_
G
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
)
=
1
}
,
where X
c is the complement of X with respect to W.Example 2.
LetU and W be nonempty finite sets and let R be a relation from U to W. We define G
=
(
U
,
W
,
T
,
S
), where T and S are defined as
(2)
T
(
x
)
=
[
x
]
R
=
{
y
∈
W
∣
x
R
y
}
,
S
(
A
,
B
)
=
{
1
,
A
⊆
B
,
0
,
otherwise
.
The upper approximation of X with respect to G, apr
¯
G
(
X
), is equal to R
¯
(
X
), the upper approximation of set X with respect to R in rough set, since
(3)
apr
¯
G
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
T
(
x
)
⊈
X
c
}
=
{
x
∈
U
∣
T
(
x
)
∩
X
≠
∅
}
=
{
x
∈
U
∣
[
x
]
R
∩
X
≠
∅
}
=
R
¯
(
X
)
.
Similarly, we can show that apr
_
G
(
X
) is equal to R
_
(
X
), which is the lower approximation of set X with respect to R in rough set.Example 3.
The pair(
V
,
H
), where V is a finite nonempty set of vertices and H is a collection {
E
1
,
…
,
E
m
} of subsets of V, is called a simple hypergraph if these two conditions hold:(i)
∪
i
=
1
m
E
i
=
V,
(ii)
E
i
⊆
E
j implies i
=
j.Let us define the S-approximation G
=
(
I
m
,
V
,
T
,
S
) such that I
m
=
{
1
,
…
,
m
}, T
(
i
)
=
E
i, and S is the inclusion function.
A subsetK of V is called a transversal of (
V
,
H
) if and only if K
∩
E
i
≠
∅ for each 1
≤
i
≤
m. It is easy to observe that K is a transversal of (
V
,
H
) if and only if apr
¯
G
(
K
)
=
I
m.Remark. For the sake of simplicity, we will use G
_
(
X
) and G
¯
(
X
) instead of apr
_
G
(
X
) and apr
¯
G
(
X
), respectively.


### 2.1. Operations onS-Approximation

Definition 4.
SupposeG
=
(
U
,
W
,
T
,
S
) is an S-approximation. One defines H
=
(
U
,
W
,
T
,
1
-
S
) as the complement of G.Proposition 5.
LetG
=
(
U
,
W
,
T
,
S
) be an S-approximation and H
=
(
U
,
W
,
T
,
S
′
=
1
-
S
) its complement. Also suppose that X
⊆
W. Then one has
(4)
G
¯
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
S
′
(
T
(
x
)
,
X
c
)
=
1
}
=
H
_
(
X
c
)
,
G
_
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
)
=
1
}
=
{
x
∈
U
∣
S
′
(
T
(
x
)
,
X
)
=
0
}
=
H
¯
(
X
c
)
.Definition 6.
LetW be a finite nonempty set. Consider the following:
(5)
Ω
T
(
W
)
=
{
S
∣
S
:
P
⋆
(
W
)
×
P
⋆
(
W
)
⟶
{
0,1
}
}
,
and S
1, S
2
∈
Ω
T
(
W
). Then one defines the following:
(6)
(
S
1
∧
S
2
)
(
A
,
B
)
=
S
1
(
A
,
B
)
∧
S
2
(
A
,
B
)
,
(
S
1
∨
S
2
)
(
A
,
B
)
=
S
1
(
A
,
B
)
∨
S
2
(
A
,
B
)
,
where A and B are arbitrary subsets of W.Definition 7.
LetG
1
=
(
U
,
W
,
T
,
S
1
) and G
2
=
(
U
,
W
,
T
,
S
2
) be two S-approximations. One defines G
1
∧
G
2 and G
1
∨
G
2 as
(7)
G
1
∧
G
2
=
(
U
,
W
,
T
,
S
1
∧
S
2
)
,
G
1
∨
G
2
=
(
U
,
W
,
T
,
S
1
∨
S
2
)
,
respectively.Proposition 8.
LetG
1
=
(
U
,
W
,
T
,
S
1
), G
2
=
(
U
,
W
,
T
,
S
2
), and G
=
(
U
,
W
,
T
,
S
=
S
1
∨
S
2
) be S-approximations. Then
(8)
G
¯
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
c
)
h
h
h
h
h
h
=
0
∧
S
2
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
c
)
=
0
}
∩
{
x
∈
U
∣
S
2
(
T
(
x
)
,
X
c
)
=
0
}
=
G
1
¯
(
X
)
∩
G
2
¯
(
X
)
,
G
_
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
)
=
1
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
)
=
1
∨
S
2
(
T
(
x
)
,
X
)
=
1
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
)
=
1
}
∪
{
x
∈
U
∣
S
2
(
T
(
x
)
,
X
)
=
1
}
=
G
1
_
(
X
)
∪
G
2
_
(
X
)
.
Similarly, for G
′
=
(
U
,
W
,
T
,
S
1
∧
S
2
), it can be shown that the following relations hold:
(9)
G
′
¯
(
X
)
=
G
1
¯
(
X
)
∪
G
2
¯
(
X
)
,
G
′
_
(
X
)
=
G
1
_
(
X
)
∩
G
2
_
(
X
)
.


## 2.1. Operations onS-Approximation

Definition 4.
SupposeG
=
(
U
,
W
,
T
,
S
) is an S-approximation. One defines H
=
(
U
,
W
,
T
,
1
-
S
) as the complement of G.Proposition 5.
LetG
=
(
U
,
W
,
T
,
S
) be an S-approximation and H
=
(
U
,
W
,
T
,
S
′
=
1
-
S
) its complement. Also suppose that X
⊆
W. Then one has
(4)
G
¯
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
S
′
(
T
(
x
)
,
X
c
)
=
1
}
=
H
_
(
X
c
)
,
G
_
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
)
=
1
}
=
{
x
∈
U
∣
S
′
(
T
(
x
)
,
X
)
=
0
}
=
H
¯
(
X
c
)
.Definition 6.
LetW be a finite nonempty set. Consider the following:
(5)
Ω
T
(
W
)
=
{
S
∣
S
:
P
⋆
(
W
)
×
P
⋆
(
W
)
⟶
{
0,1
}
}
,
and S
1, S
2
∈
Ω
T
(
W
). Then one defines the following:
(6)
(
S
1
∧
S
2
)
(
A
,
B
)
=
S
1
(
A
,
B
)
∧
S
2
(
A
,
B
)
,
(
S
1
∨
S
2
)
(
A
,
B
)
=
S
1
(
A
,
B
)
∨
S
2
(
A
,
B
)
,
where A and B are arbitrary subsets of W.Definition 7.
LetG
1
=
(
U
,
W
,
T
,
S
1
) and G
2
=
(
U
,
W
,
T
,
S
2
) be two S-approximations. One defines G
1
∧
G
2 and G
1
∨
G
2 as
(7)
G
1
∧
G
2
=
(
U
,
W
,
T
,
S
1
∧
S
2
)
,
G
1
∨
G
2
=
(
U
,
W
,
T
,
S
1
∨
S
2
)
,
respectively.Proposition 8.
LetG
1
=
(
U
,
W
,
T
,
S
1
), G
2
=
(
U
,
W
,
T
,
S
2
), and G
=
(
U
,
W
,
T
,
S
=
S
1
∨
S
2
) be S-approximations. Then
(8)
G
¯
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
c
)
h
h
h
h
h
h
=
0
∧
S
2
(
T
(
x
)
,
X
c
)
=
0
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
c
)
=
0
}
∩
{
x
∈
U
∣
S
2
(
T
(
x
)
,
X
c
)
=
0
}
=
G
1
¯
(
X
)
∩
G
2
¯
(
X
)
,
G
_
(
X
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
X
)
=
1
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
)
=
1
∨
S
2
(
T
(
x
)
,
X
)
=
1
}
=
{
x
∈
U
∣
S
1
(
T
(
x
)
,
X
)
=
1
}
∪
{
x
∈
U
∣
S
2
(
T
(
x
)
,
X
)
=
1
}
=
G
1
_
(
X
)
∪
G
2
_
(
X
)
.
Similarly, for G
′
=
(
U
,
W
,
T
,
S
1
∧
S
2
), it can be shown that the following relations hold:
(9)
G
′
¯
(
X
)
=
G
1
¯
(
X
)
∪
G
2
¯
(
X
)
,
G
′
_
(
X
)
=
G
1
_
(
X
)
∩
G
2
_
(
X
)
.


## 3.S
M-Approximations

In this section, we introduce and discuss a condition onS which is sufficient for the properties in Proposition 13 to hold. These properties are sometimes vital for many applications.In the next example we illustrate the fact that it is not necessary forS to be the inclusion function in order to satisfy the properties stated in Proposition 13.Example 9.
For arbitrary subsetsA, B
⊆
W, define the following:
(10)
S
(
A
,
B
)
=
{
1
,
if
A
∪
B
=
W
,
0
,
otherwise
.
It can be verified that this function is not the same as the inclusion function, but the properties of Proposition 13 hold for the S-approximation G
=
(
U
,
W
,
T
,
S
) with arbitrary chosen U, W, and T.The reason whyG in the above example satisfies the properties of Proposition 13 is that its S function meets the S-min condition introduced below.Definition 10 (S-min condition).
LetG
=
(
U
,
W
,
T
,
S
) be an S-approximation. One says S
:
P
⋆
(
W
)
×
P
⋆
(
W
)
→
{
0,1
} is a function in S
M class if it satisfies
(11)
S
(
A
,
B
∩
C
)
=
min
⁡
{
S
(
A
,
B
)
,
S
(
A
,
C
)
}
,
for arbitrary nonempty subsets A, B, and C of W. One says an S-approximation G
=
(
U
,
W
,
T
,
S
′
) is an S
M-approximation if S
′ belongs to the S
M class.Remark 11.
The inclusion function does belong to theS
M class but there are other noninclusion functions in this class as well.Example 12.
For arbitrary subsetsA, B, and X of W, define the following:
(12)
S
X
(
A
,
B
)
=
{
1
,
if
X
⊆
A
∩
B
,
0
,
otherwise
.
It is easy to check that S
X is a noninclusion member of the S
M class.Proposition 13.
LetG
=
(
U
,
W
,
T
,
S
) be an S
M-approximation. For all A, B
⊆
W and x
∈
U, the following hold: (1)
A
⊆
B
implies that, for all
X
⊆
W
,
S
(
X
,
B
c
)
≤
S
(
X
,
A
c
),
(2)
max
⁡
{
S
(
T
(
x
)
,
A
)
,
S
(
T
(
x
)
,
B
)
}
≤
S
(
T
(
x
)
,
A
∪
B
),
(3)
G
¯
(
A
∪
B
)
=
G
¯
(
A
)
∪
G
¯
(
B
)
,
(4)
G
_
(
A
∩
B
)
=
G
_
(
A
)
∩
G
_
(
B
)
,
(5)
A
⊆
B
implies that
G
_
(
A
)
⊆
G
_
(
B
)
,
(6)
A
⊆
B
implies that
G
¯
(
A
)
⊆
G
¯
(
B
)
,
(7)
G
_
(
A
)
∪
G
_
(
B
)
⊆
G
_
(
A
∪
B
)
,
(8)
G
¯
(
A
∩
B
)
⊆
G
¯
(
A
)
∩
G
¯
(
B
)
,
(9)
G
_
(
A
)
=
(
G
¯
(
A
c
)
)
c
,
(10)
G
¯
(
A
)
=
(
G
_
(
A
c
)
)
c
.Proof.
(1) For the first property, note thatA
⊆
B so B
c
=
B
c
∩
A
c. Hence, for all X
⊆
W, we have S
(
X
,
B
c
)
=
S
(
X
,
B
c
∩
A
c
)
=
min
⁡
{
S
(
X
,
B
c
)
,
S
(
X
,
A
c
)
}, which implies that S
(
X
,
B
c
)
≤
S
(
X
,
A
c
).
(2) For this property, we have(13)
S
(
T
(
x
)
,
A
)
=
S
(
T
(
x
)
,
A
∩
(
A
∪
B
)
)
=
min
⁡
{
S
(
T
(
x
)
,
A
)
,
S
(
T
(
x
)
,
A
∪
B
)
}
,
which implies that
(14)
S
(
T
(
x
)
,
A
)
≤
S
(
T
(
x
)
,
A
∪
B
)
.
By a similar argument for B, it can be shown that
(15)
S
(
T
(
x
)
,
B
)
≤
S
(
T
(
x
)
,
A
∪
B
)
.
By combining these inequalities,
(16)
max
⁡
{
S
(
T
(
x
)
,
A
)
,
S
(
T
(
x
)
,
B
)
}
≤
S
(
T
(
x
)
,
A
∪
B
)
.
(3) Consider the following:(17)
G
¯
(
A
∪
B
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
c
∩
B
c
)
=
0
}
=
{
x
∈
U
∣
min
⁡
{
S
(
T
(
x
)
,
A
c
)
,
S
(
T
(
x
)
,
B
c
)
}
=
0
}
=
G
¯
(
A
)
∪
G
¯
(
B
)
.
(4) Consider the following:(18)
G
_
(
A
∩
B
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
∩
B
)
=
1
}
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
)
=
1
,
S
(
T
(
x
)
,
B
)
=
1
}
=
G
_
(
A
)
∩
G
_
(
B
)
.
(5) Consider the following:(19)
G
_
(
A
)
=
G
_
(
A
∩
B
)
(
since
A
⊆
B
)
=
G
_
(
A
)
∩
G
_
(
B
)
(
by
property
(
1
)
)
.
which implies that G
_
(
A
)
⊆
G
_
(
B
).
(6) Consider the following:(20)
G
¯
(
A
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
c
)
=
0
}
⊆
{
x
∈
U
∣
S
(
T
(
x
)
,
B
c
)
=
0
}
(
by
property
(
1
)
)
=
G
¯
(
B
)
.
(7) Consider the following:(21)
G
_
(
A
)
∪
G
_
(
B
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
)
=
1
or
S
(
T
(
x
)
,
B
)
=
1
}
=
{
x
∈
U
∣
max
⁡
{
S
(
T
(
x
)
,
A
)
,
S
(
T
(
x
)
,
B
)
}
=
1
}
⊆
{
x
∈
U
∣
S
(
T
(
x
)
,
A
∪
B
)
=
1
}
(
by
property
(
1
)
)
⊆
G
_
(
A
∪
B
)
.
(8) Consider the following:(22)
G
¯
(
A
∩
B
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
c
∪
B
c
)
=
0
}
⊆
{
x
∈
U
∣
max
⁡
{
S
(
T
(
x
)
,
A
)
,
S
(
T
(
x
)
,
B
)
}
=
0
}
hhhhhhhhhhhhhhhhhhhhhhh
(
by
property
(
2
)
)
=
{
x
∈
U
∣
S
(
T
(
x
)
,
A
)
=
0
,
S
(
T
(
x
)
,
B
)
=
0
}
=
G
¯
(
A
)
∩
G
¯
(
B
)
,
The proof of properties (
9
) and (
10
) is entirely straightforward.In the next example, we show that, inS-rough sets, it is not always the case that G
_
(
A
)
⊆
G
¯
(
A
), although this property always holds in Pawlak’s rough sets.Example 14.
SupposeG
=
(
U
,
W
,
T
,
S
) is an S
M-approximation, where
(23)
S
(
A
,
B
)
=
{
1
,
A
∪
B
=
W
,
0
,
otherwise
,
U
=
{
a
}, and T
(
a
)
=
W
=
{
1,2
}.
In this caseG
¯
(
{
1
}
)
=
{
x
∈
U
∣
T
(
x
)
∪
{
2
}
≠
W
}
=
∅, while
(24)
G
_
(
{
1
}
)
=
{
x
∈
U
∣
T
(
x
)
∪
{
1
}
=
W
}
=
{
a
}
,
so G
_
(
{
1
}
)
⊈
G
¯
(
{
1
}
).


### 3.1. Cardinality of theS
M Class

Definition 15.
LetW be a nonempty finite set. A function f
:
P
⋆
(
W
)
→
{
0,1
} is said to be minimizing if, for each A
,
B
⊆
W,
(25)
f
(
A
∩
B
)
=
min
⁡
{
f
(
A
)
,
f
(
B
)
}
.Lemma 16.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function. For each A, B
⊆
W, if A
⊆
B, then f
(
A
)
≤
f
(
B
).Proof.
SinceA
⊆
B, A
=
A
∩
B, so by definition f
(
A
)
=
min
⁡
{
f
(
A
)
,
f
(
B
)
} which implies that f
(
A
)
≤
f
(
B
).Lemma 17.
LetG
=
(
U
,
W
,
T
,
S
) be an S
M-approximation and let |
W
|
=
n. One labels the nonempty subsets of W as {
A
1
,
…
,
A
2
n
-
1
}. Then there exist minimizing functions {
f
1
,
…
,
f
2
n
-
1
} of the form f
i
:
P
⋆
(
W
)
→
{
0,1
} such that, for every B
⊆
W and 1
≤
i
≤
n, S
(
A
i
,
B
)
=
f
i
(
B
).Proof.
It is straightforward.Lemma17 leads us towards counting the number and finding the structure of minimizing fs.Definition 18.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function. A nonempty subset ω of the set W is called an atom of f if and only if f
(
ω
)
=
1 and, for each proper nonempty subset of ω such as η, f
(
η
)
=
0.Proposition 19.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function and ω
1 and ω
2 two nonidentical atoms of f. Then ω
1
∩
ω
2
=
∅.Proof.
Letω
=
ω
1
∩
ω
2; then, since ω
1 and ω
2 are nonidentical atoms, ω
≠
ω
1 and ω
≠
ω
2. Suppose that ω
≠
∅. By Definition 15, f
(
ω
)
=
min
⁡
{
f
(
ω
1
)
,
f
(
ω
2
)
}
=
1, so ω is a proper subset of ω
1 and ω
2 and f
(
ω
)
=
1 which is a contradiction with Definition 18.Proposition 20.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function and Υ the set of all atoms of f. Then, for a subset X of W, f
(
X
)
=
1 if and only if there exists ω
∈
Υ such that ω
⊆
X.Proof.
It is obvious that iff
(
X
)
=
1, then at least one of the subsets of X is an atom. On the other hand, let ω
⊆
X be an atom of f; then, by Lemma 16, f
(
X
)
=
1.Proposition 21.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function, Υ the set of all atoms of f, and |
Υ
|
≥
2. Then, for each x
∈
W, {
x
} is an atom of f.Proof.
Letω
1 and ω
2 be two different atoms of f. Define A
=
ω
1
∪
{
x
} and B
=
ω
2
∪
{
x
}; then, by Proposition 20, f
(
A
)
=
f
(
B
)
=
1 and, by Proposition 19, A
∩
B
=
{
x
}. f is minimizing so f
(
{
x
}
)
=
f
(
A
∩
B
)
=
min
⁡
{
f
(
A
)
,
f
(
B
)
}
=
1; hence {
x
} is an atom of f.By previous propositions, it is clear that we have either no atoms, exactly one atom, or an atom per element.Proposition 22.
DefineF as the set of all minimizing functions f of the form f
:
P
⋆
(
W
)
→
{
0,1
}, where |
W
|
=
n
≥
2. Then the total number of elements in F is equal to 2
n
+
1.Proof.
To count the number of elements inF, we consider these three cases for each f
∈
F. (i)
f does not have any atoms: in this case, f is determined uniquely. (f
(
X
)
=
0 for each nonempty X
⊆
W.)
(ii)
Each unary subset off forms an atom: in this case, f is determined uniquely too. (f
(
X
)
=
1 for each nonempty X
⊆
W.)
(iii)
There is exactly one atom: in this case, we can choose2
n
-
1 different atoms (excluding ∅) giving us 2
n
-
1 different fs. In case n
=
1, this case is a repetition of the previous case.Proposition 23.
LetW be a nonempty finite set of size n
≥
2. The total number of different functions S
:
P
⋆
(
W
)
×
P
⋆
(
W
)
→
{
0,1
} which belong to the S-min class is equal to (
2
n
+
1
)
2
n
-
1.Proof.
This number can be obtained using the multiplication principle, Lemma17, and Proposition 22.


## 3.1. Cardinality of theS
M Class

Definition 15.
LetW be a nonempty finite set. A function f
:
P
⋆
(
W
)
→
{
0,1
} is said to be minimizing if, for each A
,
B
⊆
W,
(25)
f
(
A
∩
B
)
=
min
⁡
{
f
(
A
)
,
f
(
B
)
}
.Lemma 16.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function. For each A, B
⊆
W, if A
⊆
B, then f
(
A
)
≤
f
(
B
).Proof.
SinceA
⊆
B, A
=
A
∩
B, so by definition f
(
A
)
=
min
⁡
{
f
(
A
)
,
f
(
B
)
} which implies that f
(
A
)
≤
f
(
B
).Lemma 17.
LetG
=
(
U
,
W
,
T
,
S
) be an S
M-approximation and let |
W
|
=
n. One labels the nonempty subsets of W as {
A
1
,
…
,
A
2
n
-
1
}. Then there exist minimizing functions {
f
1
,
…
,
f
2
n
-
1
} of the form f
i
:
P
⋆
(
W
)
→
{
0,1
} such that, for every B
⊆
W and 1
≤
i
≤
n, S
(
A
i
,
B
)
=
f
i
(
B
).Proof.
It is straightforward.Lemma17 leads us towards counting the number and finding the structure of minimizing fs.Definition 18.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function. A nonempty subset ω of the set W is called an atom of f if and only if f
(
ω
)
=
1 and, for each proper nonempty subset of ω such as η, f
(
η
)
=
0.Proposition 19.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function and ω
1 and ω
2 two nonidentical atoms of f. Then ω
1
∩
ω
2
=
∅.Proof.
Letω
=
ω
1
∩
ω
2; then, since ω
1 and ω
2 are nonidentical atoms, ω
≠
ω
1 and ω
≠
ω
2. Suppose that ω
≠
∅. By Definition 15, f
(
ω
)
=
min
⁡
{
f
(
ω
1
)
,
f
(
ω
2
)
}
=
1, so ω is a proper subset of ω
1 and ω
2 and f
(
ω
)
=
1 which is a contradiction with Definition 18.Proposition 20.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function and Υ the set of all atoms of f. Then, for a subset X of W, f
(
X
)
=
1 if and only if there exists ω
∈
Υ such that ω
⊆
X.Proof.
It is obvious that iff
(
X
)
=
1, then at least one of the subsets of X is an atom. On the other hand, let ω
⊆
X be an atom of f; then, by Lemma 16, f
(
X
)
=
1.Proposition 21.
Letf
:
P
⋆
(
W
)
→
{
0,1
} be a minimizing function, Υ the set of all atoms of f, and |
Υ
|
≥
2. Then, for each x
∈
W, {
x
} is an atom of f.Proof.
Letω
1 and ω
2 be two different atoms of f. Define A
=
ω
1
∪
{
x
} and B
=
ω
2
∪
{
x
}; then, by Proposition 20, f
(
A
)
=
f
(
B
)
=
1 and, by Proposition 19, A
∩
B
=
{
x
}. f is minimizing so f
(
{
x
}
)
=
f
(
A
∩
B
)
=
min
⁡
{
f
(
A
)
,
f
(
B
)
}
=
1; hence {
x
} is an atom of f.By previous propositions, it is clear that we have either no atoms, exactly one atom, or an atom per element.Proposition 22.
DefineF as the set of all minimizing functions f of the form f
:
P
⋆
(
W
)
→
{
0,1
}, where |
W
|
=
n
≥
2. Then the total number of elements in F is equal to 2
n
+
1.Proof.
To count the number of elements inF, we consider these three cases for each f
∈
F. (i)
f does not have any atoms: in this case, f is determined uniquely. (f
(
X
)
=
0 for each nonempty X
⊆
W.)
(ii)
Each unary subset off forms an atom: in this case, f is determined uniquely too. (f
(
X
)
=
1 for each nonempty X
⊆
W.)
(iii)
There is exactly one atom: in this case, we can choose2
n
-
1 different atoms (excluding ∅) giving us 2
n
-
1 different fs. In case n
=
1, this case is a repetition of the previous case.Proposition 23.
LetW be a nonempty finite set of size n
≥
2. The total number of different functions S
:
P
⋆
(
W
)
×
P
⋆
(
W
)
→
{
0,1
} which belong to the S-min class is equal to (
2
n
+
1
)
2
n
-
1.Proof.
This number can be obtained using the multiplication principle, Lemma17, and Proposition 22.


## 4. Conclusion

In this paper, we proposed a new class of algebraic approximation, calledS-approximation sets. Corresponding to the problem under consideration, we can define the elements of S-approximation set for obtaining the approximations. Moreover, we investigated the properties of a subclass of S-approximation sets, S
M-approximation sets. We have shown that this subclass preserves most of the properties of inclusion based approximations but is not necessarily inclusion based. Finally, we have considered some basic operations on S-approximation sets and counted the number of functions which have the S
M property.



---

*Source: 909684-2014-04-28.xml*