Текстовые фрагменты публикации
В.Л. ПОРТОН
ALGEBRAIC GENERAL
TOPOLOGY
Монография
Москва
ИНФРА-М
2019
УДК
512(075.4)
ББК
22.152
П60
Портон В.Л.
П60
Algebraic General Topology : монография / В.Л. Портон. —
Москва : ИНФРА-М, 2019. — 395 с.
ISBN 978-5-16-108176-1 (online)
ABSTRACT. In this work I introduce and study in details the concepts
of funcoids which generalize proximity spaces and reloids which generalize
uniform spaces, and generalizations thereof. The concept of funcoid is
generalized concept of proximity, the concept of reloid is cleared from
superfluous details (generalized) concept of uniformity.
Also funcoids and reloids are generalizations of binary relations
whose domains and ranges are filters (instead of sets). Also funcoids and
reloids can be considered as a generalization of (oriented) graphs, this
provides us with a common generalization of calculus and discrete
mathematics.
It is defined a generalization of limit for arbitrary (including
discontinuous and multivalued) functions, what allows to define for
example derivative of an arbitrary real function.
The concept of continuity is defined by an algebraic formula (instead
of old messy epsilon-delta notation) for arbitrary morphisms (including
funcoids and reloids) of a partially ordered category. In one formula
continuity, proximity continuity, and uniform continuity are generalized.
Also I define connectedness for funcoids and reloids.
Then I consider generalizations of funcoids: pointfree funcoids and
generalization of pointfree funcoids: staroids and multifuncoids. Also I
define several kinds of products of funcoids and other morphisms.
Before going to topology, this book studies properties of co-
brouwerian lattices and filters.
УДК
512(075.4)
ББК
22.152
ISBN 978-5-16-108176-1 (online)
© Портон В.Л., 2019
ФЗ
№ 436-ФЗ
Издание не подлежит маркировке
в соответствии с п. 1 ч. 2 ст. 1
Contents
Part 1.
Introductory chapters
8
Chapter 1.
Introduction
9
1.1.
License and editing
9
1.2.
Intended audience
9
1.3.
Reading Order
9
1.4.
Our topic and rationale
10
1.5.
Earlier works
10
1.6.
Kinds of continuity
11
1.7.
Responses to some accusations against style of my exposition
11
1.8.
Structure of this book
12
1.9.
Basic notation
12
1.10.
Implicit arguments
13
1.11.
Unusual notation
13
Chapter 2.
Common knowledge, part 1
15
2.1.
Order theory
15
2.2.
Intro to category theory
31
2.3.
Intro to group theory
35
Chapter 3.
More on order theory
36
3.1.
Straight maps and separation subsets
36
3.2.
Quasidifference and Quasicomplement
39
3.3.
Several equal ways to express pseudodifference
42
3.4.
Partially ordered categories
43
3.5.
Partitioning
46
3.6.
A proposition about binary relations
47
3.7.
Infinite associativity and ordinated product
47
3.8.
Galois surjections
55
3.9.
Some properties of frames
55
Chapter 4.
Typed sets and category Rel
61
4.1.
Relational structures
61
4.2.
Typed elements and typed sets
61
4.3.
Category Rel
62
4.4.
Product of typed sets
66
Chapter 5.
Filters and filtrators
68
5.1.
Implication tuples
68
5.2.
Introduction to filters and filtrators
68
5.3.
Filters on a poset
69
5.4.
Filters on a Set
71
5.5.
Filtrators
72
5.6.
Alternative primary filtrators
74
5.7.
Basic properties of filters
80
3
CONTENTS
4
5.8.
More advanced properties of filters
81
5.9.
Misc filtrator properties
86
5.10.
Characterization of Binarily Meet-Closed Filtrators
86
5.11.
Core Part
87
5.12.
Intersection and Joining with an Element of the Core
88
5.13.
Stars of Elements of Filtrators
89
5.14.
Atomic Elements of a Filtrator
90
5.15.
Prime Filtrator Elements
92
5.16.
Stars for filters
93
5.17.
Generalized Filter Base
94
5.18.
Separability of filters
95
5.19.
Some Criteria
96
5.20.
Co-Separability of Core
98
5.21.
Complements and Core Parts
99
5.22.
Core Part and Atomic Elements
101
5.23.
Distributivity of Core Part over Lattice Operations
102
5.24.
Separability criteria
103
5.25.
Filtrators over Boolean Lattices
104
5.26.
Distributivity for an Element of Boolean Core
105
5.27.
More about the Lattice of Filters
106
5.28.
More Criteria
106
5.29.
Filters and a Special Sublattice
107
5.30.
Distributivity of quasicomplements
108
5.31.
Complementive Filters and Factoring by a Filter
110
5.32.
Pseudodifference of filters
112
5.33.
Function spaces of posets
113
5.34.
Filters on a Set
118
5.35.
Bases on filtrators
121
5.36.
Some Counter-Examples
122
5.37.
Open problems about filters
126
5.38.
Further notation
126
5.39.
Equivalent filters and rebase of filters
126
Chapter 6.
Common knowledge, part 2 (topology)
135
6.1.
Metric spaces
135
6.2.
Pretopological spaces
136
6.3.
Topological spaces
138
6.4.
Proximity spaces
141
6.5.
Definition of uniform spaces
142
Part 2.
Funcoids and reloids
143
Chapter 7.
Funcoids
144
7.1.
Informal introduction into funcoids
144
7.2.
Basic definitions
145
7.3.
Funcoid as continuation
147
7.4.
Another way to represent funcoids as binary relations
152
7.5.
Lattices of funcoids
153
7.6.
More on composition of funcoids
155
7.7.
Domain and range of a funcoid
157
7.8.
Categories of funcoids
159
7.9.
Specifying funcoids by functions or relations on atomic filters
160
7.10.
Funcoidal product of filters
164
CONTENTS
5
7.11.
Atomic funcoids
167
7.12.
Complete funcoids
169
7.13.
Funcoids corresponding to pretopologies
174
7.14.
Completion of funcoids
174
7.15.
Monovalued and injective funcoids
177
7.16.
Open maps
179
7.17.
T0-, T1-, T2-, T3-, and T4-separable funcoids
180
7.18.
Filters closed regarding a funcoid
181
7.19.
Proximity spaces
182
Chapter 8.
Reloids
183
8.1.
Basic definitions
183
8.2.
Composition of reloids
184
8.3.
Reloidal product of filters
186
8.4.
Restricting reloid to a filter. Domain and image
188
8.5.
Categories of reloids
190
8.6.
Monovalued and injective reloids
191
8.7.
Complete reloids and completion of reloids
192
8.8.
What uniform spaces are
196
Chapter 9.
Relationships between funcoids and reloids
197
9.1.
Funcoid induced by a reloid
197
9.2.
Reloids induced by a funcoid
201
9.3.
Galois connections between funcoids and reloids
204
9.4.
Funcoidal reloids
207
9.5.
Complete funcoids and reloids
210
9.6.
Properties preserved by relationships
212
9.7.
Some sub-posets of funcoids and reloids
213
9.8.
Double filtrators
214
Chapter 10.
On distributivity of composition with a principal reloid
215
10.1.
Decomposition of composition of binary relations
215
10.2.
Decomposition of composition of reloids
215
10.3.
Lemmas for the main result
216
10.4.
Proof of the main result
217
10.5.
Embedding reloids into funcoids
217
Chapter 11.
Continuous morphisms
220
11.1.
Traditional definitions of continuity
220
11.2.
Our three definitions of continuity
221
11.3.
Continuity for topological spaces
222
11.4.
C(µ ◦ µ−1, ν ◦ ν−1)
223
11.5.
Continuity of a restricted morphism
223
Chapter 12.
Connectedness regarding funcoids and reloids
225
12.1.
Some lemmas
225
12.2.
Endomorphism series
225
12.3.
Connectedness regarding binary relations
226
12.4.
Connectedness regarding funcoids and reloids
227
12.5.
Algebraic properties of S and S∗
229
12.6.
Irreflexive reloids
230
12.7.
Micronization
231
Chapter 13.
Total boundness of reloids
232
CONTENTS
6
13.1.
Thick binary relations
232
13.2.
Totally bounded endoreloids
233
13.3.
Special case of uniform spaces
233
13.4.
Relationships with other properties
234
13.5.
Additional predicates
235
Chapter 14.
Orderings of filters in terms of reloids
236
14.1.
Ordering of filters
236
14.2.
Rudin-Keisler equivalence and Rudin-Keisler order
246
14.3.
Consequences
248
Chapter 15.
Counter-examples about funcoids and reloids
252
15.1.
Second product. Oblique product
256
Chapter 16.
Funcoids are filters
258
16.1.
Rearrangement of collections of sets
258
16.2.
Finite unions of Cartesian products
259
16.3.
Before the diagram
260
16.4.
Associativity over composition
262
16.5.
The diagram
264
16.6.
Some additional properties
265
16.7.
More on properties of funcoids
267
16.8.
Funcoid bases
268
16.9.
Some (example) values
270
Chapter 17.
Generalized cofinite filters
272
Chapter 18.
Convergence of funcoids
276
18.1.
Convergence
276
18.2.
Relationships between convergence and continuity
277
18.3.
Convergence of join
277
18.4.
Limit
278
18.5.
Generalized limit
278
18.6.
Expressing limits as implications
280
Part 3.
Pointfree funcoids and reloids
282
Chapter 19.
Pointfree funcoids
283
19.1.
Definition
283
19.2.
Composition of pointfree funcoids
285
19.3.
Pointfree funcoid as continuation
286
19.4.
The order of pointfree funcoids
289
19.5.
Domain and range of a pointfree funcoid
292
19.6.
Specifying funcoids by functions or relations on atomic filters
294
19.7.
More on composition of pointfree funcoids
296
19.8.
Funcoidal product of elements
298
19.9.
Category of pointfree funcoids
301
19.10.
Atomic pointfree funcoids
302
19.11.
Complete pointfree funcoids
303
19.12.
Completion and co-completion
306
19.13.
Monovalued and injective pointfree funcoids
306
19.14.
Elements closed regarding a pointfree funcoid
308
19.15.
Connectedness regarding a pointfree funcoid
308
19.16.
Boolean funcoids
309
CONTENTS
7
19.17.
Binary relations are pointfree funcoids
310
Chapter 20.
Alternative representations of binary relations
312
Part 4.
Staroids and multifuncoids
317
Chapter 21.
Multifuncoids and staroids
318
21.1.
Product of two funcoids
318
21.2.
Definition of staroids
319
21.3.
Upgrading and downgrading a set regarding a filtrator
322
21.4.
Principal staroids
323
21.5.
Multifuncoids
325
21.6.
Join of multifuncoids
327
21.7.
Infinite product of poset elements
329
21.8.
On products of staroids
332
21.9.
Star categories
335
21.10.
Product of an arbitrary number of funcoids
338
21.11.
Multireloids
347
21.12.
Subatomic product of funcoids
351
21.13.
On products and projections
354
21.14.
Relationships between cross-composition and subatomic products
357
21.15.
Cross-inner and cross-outer product
360
21.16.
Coordinate-wise continuity
361
21.17.
Upgrading and downgrading multifuncoids
362
21.18.
On pseudofuncoids
364
21.19.
Identity staroids and multifuncoids
369
21.20.
Counter-examples
376
21.21.
Conjectures
379
Part 5.
Postface
383
Chapter 22.
Postface
384
22.1.
Pointfree reloids
384
22.2.
Formalizing this theory
384
Chapter 23.
Story of the discovery
386
Appendix A.
Using logic of generalizations
388
A.1.
Logic of generalization
388
Appendix.
Bibliography
390
Part 1
Introductory chapters
CHAPTER 1
Introduction
The main purpose of this book is to record the current state of my research.
The book is however written in such a way that it can be used as a textbook for
studying my research.
For the latest version of this file, related materials, articles, research questions,
and erratum consult the Web page of the author of the book:
http://www.mathematics21.org/algebraic-general-topology.html
1.1. License and editing
This work is licensed under the Creative Commons Attribution 4.0 Interna-
tional License. To view a copy of the license, visit
http://creativecommons.org/licenses/by/4.0/.
You can create your own copy of LATEX source of the book and edit it (to
correct errors, add new results, generalize existing results, enhance readability).
The editable source of the book is presented at
https://bitbucket.org/portonv/algebraic-general-topology
Please consider reviewing this book at
http://www.euro-math-soc.eu/node/add/book-review
If you find any error (or some improvement idea), please report in our bug
tracker:
https://bitbucket.org/portonv/algebraic-general-topology/issues
1.2. Intended audience
This book is suitable for any math student as well as for researchers.
To make this book be understandable even for first grade students, I made
a chapter about basic concepts (posets, lattices, topological spaces, etc.), which
an already knowledgeable person may skip reading. It is assumed that the reader
knows basic set theory.
But it is also valuable for mature researchers, as it contains much original
research which you could not find in any other source except of my work.
Knowledge of the basic set theory is expected from the reader.
Despite that this book presents new research, it is well structured and is suitable
to be used as a textbook for a college course.
Your comments about this book are welcome to the email porton@narod.ru.
1.3. Reading Order
If you know basic order and lattice theory (including Galois connections and
brouwerian lattices) and basics of category theory, you may skip reading the chapter
“Common knowledge, part 1”.
You are recommended to read the rest of this book by the order.
9
1.5. EARLIER WORKS
10
1.4. Our topic and rationale
From [42]: Point-set topology, also called set-theoretic topology or general topol-
ogy, is the study of the general abstract nature of continuity or “closeness” on
spaces. Basic point-set topological notions are ones like continuity, dimension, com-
pactness, and connectedness.
In this work we study a new approach to point-set topology (and pointfree
topology).
Traditionally general topology is studied using topological spaces (defined below
in the section “Topological spaces”). I however argue that the theory of topolog-
ical spaces is not the best method of studying general topology and introduce an
alternative theory, the theory of funcoids. Despite of popularity of the theory of
topological spaces it has some drawbacks and is in my opinion not the most appro-
priate formalism to study most of general topology. Because topological spaces are
tailored for study of special sets, so called open and closed sets, studying general
topology with topological spaces is a little anti-natural and ugly. In my opinion the
theory of funcoids is more elegant than the theory of topological spaces, and it is
better to study funcoids than topological spaces. One of the main purposes of this
work is to present an alternative General Topology based on funcoids instead of
being based on topological spaces as it is customary. In order to study funcoids the
prior knowledge of topological spaces is not necessary. Nevertheless in this work
I will consider topological spaces and the topic of interrelation of funcoids with
topological spaces.
In fact funcoids are a generalization of topological spaces, so the well known
theory of topological spaces is a special case of the below presented theory of fun-
coids.
But probably the most important reason to study funcoids is that funcoids
are a generalization of proximity spaces (see section “Proximity spaces” for the
definition of proximity spaces). Before this work it was written that the theory of
proximity spaces was an example of a stalled research, almost nothing interesting
was discovered about this theory. It was so because the proper way to research
proximity spaces is to research their generalization, funcoids. And so it was stalled
until discovery of funcoids. That generalized theory of proximity spaces will bring
us yet many interesting results.
In addition to funcoids I research reloids. Using below defined terminology it
may be said that reloids are (basically) filters on Cartesian product of sets, and
this is a special case of uniform spaces.
Afterward we study some generalizations.
Somebody might ask, why to study it?
My approach relates to traditional
general topology like complex numbers to real numbers theory. Be sure this will
find applications.
This book has a deficiency: It does not properly relate my theory with previous
research in general topology and does not consider deeper category theory prop-
erties. It is however OK for now, as I am going to do this study in later volumes
(continuation of this book).
Many proofs in this book may seem too easy and thus this theory not sophis-
ticated enough. But it is largely a result of a well structured digraph of proofs,
where more difficult results are made easy by reducing them to easier lemmas and
propositions.
1.5. Earlier works
Some mathematicians were researching generalizations of proximities and uni-
formities before me but they have failed to reach the right degree of generalization
1.7. RESPONSES TO SOME ACCUSATIONS AGAINST STYLE OF MY EXPOSITION
11
which is presented in this work allowing to represent properties of spaces with
algebraic (or categorical) formulas.
Proximity structures were introduced by Smirnov in [11].
Some references to predecessors:
• In [15, 16, 25, 2, 36] generalized uniformities and proximities are studied.
• Proximities and uniformities are also studied in [22, 23, 35, 37, 38].
• [20, 21] contains recent progress in quasi-uniform spaces. [21] has a very
long list of related literature.
Some works ([34]) about proximity spaces consider relationships of proximities and
compact topological spaces. In this work the attempt to define or research their
generalization, compactness of funcoids or reloids is not done. It seems potentially
productive to attempt to borrow the definitions and procedures from the above
mentioned works. I hope to do this study in a separate volume.
[10] studies mappings between proximity structures. (In this volume no at-
tempt to research mappings between funcoids is done.) [26] researches relationships
of quasi-uniform spaces and topological spaces. [1] studies how proximity structures
can be treated as uniform structures and compactification regarding proximity and
uniform spaces.
This book is based partially on my articles [30, 28, 29].
1.6. Kinds of continuity
A research result based on this book but not fully included in this book (and
not yet published) is that the following kinds of continuity are described by the
same algebraic (or rather categorical) formulas for different kinds of continuity and
have common properties:
• discrete continuity (between digraphs);
• (pre)topological continuity;
• proximal continuity;
• uniform continuity;
• Cauchy continuity;
• (probably other kinds of continuity).
Thus my research justifies using the same word “continuity” for these diverse kinds
of continuity.
See http://www.mathematics21.org/algebraic-general-topology.html
1.7. Responses to some accusations against style of my exposition
The proofs are generally hard to follow and unpleasant to read
as they are just a bunch of equations thrown at you, without
motivation or underlying reasoning, etc.
I don’t think this is essential. The proofs are not the most important thing in
my book. The most essential thing are definitions. The proofs are just to fill the
gaps. So I deem it not important whether proofs are motivated.
Also, note “algebraic” in the title of my book. The proofs are meant to be just
sequences of formulas for as much as possible :-) It is to be thought algebraically.
The meaning are the formulas themselves.
Maybe it makes sense to read my book skipping all the proofs? Some proofs
contain important ideas, but most don’t. The important thing are definitions.
1.9. BASIC NOTATION
12
1.8. Structure of this book
In the chapter “Common knowledge, part 1” some well known definitions and
theories are considered. You may skip its reading if you already know it. That
chapter contains info about:
• posets;
• lattices and complete lattices;
• Galois connections;
• co-brouwerian lattices;
• a very short intro into category theory;
• a very short introduction to group theory.
Afterward there are my little additions to poset/lattice and category theory.
Afterward there is the theory of filters and filtrators.
Then there is “Common knowledge, part 2 (topology)”, which considers briefly:
• metric spaces;
• topological spaces;
• pretopological spaces;
• proximity spaces.
Despite of the name “Common knowledge” this second common knowledge chapter
is recommended to be read completely even if you know topology well, because it
contains some rare theorems not known to most mathematicians and hard to find
in literature.
Then the most interesting thing in this book, the theory of funcoids, starts.
Afterwards there is the theory of reloids.
Then I show relationships between funcoids and reloids.
The last I research generalizations of funcoids, pointfree funcoids, staroids, and
multifuncoids and some different kinds of products of morphisms.
1.9. Basic notation
I will denote a set definition like
x∈A
P (x)
instead of customary {x ∈ A | P(x)}.
I do this because otherwise formulas don’t fit horizontally into the available space.
1.9.1. Grothendieck universes. We will work in ZFC with an infinite and
uncountable Grothendieck universe.
A Grothendieck universe is just a set big enough to make all usual set theory
inside it. For example if ℧ is a Grothendieck universe, and sets X, Y ∈ ℧, then also
X ∪ Y ∈ ℧, X ∩ Y ∈ ℧, X × Y ∈ ℧, etc.
A set which is a member of a Grothendieck universe is called a small set (re-
garding this Grothendieck universe). We can restrict our consideration to small
sets in order to get rid troubles with proper classes.
Definition 1. Grothendieck universe is a set ℧ such that:
1◦. If x ∈ ℧ and y ∈ x then y ∈ ℧.
2◦. If x, y ∈ ℧ then {x, y} ∈ ℧.
3◦. If x ∈ ℧ then Px ∈ ℧.
4◦. If
xi
i∈I∈℧
is a family of elements of ℧, then
i∈I xi ∈ ℧.
One can deduce from this also:
1◦. If x ∈ ℧, then {x} ∈ ℧.
2◦. If x is a subset of y ∈ ℧, then x ∈ ℧.
3◦. If x, y ∈ ℧ then the ordered pair (x, y) = {{x, y}, x} ∈ ℧.
4◦. If x, y ∈ ℧ then x ∪ y and x × y are in ℧.
5◦. If
xi
i∈I∈℧
is a family of elements of ℧, then the product
i∈I xi ∈ ℧.
1.11. UNUSUAL NOTATION
13
6◦. If x ∈ ℧, then the cardinality of x is strictly less than the cardinality of ℧.
1.9.2. Misc. In this book quantifiers bind tightly. That is ∀x ∈ A : P(x) ∧ Q
and ∀x ∈ A : P(x) ⇒ Q should be read (∀x ∈ A : P(x))∧Q and (∀x ∈ A : P(x)) ⇒
Q not ∀x ∈ A : (P(x) ∧ Q) and ∀x ∈ A : (P(x) ⇒ Q).
The set of functions from a set A to a set B is denoted as BA.
I will often skip parentheses and write fx instead of f(x) to denote the result
of a function f acting on the argument x.
I will denote ⟨f⟩∗X =
β∈im f
∃α∈X:αfβ
(in other words ⟨f⟩∗X is the image of a
set X under a function or binary relation f) and X [f]∗ Y ⇔ ∃x ∈ X, y ∈ Y : x f y
for sets X, Y and a binary relation f. (Note that functions are a special case of
binary relations.)
By just ⟨f⟩∗ and [f]∗ I will denote the corresponding function and relation on
small sets.
Obvious 2. For a function f we have ⟨f⟩∗X =
f(x)
x∈X
.
Definition 3.
f −1∗X is called the preimage of a set X by a function (or,
more generally, a binary relation) f.
Obvious 4. {α} [f]∗ {β} ⇔ α f β for every α and β.
λx ∈ D : f(x) =
(x,f(x))
x∈D
for a set D and and a form f depending on the
variable x. In other words, λx ∈ D : f(x) is the function which maps elements x of
a set D into f(x).
I will denote source and destination of a morphism f of any category (See
chapter 2 for a definition of a category.) as Src f and Dst f correspondingly. Note
that below defined domain and image of a funcoid are not the same as its source
and destination.
I will denote GR(A, B, f) = f for any morphism (A, B, f) of either Set or Rel.
(See definitions of Set and Rel below.)
1.10. Implicit arguments
Some notation such that ⊥A, ⊤A, ⊔A, ⊓A have indexes (in these examples A).
We will omit these indexes when they can be restored from the context. For
example, having a function f : A → B where A, B are posets with least elements,
we will concisely denote f⊥ = ⊥ for f⊥A = ⊥B. (See below for definitions of these
operations.)
Note 5. In the above formula f⊥ = ⊥ we have the first ⊥ and the second ⊥
denoting different objects.
We will assume (skipping this in actual proofs) that all omitted indexes can be
restored from context. (Note that so called dependent type theory computer proof
assistants do this like we implicitly.)
1.11. Unusual notation
In the chapter “Common knowledge, part 1” (which you may skip reading if
you are already knowledgeable) some non-standard notation is defined. I summarize
here this notation for the case if you choose to skip reading that chapter:
Partial order is denoted as ⊑.
Meets and joins are denoted as ⊓, ⊔, ,
.
I call element b substractive from an element a (of a distributive lattice A) when
the difference a \ b exists. I call b complementive to a when there exists c ∈ A such
1.11. UNUSUAL NOTATION
14
that b ⊓ c = ⊥ and b ⊔ c = a. We will prove that b is complementive to a iff b is
substractive from a and b ⊑ a.
Definition 6. Call a and b of a poset A intersecting, denoted a ̸≍ b, when
there exists a non-least element c such that c ⊑ a ∧ c ⊑ b.
Definition 7. a ≍ b
def
= ¬(a ̸≍ b).
Definition 8. I call elements a and b of a poset A joining and denote a ≡ b
when there are no non-greatest element c such that c ⊒ a ∧ c ⊒ b.
Definition 9. a ̸≡ b
def
= ¬(a ≡ b).
Obvious 10. a ̸≍ b iff a ⊓ b is non-least, for every elements a, b of a meet-
semilattice.
Obvious 11. a ≡ b iff a ⊔ b is the greatest element, for every elements a, b of
a join-semilattice.
I extend the definitions of pseudocomplement and dual pseudocomplement to
arbitrary posets (not just lattices as it is customary):
Definition 12. Let A be a poset. Pseudocomplement of a is
max
c ∈ A
c ≍ a
.
If z is the pseudocomplement of a we will denote z = a∗.
Definition 13. Let A be a poset. Dual pseudocomplement of a is
min
c ∈ A
c ≡ a
.
If z is the dual pseudocomplement of a we will denote z = a+.
CHAPTER 2
Common knowledge, part 1
In this chapter we will consider some well known mathematical theories. If you
already know them you may skip reading this chapter (or its parts).
2.1. Order theory
2.1.1. Posets.
Definition 14. The identity relation on a set A is idA =
(a,a)
a∈A
.
Definition 15. A preorder on a set A is a binary relation ⊑ on A which is:
• reflexive on A that is (⊑) ⊇ idA or what is the same ∀x ∈ A : x ⊑ x;
• transitive that is (⊑) ◦ (⊑) ⊆ (⊑) or what is the same
∀x, y, z : (x ⊑ y ∧ y ⊑ z ⇒ x ⊑ z).
Definition 16. A partial order on a set A is a preorder on A which is anti-
symmetric that is (⊑) ∩ (⊑) ⊆ idA or what is the same
∀x, y ∈ A : (x ⊑ y ∧ y ⊑ x ⇒ x = y).
The reverse relation is denoted ⊒.
Definition 17. a is a subelement of b (or what is the same a is contained in
b or b contains a) iff a ⊑ b.
Obvious 18. The reverse of a partial order is also a partial order.
Definition 19. A set A together with a partial order on it is called a partially
ordered set (poset for short).
An example of a poset is the set R of real numbers with ⊑ = ≤.
Another example is the set PA of all subsets of an arbitrary fixed set A with
⊑ = ⊆. Note that this poset is (in general) not linear (see definition of linear poset
below.)
Definition 20. Strict partial order ⊏ corresponding to the partial order ⊑ on
a set A is defined by the formula (⊏) = (⊑) \ idA. In other words,
a ⊏ b ⇔ a ⊑ b ∧ a ̸= b.
An example of strict partial order is < on the set R of real numbers.
Definition 21. A partial order on a set A restricted to a set B ⊆ A is (⊑) ∩
(B × B).
Obvious 22. A partial order on a set A restricted to a set B ⊆ A is a partial
order on B.
Definition 23.
• The least element ⊥ of a poset A is defined by the formula ∀a ∈ A : ⊥ ⊑ a.
• The greatest element ⊤ of a poset A is defined by the formula ∀a ∈ A :
⊤ ⊒ a.
15
Фрагмент текстового слоя документа размещен для индексирующих роботов.
Для полноценной работы с документом, пожалуйста, перейдите в
ридер.