Algebraic General Topology. Vol 1: Paperback / E-book || Axiomatic Theory of Formulas: Paperback / E-book

As an Amazon Associate I earn from qualifying purchases.

A New Kind of Pr oduct of Ordinal Number of Rela-
tions having Ordinal Numbers of Ar guments
by Victor Porton
Email: porton@narod.ru
Web: http://www.mathematics21.org
Abstract
Innite associativity is defined for functions taking an ordinal numbers of arguments. As an
important example of an infinite associative function I dene ordinated product and research
its properties. Ordinated product is an innitely associative function.
Keywords: innite associativity, abstract algebra, set theory, ordinal numbers, product,
relations
A.M.S. subject classification: 05C25, 03E10
1 Introduction
We will consider some function f which takes an arbitrary ordinal number of arguments. That is
f can be taken for arbitary (small, if to be precise) ordinal number of arguments. More formally:
Let x = x
in
is a family indexed by an ordinal n. Then f (x) can be taken. The same function f
can take different number of argu ments. (See below for the exact definition.)
Some of such functions f ar e associative in the sense defined below. If a f unction is associative
in the below defined sense, then the binary operation induced by this function is associative in the
usual meaning of the word “associativity” as defined in basic alge bra.
I also introduce and research an important example o f infinitely associative function, which I
call ordinated product.
Note that my searching about infinite associativity and ordinals in Internet has provided no
useful results. As such there is a reason to assume that my research of generalized associativity in
terms of ordinals is novel.
2 Used notation
We identify natural numbers with fin ite Von Neumann’s ordinals (furt her just ordinals or ordinal
numbers).
For simplicity we will deal w ith sma ll sets (member s of a Grothendieck universe). We will denote
the Grothendieck universe (aka universal set) as .
(λx D: f (x ))=
def
{(x; f (x)) | x D } for every set D and a form f taking x as argument.
I will denote a tuple of n ele ments like Ja
0
;
; a
n1
K. By definition
Ja
0
;
; a
n1
K = {(0; a
0
),
, (n 1; a
n1
)}.
Note that an ordered pair (a; b) is not the same as the tuple Ja; bK of two elements.
Definition 1. An anchored re lation is a tuple Jn; rK where n is an index set and r is an n-ary
relation.
For an anchored relation arityJn;rK = n. The graph
1
of Jn; rK is defined as follows: GRJn; rK=r.
Definition 2. Pr
i
is a small function defined by the formula
Pr
i
f = {x
i
| x f }
1. It is unrelated with graph theory.
1
for every small n- ary relation f where n is an ordinal number and i n. Particularly for every n-
ary relation f and i n where n N.
Pr
i
f = {x
i
| Jx
0
,
, x
n1
K f }.
Recall that cartesian product is defined as follows:
Y
a =
z
[
im a
dom a
| i dom a: z(i) a
i
.
Obvious 3. If a is a small function, then
Q
a = {z
dom a
| i dom a: z(i) a
i
}.
2.1 Currying and uncurrying
2.1.1 The customary definition
Let X, Y , Z are sets.
We will consider variables x X and y Y .
Let a function f Z
X ×Y
. Then curry(f) (Z
Y
)
X
is the function defined by the formula
(curry(f )x) y = f(x; y).
Let now f (Z
Y
)
X
. Then uncurry(f) Z
X ×Y
is the functio n defined by the formula
uncurry(f )(x; y) = (fx) y.
Obvious 4.
1. uncurry(curry(f )) = f for every f Z
X ×Y
.
2. curry(uncurry(f )) = f for every f (Z
Y
)
X
.
2.1.2 Currying and uncurrying with a dependent variable
Let X, Z are sets and Y is a function with the domain X. (Vaguely saying, Y is a variable dependent
on X.)
The disjoint union
`
Y =
S
{{i} × Y
i
| i dom Y } = {(i; x) | i dom Y , x Y
i
}.
We will consider variables x X and y Y
x
.
Let a function f Z
`
iX
Y
i
(or equivalently f Z
`
Y
). Then curry(f)
Q
iX
Z
Y
i
is the
function defined by the fo rmula (c urry(f )x) y = f (x ; y).
Let now f
Q
iX
Z
Y
i
. Then uncurry(f) Z
`
i X
Y
i
is the function defined by the formula
uncurry(f )(x; y) = (fx) y.
Obvious 5.
1. uncurry(curry(f )) = f for every f Z
`
iX
Y
i
.
2. curry(uncurry(f )) = f for every f
Q
iX
Z
Y
i
.
Remark 6. There is nothing said anything about currying with dependent variables in Wikipedia.
Am I really the first person who fo rmulated t his simple generalization of currying and uncurrying?
2.2 Functions with ordinal number s of argum ents
Let Ord is the set o f small ordinal numbers.
If X and Y are sets and n is an ordinal number, the set of functions taking n arguments on
the set X and returning a value in Y is Y
X
n
.
The set of all small functions taking ordinal numbers of arguments is Y
S
nOrd
X
n
.
I will denot e OrdVar(X) =
S
n Ord
X
n
and call it ordinal variadic. (“Var” in this notation is
taken from the word variadic in the collocation variadic function used in computer science.)
3 On sums of ord inals
Let a is an ordinal-inde xed family of ordinals.
2 Section 3
Proposition 7.
`
a with lexigraphic order is a well-ordered set.
Proof. L e t S is non-empty sub set of
`
a.
Take i
0
= inf Pr
0
S and x
0
= inf a
i
0
(these exist by properties of ordinals). Then (i
0
; x
0
) is the
least element of S.
Definition 8.
P
a is the unique ordinal order-isomorphic to
`
a.
This ordinal exists and is unique because our set is well-ordered.
Remark 9. An infinite sum of ordina ls is not c ustomary defined.
The structured sum
L
a of a is an order isomorphism from lexig raphically ordered set
`
a
into
P
a.
There exist ( for a given a) exactly one structured sum, by properties of well-ordered sets.
Obvious 10.
P
a = im
L
a.
Theorem 11. (
L
a)(n; x) =
P
in
a
i
+ x.
Proof. We need to prove that it is an order isomorphism. Let’s prove it is an injection that is
m > n
P
im
a
i
+ x >
P
in
a
i
+ x and y > x
P
in
a
i
+ y >
P
in
a
i
+ x.
Really, if m > n then
P
im
a
i
+ x >
P
in+1
a
i
+ x >
P
in
a
i
+ x. The second formula is true
by properties of ordinals.
Let’s prove that it is a surjection. Let r
P
a. There exist n dom a and x a
n
such that
r = (
L
a)(n; x). Thus r = (
L
a)(n; 0) + x =
P
in
a
i
+ x because (
L
a)(n; 0) =
P
in
a
i
since
(n; 0) has
P
in
a
i
predecessors.
4 Ordinated product
4.1 Introduction
Ordinated product defined below is a variation of cartesian product, but is associative unlike
cartesian product. However, ordinated product unlike cartesian product is defined not for arbitrary
sets, but only for relations having ordinal numbers of arguments.
Let F indexed by an ordinal number is a small family of anchored relations.
4.2 Concatena tion
Definition 12. Le t z is an indexed by an ordinal number family of functions each taking an ordinal
number of arguments. The concatenation of z is
concat z = uncurry(z)
M
(dom z)
1
.
Obvious 1 3. If z is a nite family of finitary functions, it is c oncatenation of dom z tuples in the
usual sense (as it is commonly used in computer s cience).
Proposition 14. If z
Q
(GR F ) then concat z = uncurry(z) (
L
(arity F ))
1
.
Proof. If z
Q
(GR F ) then dom z(i) = dom (GR F )
i
= dom F
i
= arity F
i
for every i dom F .
Thus dom z = arity F .
Proposition 15. dom conc at z =
P
idom z
dom z
i
.
Proof. Because dom (
L
(dom z))
1
=
P
idom F
dom z
i
, it is enough to pr ove that
dom uncurry(z) = dom
M
(dom z).
Ordinated product 3
Really,
dom
M
(dom z) = {(i; x) | i dom (dom z), x do m z
i
} = {(i; x) | i dom z, x dom z
i
} =
a
z
and dom uncurry(z) =
`
iX
z
i
=
`
z.
4.3 Finite example
If F is a finite fa mily (indexed by a natural number dom F ) of anchored finitary re lat ions, then by
definition GR
Q
(ord)
F = {Ja
0,0
;
; a
0,arity F
0
1
;
; a
dom F 1,0
;
; a
dom F 1,arity F
dom F 1
1
K | Ja
0,0
;
; a
0,arity F
0
1
K GR F
0
Ja
dom F 1,arity F
dom F 1
1
K GR F
dom F 1
} and
arity
Y
(ord)
F = arity F
0
+
+ arity F
dom F 1
.
The a bove formula can be shortened to
GR
Y
(ord)
F =
concat z | z
Y
(GR F )
.
4.4 The definition
Definition 16. The anchored relation (which I call ordinated product)
Q
(ord)
F is defined by the
formulas:
arity
Y
(ord)
F =
X
(arity F );
GR
Y
(ord)
F =
concat z | z
Y
(GR F )
.
Theorem 17.
Q
(ord)
F is a properly defined anchored relation.
Proof. dom concat z =
P
idom F
dom z
i
=
P
idom F
arity F
i
=
P
(arity F ).
4.5 Definition with composition for every multiplier
q(F )
i
=
def
(curry(
L
(arity F )))i.
Theorem 18. GR
Q
(ord)
F =
L
P
(arityF )
| i dom F : L q(F )
i
GR F
i
.
Proof. GR
Q
(ord)
F ={concat z | z
Q
(GR F )};
GR
Q
(ord)
F =
uncurry(z) (
L
(arity F ))
1
| z
Q
idom F
arity F
i
, i dom F : z(i)
GR F
i
;
Let L = uncurry(z). Then z = curry(L).
GR
Q
(ord)
F =
L (
L
(arity F ))
1
| curry(L)
Q
idom F
arity F
i
, i dom F : curry(L)i
GR F
i
;
GR
Q
(ord)
F =
n
L (
L
(arity F ))
1
| L
`
i dom F
arity F
i
, i dom F : curry(L)i GR F
i
o
;
GR
Q
(ord)
F =
L
P
(arityF )
| i dom F : curry(L
L
(arity F ))i GR F
i
;
(curry(L
L
(arity F ))i )x = L((curry(
L
(arity F ))i )x) = L(q(F )
i
x) = (L q(F )
i
)x;
curry(L
L
(arity F ))i = L q(F )
i
;
GR
Q
(ord)
F =
L
P
(arityF )
| i dom F : L q(F )
i
GR F
i
.
Corollary 19. GR
Q
(ord)
F =
L (
S
im(GR F ))
P
(arityF )
| i dom F : L q(F )
i
GR F
i
.
Corollary 20. GR
Q
(ord)
F is small if F is small.
4 Section 4
4.6 Definition with shifting argument s
Let F
i
= {L Pr
1
|
{i}×arity F
i
| L GR F
i
}.
Proposition 21. F
i
= {L Pr
1
|
{i}×
| L GR F
i
}.
Proof. If L GR F
i
then dom L = arity F
i
. Thus
L Pr
1
|
{i}×arity F
i
=L Pr
1
|
{i}×dom L
=L Pr
1
|
{i}×
.
Proposition 22. F
i
is an ({i} × arity F
i
)-ary relation.
Proof. We need to prove that dom(L Pr
1
|
{i}×arity F
i
) = {i} × arity F
i
for L GR F
i
, but that’ s
obvious.
Obvious 23.
`
(arity F ) =
S
idom F
({i} × arity F
i
) =
S
idom F
dom F
i
.
Lemma 24. P
Q
idom F
F
i
curry(
S
im P )
Q
(GR F ) for a dom F indexed family P where
P
i
{i}×arity F
i
for every i dom F , that is for P
`
idom F
{i}×arity F
i
.
Proof. For every P
`
idom F
{i}×arity F
i
we have:
P
Q
idom F
F
i
P {z
dom F
| i dom F : z(i) F
i
} P
dom F
i dom F :
P (i) F
i
P
dom F
i dom F L GR F
i
: P
i
= L (Pr
1
|
{i}×
) P
dom F
i dom F L GR F
i
:
P
i
{i}×arity F
i
x arity F
i
: P
i
(i; x) = Lx
P
dom F
i dom F L GR F
i
:
P
i
{i}×arity F
i
curry(P
i
)i = L
P
dom F
i dom F :
P
i
{i}×arity F
i
curry(P
i
) GR F
i
i dom F Q
i
(
arity F
i
)
{i}
: (P
i
= uncurry(Q
i
)
(Q
i
)i
arity F
i
Q
i
i GR F
i
) i dom F Q
i
(
arity F
i
)
{i}
P
i
= uncurry(Q
i
)
S
idom F
Q
i
i
GR F
i
i dom F Q
i
(
arity F
i
)
{i}
P
i
= uncurry(Q
i
)
S
idom F
Q
i
Q
(GR F )
i dom F :
S
idom F
curry(P
i
)
Q
(GR F ) curry
S
idom F
P
i
Q
(GR F )
curry(
S
im P )
Q
(GR F ).
Lemma 25.
n
curry(f)
L
(arity F ) | f GR
Q
(ord)
F
o
=
Q
(GR F ).
Proof. First GR
Q
(ord)
F = {uncurry(z) (
L
(dom z))
1
| z
Q
(GR F )}, tha t is
n
f | f GR
Q
(ord)
F
o
= {uncurry(z) (
L
(arity F ))
1
| z
Q
(GR F )}.
Since
L
(arity F ) is a bijection, we have
n
f
L
(arity F ) | f GR
Q
(ord)
F
o
= {uncurry(z) | z
Q
(GR F )} what is equivalent to
n
curry(f )
L
(arity F ) | f GR
Q
(ord)
F
o
= {z | z
Q
(GR F )} that is
n
curry(f )
L
(arity F ) | f GR
Q
(ord)
F
o
=
Q
(GR F ).
Lemma 26.
S
im P | P
`
idom F
{i}×arity F
i
curry(
S
im P )
Q
(GR F )
=
n
L | L
`
i X
arity F
i
curry(L)
Q
(GR F )
o
.
Proof. Let L
n
L | L
`
i X
arity F
i
curry(L)
Q
(GR F )
o
. Then L
`
i X
arity F
i
and
curry(L
)
Q
(GR F ).
Let P = λi dom F : L
|
{i}×arity F
i
. Then P
`
idom F
{i}×arity F
i
and
S
im P = L
. So
L
S
im P | P
`
idom F
{i}×arity F
i
curry(
S
im P )
Q
(GR F )
.
Let now L
S
im P | P
`
idom F
{i}×arity F
i
curry(
S
im P )
Q
(GR F )
. Then there
exists P
`
idom F
{i}×arity F
i
such that L
=
S
im P and curry(L
)
Q
(GR F ). Evidently
L
`
i X
arity F
i
. So L
S
im P | P
`
idom F
{i}×arity F
i
curry(
S
im P )
Q
(GR F )
.
Ordinated product 5
Lemma 27.
n
f
L
(arity F ) | f GR
Q
(ord)
F
o
=
S
im P | P
Q
idom F
F
i
.
Proof. L
S
im P | P
Q
idom F
F
i
L
S
im P | P
`
idom F
{i}×arity F
i
curry(
S
im P )
Q
(GR F )
L
`
iX
arity F
i
curry(L)
Q
(GR F ) L
`
iX
arity F
i
curry(L)
n
curry(f)
L
(arity F ) | f GR
Q
(ord)
F
o
(because
L
(arity F ) is a
bijection)curry(L) (
L
(arity F ))
1
n
curry(f ) | f GR
Q
(ord)
F
o
L (
L
(arity F ))
1
n
f | f GR
Q
(ord)
F
o
(because
L
(arity F ) is a bijection)L
n
f
L
(arity F ) | f
GR
Q
(ord)
F
o
.
Theorem 28.
GR
Y
(ord)
F =
(
[
im P
M
(arity F )
1
| P
Y
idom F
F
i
)
.
Proof. From the lemma, because
L
(arity F ) is a bijection.
Theorem 29.
GR
Y
(ord)
F =
(
[
idom F
P
i
M
(arity F )
1
| P
Y
idom F
F
i
)
.
Proof. From the previous theorem.
Theorem 30.
GR
Y
(ord)
F =
(
[
im P | P
Y
idom F
f
M
(arity F )
1
| f F
i
)
.
Proof. From the previous.
Remark 31. No te that the above formulas contain both
S
idom F
dom F
i
and
S
idom F
F
i
. These
forms are similar but different.
4.7 Associativity of ordinated product
Let f is an ordinal variadic functio n.
Let S is an ordinal indexed family of functio ns of ordinal index ed families of functions each
taking an ordinal number of arguments in a set X.
I ca ll f infinite associative when
1. f (f S) = f (concat S) for every S;
2. f (JxK) = x for x X.
4.7.1 Infinite associativity impliess associativity
Proposition 32. Let f is an infinitely associative function taking an ordina l number of arguments
in a set X. Define x y = f Jx; yK for x, y X. Then the binary operation is ass ociative.
Proof. Let x, y, z X. Then (x y) z = f JfJx; yK; zK = f(fJx; yK; f JzK) = fJx; y; zK. Similarly
x (y z) = f Jx; y; zK. So (x y) z = x (y z).
4.7.2 Concatenation is associative
First we will prove some lemmas.
6 Section 4
Let a and b are functions on a poset. Let a b iff there exist an order isomorphism f such that
a = b f . Evidently is an equivalence r elation.
Obvious 33. concat a = concat b uncurry(a) uncurry(b) for every ordinal indexed families a
and b of functions taking an ordinal number of arguments.
Thank to the above, we can reduce properties of concat to properties of uncurry.
Lemma 34. a b uncurry a uncurry b for every ordinal indexed families a and b of functions
taking an ordinal number of arguments.
Proof. There exist an order isomorphism f such that a = b f.
uncurry(a)(x; y) = (ax)y = (bfx)y = uncurry(b)(fx; y) = uncurry(b)g(x; y) where g(x; y) = (fx;
y).
g is an order isomorphism because g(x
0
; y
0
) > g(x
1
; y
1
) (x
0
; y
0
) > (x
1
; y
1
). (In jectivity and
surjectivity are obvious.)
Lemma 35. Let a
i
b
i
where f
i
for every i. Then uncurry a uncurry b for every ordinal indexed
families a and b of ordinal indexed families of fu nc tio ns taking an ordinal number of arguments.
Proof. L e t a
i
= b
i
f
i
where f
i
is an order isomorphism for every i.
uncurry(a)(i; y) = a
i
y = b
i
f
i
y = uncurry(b)(i; f
i
y) = uncurry(b)g(i; y) = (uncurry(b) g)(i; y)
where g(i; y) = (i; f
i
y).
g is an order isomorphism because g(i; y
0
) > g(i; y
1
) f
i
y
0
> f
i
y
1
y
0
> y
1
and i
0
> i
1
g(i
0
;
y
0
) > g(i
1
; y
1
). (Injectivity and surjectivity are obvious.)
Let now S is an ordinal indexed family of ordinal indexed families of functions taking an ordinal
number of arguments.
Lemma 36. uncurry(uncurry S) uncurry(uncurry S).
Proof. uncurry S = λi S: uncurry(S
i
);
uncurry(uncurry S)(i; (x; y)) = (uncurry S
i
)(x; y) = (S
i
x)y;
(uncurry(uncurry S))((i; x); y) = ((uncurry S)(i; x))y = (S
i
x)y.
Thus uncurry(uncurry S)(i; (x; y)) = (uncurry(uncurry S))((i; x); y) and thus evidently
uncurry(uncurry S) uncurry(uncurry S).
Theorem 37. concat is an infinitely associative function.
Proof. conc at(JxK) = x for a function x taking an ordinal number of argument is obvious. It is
remained to prove
concat(concat S) = concat(concat S);
We have, using the lemmas, concat(concat S) uncurry(concat S) (by lemma 35)
uncurry(uncurry S) uncurry(uncurry S) uncurry(concat S) concat(concat S).
Corollary 38. O rdinated product is an infinitely a ssociative function.
Bib liography
[1] K. Ciesielski. Set Theory for the Working Mathematician. Cambridge, England: Cambridge University Press,
1997.
[2] J. E. Rubin. Set Theory for the Mathematician. New York: Holden-Day, 1967.
[3] P. Suppes. Axiomatic Set Theory. New York: Dover, 1972.
Bibliography 7