Upgrading a Multifuncoid
∗
May 1, 2012
Abstract
I define the concepts of multifuncoid (and completary multifun-
coid) and upgrading. Then I conjecture that upgrading of certain mul-
tifuncoids are multifuncoids (and that upgrading certain completary mul-
tifuncoids are completary multifuncoids). I have proved the conjectures
for n 6 2.
The main conjecture from this article is now p roved in the article
“Multidimensional Funcoids“
This short article is the first my public writing wher e I introduce the concept
of multidimensional funcoid which I am investigating now.
Refer to this Web site for the theory which I now attempt to generalize.
1 Background
1.1 About some p osets
Let A is a poset that is a set partially ordered by a relation ≥.
If A is a join-semilattice, I will denote a ⊔ b join o f its elements. (Dually for
a meet-semilattice I will de note a ⊓ b meet of its elements.)
If A = A
i∈n
is a family o f posets, then I will denote
Q
A the product order
on A that is we have for every a, b ∈
Q
A
a ≥ b ⇔ ∀i ∈ n : a
i
≥ b
i
.
Note that if every A
i
is a join-semilattice then
Q
A is als o a join-semilattice
and
a ⊔ b = λi ∈ n : a
i
⊔ b
i
.
I will denote A
n
=
Q
i∈n
A for every pose t A and an index set n.
∗
Keywords: multifuncoid, filtrator; A.M.S. subject classification: 54J05, 54A99,
54B99, 54D35, 54D70, 54E05
1
1.2 Filtrators and upgrading
Definition 1 A filtrator is a pair (A; Z) of a poset A and its subset Z.
See [2] for a detailed study of filtrators .
Having fixed a filtrator, we define:
Definition 2 up x = {Y ∈ Z | Y > x} for every X ∈ A.
Definition 3 E
∗
K = {L ∈ A | up L ⊆ K} (upgrading the set K) for every
K ∈ PZ.
1.3 Multifuncoids
Definition 4 A free star on a join-semilattice A with least element 0 is a set
S such that 0 6∈ S and
∀A, B ∈ A : (A ⊔ B ∈ S ⇔ A ∈ S ∨ B ∈ S) .
I will denote the set of free stars on A as A Star.
Let n be a s e t. As an example, n may be an ordinal, n may be a natural
number, considered as a set by the formula n = {0, . . . , n − 1}. Let A = A
i∈n
is a family of posets index ed by the set n.
Definition 5 Let f ∈ P
Q
A, i ∈ dom A, L ∈
Q
A|
(dom A)\{i}
.
(val f )
i
L = {X ∈ A
i
| L ∪ {(i; X)} ∈ f} .
(“val” is an abbreviation of the word “value”.)
Proposition 1 f can be restored knowing (val f)
i
for some i ∈ n.
Proof f = {K ∈
Q
A | K ∈ f } =
L ∪ {(i; X)} | L ∈
Q
A|
(dom A)\{i}
, X ∈ A
i
, L ∪ {(i; X)} ∈ f
=
L ∪ {(i; X)} | L ∈
Q
A|
(dom A)\{i}
, X ∈ (val f)
i
L
.
Definition 6 Let A is a family of join-semilattices. A pre-multidimensional
funcoid (or pre-multifuncoi d for short) of the form A is an f ∈ P
Q
A
such that we have that: (val f )
i
L is a free star for every i ∈ dom A, L ∈
Q
A|
(dom A)\{i}
.
Definition 7 A multidimensional funcoid ( or multifuncoid for short) is
a pre-multifuncoid which is an upper set.
Proposition 2 If L ∈
Q
A and L
i
= 0
A
i
for some i then L 6∈ f if f is a
pre-mu ltifuncoid.
Proof Let K = L|
dom A\{i}
. We have 0 6∈ (val f)
i
K; K ∪ {(i; 0 )} 6∈ f ; L 6∈ f .
2
Definition 8 Infinitary pre-multifuncoid is such an n-ary multifuncoid that
n is infinite; finitary pre-mul tifuncoid is such an n-ary multifuncoid that n
is finite.
Definition 9 Let A is a family of join-semilattices. A completary multi fun-
coid of the form A is an f ∈ P
Q
i∈dom A
A
i
such that
1. L
0
⊔ L
1
∈ f ⇔ ∃c ∈ {0, 1}
n
:
λi ∈ n : L
c(i)
i
∈ f for every L
0
, L
1
∈
Q
A.
2. If L ∈
Q
A and L
i
= 0
A
i
for some i then ¬f L.
Proposition 3 A completary multifuncoid is a multifuncoid.
Proof Let f is a completary multifuncoid.
Let K ∈
Q
i∈(dom A)\{i}
A
i
. Let L
0
= K ∪ {(i; X
0
)}, L
1
= K ∪ {(i; X
1
)}
for some X
0
, X
1
∈ A
i
. Then X
0
⊔ X
1
∈ (val f )
i
K ⇔ L
0
⊔ L
1
∈ f ⇔ ∃k ∈
{0, 1} : K ∪ {(i; X
k
)} ∈ f ⇔ K ∪ {(i; X
0
)} ∈ f ∨ K ∪ {(i; X
1
)} ∈ f ⇔ X
0
∈
(val f )
i
K ∨ X
1
∈ (val f )
i
K.
So (val f)
i
K is a free star (taken in account that K
i
= 0
A
i
⇒ f 6∈ K).
It remained to prove that f is an upper set. Let L
0
≤ L
1
for some L
0
, L
1
∈
Q
A and L
0
∈ f . Then taking c = n × { 0} we get λi ∈ n : L
c(i)
i = λi ∈ n :
L
0
i = L
0
∈ f and thus L
1
= L
0
⊔ L
1
∈ f .
Proposition 4 Every finitary pre-multifuncoid is completary.
Proof ∃c ∈ {0, 1}
n
: (λi ∈ n : L
c(i)
i) ∈ f ⇔
∃c ∈ {0, 1}
n−1
: ({(n − 1; L
0
(n − 1))} ∪ {(i; L
c(i)
i) | i ∈ n − 1} ∈ f ∨
{(n − 1; L
1
(n − 1))} ∪ { (i; L
c(i)
i) | i ∈ n − 1} ∈ f) ⇔ ∃c ∈ {0, 1}
n−1
:
{(n − 1; L
0
(n − 1) ⊔ L
1
(n − 1))} ∪ {(i; L
c(i)
i) | i ∈ n − 1} ∈ f ⇔ . . . ⇔
{(i; L
0
i ⊔ L
1
i) | i ∈ n} ∈ f .
Theorem 1 For finite n the following are the same:
1. pre-mu ltifuncoids;
2. multifuncoids;
3. completary multifuncoids.
Proof f is a finitary pre-multifuncoid ⇒ f is a finitary completary multifun-
coid.
f is a finitary completary multifuncoid ⇒ f is a finitary multifuncoid.
f is a finitary multifuncoid ⇒ f is a finitary pre-multifuncoid.
As it will b e clear from below, (finitary) multifuncoids are a generalization
of funco ids [1].
I will deno te AFCD the se t of multifuncoids for a finite family A of join-
semilattices.
3
2 Open problems
Conjecture 1 Let ℧ be a set , F be the set of filters on ℧ ordered reverse to
set-theoretic inclusion, P be the set of principal filters on ℧, let n be an index
set. Consider the filtrator (F
n
; P
n
). If f is a multifuncoid of the form P
n
, then
E
∗
f is a multifuncoid of the form F
n
.
A similar conjecture about completary multifuncoids:
Conjecture 2 Let ℧ be a set , F be the set of filters on ℧ ordered reverse to
set-theoretic inclusion, P be the set of principal filters on ℧, let n be an index
set. Consider the filtrator (F
n
; P
n
). If f is a completary multifuncoid of the
form P
n
, then E
∗
f is a completary mult ifuncoid of the form F
n
.
A weaker conjecture:
Conjecture 3 Let ℧ be a set , F be the set of filters on ℧ ordered reverse to
set-theoretic inclusion, P be the set of principal filters on ℧, let n be an index
set. Consider the filtrator (F
n
; P
n
). If f is a completary multifuncoid of the
form P
n
, then E
∗
f is a multifuncoid of the form F
n
.
For finite n all three conjectures are equivalent.
For n = 0 the conjecture is trivial. For n = 1 it can be proved using the
theory of filters [2]. For n = 2 we can prove it using the theory of funcoids [1].
For card n > 3 (finite and infinite) the problem is open.
The full proo fs for c ard n 6 2 are presented below.
If a conjecture will be proved true, we may generalize it for a wider set of
filtrators.
3 Preliminary Results
3.1 Isomorphic filt rators
We will use the concept of isomorphic filtrators in the below proo fs.
An isom orphism from a filtrator (A
0
; Z
0
) to a filtrator (A
1
; Z
1
) is an order
embedding ϕ from A
0
to A
1
such that the image of Z
0
under ϕ is exactly Z
1
.
Two filtrators are isomorphic when there exist an isomorphism fr om one to
the other.
It is triv ial that neither the prope rty of be ing a multifuncoid, nor the result
of upgrading does change under an isomorphism.
3.2 The proof of the conjecture for card n 6 2
The below constitutes a proof of my conjecture for n ∈ {0, 1, 2} as well as n
being any set of cardinality card n 6 2, because a particular index se t doe s not
matter, just it’s cardinality.
Let Z = P
n
and A = F
n
.
4
3.2.1 The proof for n = 0
In this case a multifuncoid f of the form Z = P
0
= {()} is an element of the set
PB
0
= {{()}} that is f = {()}. Obviously f is an upper set. Then
E
∗
f =
L ∈ F
0
| up L ⊆ f
= {() | up () ⊆ {()}} = {() | {()} ⊆ {( )}} = {()} .
For i = dom F
0
we have (val f)
i
L is a free star just because i doesn’t exist.
Obviously E
∗
f is a n upper set.
So E
∗
f is a multifuncoid of the form F
0
.
3.2.2 The proof for n = 1
We will use notation from [2].
Lemma 1 The upgrading (regarding the filtrator (F; P)) of every free star on
P is a free star on F.
Proof Let f is a free star on P. Then (theorem 45 in [2]) there exist a g ∈ F
such that ∂g = f .
E
∗
f = {L ∈ F | up L ⊆ ∂g} = {L ∈ F | L 6≍ g}. It remained to prove
that {L ∈ F | L 6≍ g} is a free star.
Obviously 0
F
6∈ {L ∈ F | L 6≍ g}.
For every A, B ∈ {L ∈ F | L 6≍ g} we have A⊔B ∈ {L ∈ F | L 6≍ g} ⇔
(A ⊔ B) ⊓ g 6= 0
F
⇔ (A ⊓ g) ⊔ (B ⊓ g) 6= 0
F
⇔ A ⊓ g 6= 0
F
∨ B ⊓ g 6= 0
F
⇔ A ∈
{L ∈ F | L 6≍ g} ∨ B ∈ {L ∈ F | L 6≍ g}.
The proof is finished.
Let Q be the set of all multifuncoids of the form A
1
where A is a join-
semilattice with least element. Then f ∈ Q if and only if (val f )
0
∅ is a free
star.
But (val f )
0
∅ = {X ∈ A | {(0; X)} ∈ f } = {X ∈ A | f0 = X} = f 0.
So it uis easy to show that the filtrator of the form
F
1
FCD; P
1
FCD
is
isomorphic to the filtrator (F Star; P Star).
Thus by the lemma upgrading a multifuncoid of the form P
1
is a multifuncoid
of the form F
1
.
3.2.3 The proof for n = 2
An f is a (finitary) multifuncoid of the form A × B (for A, B being join-
semilattices with least elements) iff all the following:
1. (val f )
0
L is a free star for every L = {(1; Y )} where Y ∈ B;
2. (val f )
1
L is a free star for every L = {(0; X)} where X ∈ A;
what is equal to the following:
1. {X ∈ A | X f Y } is a free star for e very Y ∈ B;
5
2. {Y ∈ B | X f Y } is a free star for every X ∈ A;
what is equal to the following:
1. (I ⊔ J) f Y ⇔ I f Y ∨ J f Y and not 0 f Y for every Y ∈ B, I, J ∈ A;
2. X f (I ⊔ J) ⇔ X f I ∨ X f J and not X f 0 for every X ∈ A, I, J ∈ B.
By the way, it implies that f 7→ [f ]
∗
is a bijection from the set of funcoids from
℧
0
to ℧
1
into the set of multifuncoids of the form P℧
0
× P℧
1
, for every sets
℧
0
and ℧
1
.
Now supp ose f is a multifuncoid of the form P
2
. Then:
1. (I ⊔ J) f Y ⇔ I f Y ∨ J f Y and not 0 f Y for every Y, I, J ∈ P;
2. X f (I ⊔ J) ⇔ X f I ∨ X f J and not X f 0. for every X, I, J ∈ P.
Thus multifuncoids of the fo rm P
2
are essentially equivalent to funcoids from
P to P ([1]), formally: there exist a funcoid f
′
such that [f
′
]
∗
= f .
E
∗
f =
L ∈ F
2
| up L ⊆ f
= {(L
0
; L
1
) | L
0
, L
1
∈ F, ∀g
0
∈ up L
0
, g
1
∈ up L
1
: (g
0
; g
1
) ∈ f } =
(L
0
; L
1
) | L
0
, L
1
∈ F, ∀g
0
∈ up L
0
, g
1
∈ up L
1
: g
0
[f
′
]
∗
g
1
= {(L
0
; L
1
) | L
0
, L
1
∈ F, L
0
[f
′
] L
1
} =
[f
′
].
Thus:
1. (I ⊔ J) (E
∗
f) Y ⇔ I (E
∗
f) Y ∨ J (E
∗
f) Y and not 0 (E
∗
f) Y for every
Y, I, J ∈ F;
2. X (E
∗
f) (I ⊔ J) ⇔ X (E
∗
f) I ∨ X (E
∗
f) J and not X (E
∗
f) 0 for every
X, I, J ∈ F.
that is E
∗
f is a multifuncoid of the form F
2
.
References
[1] Victor Porton. Funcoids and reloids. At
http://www.mathematics21.org/binaries/funcoids-reloids.pdf.
[2] Victor Porton. Filters on posets and generalizations. International Journal
of Pure and Applied Mathematics, 74(1):55–119, 2012.
6
