关系论在数学和许多学科领域(决策,知识和数据库,数学语言学,过程建模等)中起着非常显着的作用,但距离完善还很远。如同在数学知识的其他分支中一样,她的著名结果在更大程度上与某些对象存在的问题有关,而不是与列举它们有关。看起来,该理论特定领域的任何研究人员都应该对所关注对象及其依存关系的总体和完整图片感兴趣,以观察整个全景图。但可惜的是,这样做非常麻烦,因为没有人创建或提供过这样的全景图(图片)。甚至工作中提出的关系目录也无法解决问题。
一个简单的例子。许多年前,我在书中[1 p。207]遇到了这样一个段落。
部分有序集的理论仍然包含许多未解决的问题。如果n≥6,那么即使可以从给定的n个元素中构建出这样的集合的数量的问题,甚至都不存在。直接计算仅成功地确定了:如果S(n)是部分有序集的数量,则S(2)= 3,S(3)= 19,S(4)= 219,S(5)= 4231,以及数字S (n)对于非同构集,仅针对n = 4和n = 5个元素:Sn(4)= 16和Sn(5)= 63。
关于这一点,写了莫斯科国立大学Rybnikov K.A.系主任。我想更深入地了解这一点,似乎可以尝试寻找解决方案,至少以某种方式扩展列表,最重要的是-列出部分订单,查看其在现实中的分布及其属性。只是为了将结果挂在墙上。我承认,花费了大量的精力来开发研究程序,创建可行的部分订单模型,编写程序并对其进行调试,计算机将编程的算法旋转了数十个小时。 (从伟人那里)有人想到,数学的基础不应该是数字,而是一个顺序,那么据说许多定理将得到更简单,更透明的证明。
我们已经学会了计算大集合-载体上的关系数并枚举关系,但是即使对于数S(n),我们也无法获得严格的公式。我记得这次是我和我的同事密集的创造力成长的时期,在几乎所有计算机结果及其分析输出之后,都出现了修改,改进模型,算法,更正的想法,以检验新的假设,但是没有重要的事情(
我在下面的文字中尝试打开(获取)的内容。顺便说一句,其他外国研究人员的结果与我们的结果相吻合,但是他们只报告了S(n)的数量,没有提及偏序的枚举。
我们从小开始。任何n载波集的二进制关系的完整列表是已知的,可以轻松获得。他们正在寻找问题的答案:对于给定的n,有多少个关系与一个固定的属性,一对属性,三重关系等。事实是,有了这些数据,就可以建立不是枚举,而是直接算法来枚举此类关系,通过遵循Occam的剃刀规则,它们不会产生额外的精华。
在这里,我们将讨论获得二进制关系(BR)的这种结果。
因此,存在BO的n个集载波和所有BO的完整列表以及BO属性的列表:
-自反性;抗反射性部分自反
-对称性;反对称不对称不对称
-可传递性;反及物性
-秩序薄弱;严格的秩序;偏序 完美(线性);
-宽容;
-等价;
-周期性;
-完整性。
二元关系类型的定量特征
关系不仅可以具有一个特定的属性,还可以具有成对的,三联的等一组属性。在实践中使用这种关系是常见的情况。因此,例如,每种容忍态度(区别)都具有两个属性:对称性和自反性。这组属性确定公差关系的类型。
如果我们从公差关系中要求扩展属性列表的可行性(对称性,自反性和可传递性),则另一种类型的关系由公差关系引起。显然,也许并非所有的公差关系都将是可传递的,但是那些具有一组三个命名属性的公差关系将形成一种称为等价关系的新型关系。
等效关系集嵌套在公差关系集中。例如,在目录中,这些类型的关系通过填充来突出显示(8个公差,而其中只有5个等效)。出现了具有一组属性或其中一组属性的BO的数量的问题。
反身性
集合A = {上的关系α= <,A> }是自反的(具有自反性),如果每对()满足此关系。这里M是关系的图(不是图)...
换句话说,图矩阵的主要对角线即比率用1填充。自反关系图上的所有顶点都有环。如果没有的话,这种态度是防反射的 不执行 ... 在这种情况下,在主对角线上的反反射关系α的矩阵不具有单个单位,即。有零,并且相应的图在任何顶点都没有循环。
最后,如果对于某些情况,关系α是非反射的被执行,但对其他人则不是。我们将认为这种关系是部分自反的。主对角线上的非反射关系矩阵部分包含1,部分包含零。这种非反射关系的图在所有顶点上都没有回路。
自反关系的经典示例是矩阵表示形式的主要对角线,即单位(E =Δ)比,即平等关系(目录编号68)。该比率的图形由位于矩阵主对角线上的点(对)和相应的对形成,该图不包含任何其他点。
该比率的矩阵表示对应于单位矩阵(E)。对角线关系图由对应于集合A中元素的顶点形成,这些元素被分配了循环。对角线关系通常用符号表示...
在自反关系的情况下,相应的图也是自反的;在反自反关系的情况下,其图是反自反的。如果对于某种关系α已知它是自反的,则补语always始终是反自反的,并且...
对于抗反射关系β,这是正确的
例子1。在集合N上的关系≤(没有)是自反的,而在同一集合上的关系<(较少)是反自反的。
因为没有人是自己的儿子,所以“做儿子”的态度是反省的。
出于实际目的,有时有必要用基数| A |计算在集合A上给出的完整关系集中可用的自反关系的数量。 = n。
让我们展示如何执行这样的计算。我们将考虑平面上二元自反关系α的矩阵。它始终包含所有对角点。
对应于成对(i,j)的剩余点(n×n-n = n(n – 1)个对)可以包含在不同的组成和数目k中,k = 0(1)(n×n-n)进入可能的关系,这当然是反思的。通过求和ķ的组合n个(n-1)超过ķ,确定自反关系的总数
,其中K = N(N-1)/ 2是弧(边缘)中的数目正没有循环顶点曲线图。
非反射性关系的数量定义为A上的关系总数与反射性关系的数量之差。
从该表达式可以得出,非反射关系集包含
来自非反身关系的集合中的反身关系的数量恰好等于反身关系的数量,即
对称
根据对称性,整个关系集不分为四类:对称,不对称。后者又分为三类:反对称,不对称以及其余的不对称。
如果对于某对,集合A上的关系α= <Å,A>是对称的(相对于与图M的主对角线重合的直线具有对称性)
在对称关系图上,如果一对顶点i和j通过弧线(i,j)连接,则必然要通过弧线(j,i)连接。对称关系图是对称的或简单无向的普通图。
的比率α是反对称的,如果从
反对称比率矩阵不一定在主对角线中包含所有1,而在相对于主对角线对称的两个位置之一中包含对角线:在对角线上方或对角线下方。此关系的图由所有或其中一些具有顶点的顶点形成,如果图中的一对顶点(i,j)已连接,则它始终仅是一个方向的弧。请注意,对于对称和反对称关系,可以在其中包含或不包含一些对角点。
如果反对称关系不包含单个对角点,则他们说这样的关系是非对称的,即它始终是防反射的。
例子2... 集合N上的关系(≤)是反对称的,同一集合上的关系(<)是不对称的。确实,在第一种情况下
对于任何对称比率α,它总是成立
对称性也表现在n元关系中。集合上的关系R
还应注意,不对称关系始终是反身反射的;它是通过集合X的成员的排列而形成的。非反射和传递二进制关系始终是不对称的。对于实践和执行计算,具有与图的对称性相关的特定属性的关系数是令人感兴趣的。让我们为基数的任意集合A | A |计算这样的比率。 = n。
在我们的论证中,我们将依赖于自反性,与许多其他自反性一样,自反性尚未得到足够深入的研究。即使对所有关系的集合进行表面分析,我们也可以得出结论:它总是可以分为
所有类别中的关系集具有相同的结构,仅对角点的数量和组成有所不同,对角点的整体种类由数量决定
因此,在关系理论中,传统上仅考虑和研究两个极端状态:对角线的所有点都包含在该关系中,并且是自反的;或者该关系不包含任何对角点,然后是抗反射的。
我们将所有具有一个对角点的中间状态称为两个对角点,依此类推,第k阶k = 0(1)n的部分自反,这种类型的关系是部分自反的。因此,零阶的部分自反关系是反自反关系,而阶n的部分自反关系只是自反关系。
注意,所有状态都可以作为集合∆的布尔值的元素进行排序。提出的方法使我们能够概述分析各种属性并计算与单个属性或其集合的关系数的方式。
让这种关系被认为是反身和对称的。比率的对称性由其中存在成对的点决定,这些点对相对于对角线对称地位于比率矩阵中。对于任意n个这样的对,有
然后,对称和自反关系的全部种类将由布尔值确定。
下表中。图1显示了自然数段中初始值n的公差比的数量值。
表1。容忍BO的数量
现在很容易计算所有对称关系的基数,因为对角点的存在或不存在都不会改变对称性。对称关系集用符号SM表示。然后,由下式确定该集合对固定n的基数
表2。对称BO个数
现在让我们转向非对称关系的计算,其不对称关系的集合将用AS表示。这些关系的特征在于,对角线的所有点都不存在,并且位于对角线之外的关系矩阵的所有像元都不对称。换句话说,它是一组抗反射和抗对称关系。
该集合的基数可以从以下表达式确定
对于给定的载波基数| A | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | = n。根据定义,集合AS的所有关系都是反身;因此,关系矩阵中的主要对角线为空,单位元素只能位于矩阵其余位置的一半,即 在
因此,假设一个非对称关系包含k个元素(点,有序对)0≤k≤
在这种情况下,对于k个元素中的每一个,我们将一对对称位置关联起来:一个在矩阵主对角线上方,另一个在对角线下方,由于每对中一个元素可以位于两个位置之一,则布尔值似乎可以容纳k个元素
通过这种方式,
集合AS中的关系总数是通过将从零到最大允许K的所有k值上的所得乘积求和而获得的
例子3.让支撑的基数| A | =5。使用找到的公式计算不对称关系的数量。让我们确定总和中的上限K的值,K =
表3。BO特性
还有另一种计算集合AS的基数的方法。它基于对一组对称位置对到每个状态对可以处于的一组状态的映射数量进行计数。在不对称关系中,存在
一对像元中的每个位置都可以被0或1占据,但是对于一对位置,则存在S = 3状态,我们将其表示为:
-1,如果元素(1)放置在对角线上方;
-2,如果元素(1)位于对角线之下;
-如果两个位置都为空(由零占据),则为3。
因此,一对对称位置(在关系矩阵中)可以处于
三种状态之一的每种关系中。用于计算位置对对集合(用符号K表示)到状态S集的所有可能映射的公式为:
例子4。对于前面示例的条件,格式为| A | = 5,K = | K | =
计算结果以两种不同的方式重合,这再次证明了所获得公式的正确性。这样,我们得到了
让我们来表。4个不对称关系| AS | 对于n的小值。
表4.不对称BO的数量
有了确定非对称关系数的公式,一个人可以得到另一个-用于计算反对称关系数,因为对角点的存在或不存在都不会改变关系的反对称性。
因此,我们用符号ANS表示反对称关系的集合,则该集合的基数将由公式确定
以下是表格。5包含n = 3(1)的(ANS)值5。
表5。反对称BO的数量
在下面的内容中,我们需要方便引入的概念。
二元关系α的对称部分称为(并表示为
及物性(拉丁语Transitivus-过渡性,从Transtransus-过渡性)
-关系的属性之一。如果对任何集合A定义的关系= <M,A>是传递的换句话说,对于元素中存在元素的传递关系(
二进制关系的传递性属性的定义假定该关系至少包含三个元素(有序对)。以及该属性如何以单元素,空或仅包含两个元素的关系体现出来?
所有单例和空关系都是可传递的。如果包含在其中的对包含公共元素j,则两个元素关系可以是传递的和非传递的。对应于有序对的图的弧线指向一个方向(形成定向的非传递路径)。
例如,让(
如果像以前一样,该关系仅包含具有共同元素的两对
(
当两对没有公共元素时,也将具有传递关系。传递关系的示例为:“相等”(=),因为i = k,所以k = j表示i = j; “我大于j”;在几何上-“直线的平行度”。非传递关系的示例:几何中的“直线的垂直性”; “我不等于j”。
在有关关系的文献中,可以找到各种表征和物性的概念:弱和物性,强和物性,负和物性,反和物性,弱和物性,广义和物性,和物闭合和其他一些。这里尝试将关系中传递性属性的各种不同的阴影系统化。
对于传递关系α,该关系
传递闭包ᾰ可以根据
关系ᾰ是包含α的最小传递关系。如果α是可传递的,则它与其可传递闭包α= coincide重合,反之亦然。
当通过有向图表示传递二元关系时,可能不代表整个有向图,而仅代表其传递骨架,即。连接每条路线的起点和终点的弧长不超过一个。在这种情况下,我们说图的传递骨架是针对关系α的。此操作本质上是与传递闭合操作相反的操作,在传递闭合操作中,每个网的起点和终点通过弧线连接。
在一般情况下,对于合并关系的运算,不满足传递性。结合两个传递关系
所以
1)来自
2)来自
在这种情况下
以下是有关关系的传递性,对称性和不对称性的声明。如果二元关系是可传递的,则其对称部分
相反的只有当
传递关系α的组成本身满足关系α·α⊆α。如果关系α的补码是传递性的,即关系α是负传递的(非传递性)。ᾱ。在这种关系的矩阵中[
在这种情况下,α被称为强传递关系。矩阵元素[
除了强传递关系外,我们还考虑了弱传递(伪传递)关系,其中包括
关系α是可传递的
可比性如下
循环性
可以从集合A中定义的关系从它们中存在循环的角度来看。在关系图上进行这种考虑很方便。循环关系图始终包含至少一个闭合轮廓(路径)。忽略箭头会将路径变成循环。非循环关系图不包含循环,称为非循环或不受控制。如果可以从集合A的元素中形成至少一个形式的链,则
关系= <Å,A>是循环的
= <,A>是非循环的
是具有此属性的图形的经典示例。这些图的顶点可以重新编号,在此情况下,对于任何弧形(
如果α是抗反射传递二元关系,则它是非循环的。关系的非周期性和及物性表示其可及性。
完整性
完整性属性(完美,线性)。整个关系分为不完整和完整的关系,而其中,强烈完整的关系则更为突出。我们将通过考虑关系图来说明关系完整性的性质。
完整关系的图是完整的,即 它的任意两个顶点通过至少一个弧直接相连,即 相邻。由于图中的每个圆弧都对应于关系图的一个点(元素,对),因此可以基于以上内容来定义定义。当且仅当集合A的所有元素彼此可比或相等时,
关系= <Å,A>是完全的(完美的,线性的)。因此,总体态度是反身的。换句话说,对于任何两个元素
如果关于α有至少一对
当二元关系的图与A×A重合时,二元关系α完全完成。这种关系的图是一个完整的图,其中每对顶点通过一条边连接,并且每个顶点都有一个环。这样的图称为强完成图。总比率α总是满足关系
如果
在矩阵[
让我们计算完整关系的数量。首先,考虑线路问题。的线的比率矩阵是一个直线段垂直于比矩阵的主对角线,连接对称地位于相对于该对角矩阵的两个小区(小区)的中心。
如果两对或更多对对称位置落在比率矩阵中的一条直线(直线)上,则行数仍然与这些成对的位置数相等。任意n的位置对总数为
因此,在集合A上具有任意关系的矩阵中,存在一组L个平行段(线)。让我们用符号L-左和P-右来指定线段(线)的终点位置。也可用| L |可以放置在行尾位置的芯片。面临的挑战是确定可能的布置方式| L |芯片,因此每条线上至少有一个芯片。
显然,可以将问题减少为确定映射数f:L→线的集合L到π位置的集合(n = {A,P})。已知此类映射的数量由公式确定
根据总比率的定义,其图至少包含K个点,K =
对于每固定数量的k个点,可以将其放置的位置选择集由以下值确定:
k个附加点的位置选择和用芯片填充K-k条线的方法是独立的。因此,通过以下表达式确定将K + k点放置在2∙K个位置中以便所有行至少被一个点占据的可能性总数。
如果我们对这个表达式求和,那么我们将得到完全关系的数量,它不依赖于对角点位置的情况。换句话说,它是部分自反的完整关系的数量,例如抗反射和全自反的完整关系等。
例子5。放置对角点的情况的多样性取决于数量
对于具有三个必需属性的关系对于具有三个必需属性的
等价关系。有一个显着的结果:一组n个元素上的每个等价关系与该元素的一个分区一一对应。这种关系的数量由公式确定
贝尔数,或为递归形式
对于有序集(部分订单),此类公式未打开,其数量由直接计算确定,即 造型。对于n的小值,数据在
表6中给出。二元关系的定量特征
表6.显示:n = | A | -集合载波的基数;
|在(n)中| -非同构关系的类数;
|(n)| -偏序关系的数量;
| Gn(n)| -类的数量是偏序的非同构关系;
| Gl(n)| = n!-线性顺序关系的数量。
结论
在这项工作中,对二元比率的基本性质和结构进行了详细的分析,在此基础上可以获得具有一种或多种性质的BO的定量特征。找到并给出了具有两个和三个必需属性的某些类型关系的数量的原始比率。这些结果为建模和研究BO和较高Ar关系提供了可能性。
二手文献清单
- Aigner M.组合理论-M.:Mir,1982年。
- Birkhoff G.结构理论。-M .:伊利诺伊州,1952.-408羽
- Noden P.,Kitte K.代数算法。-M .:米尔(Mir),1999年。-720羽
- 雷布尼科夫(Rybnikov K.A.)组合分析简介。-M。:Ed。莫斯科国立大学,1972年。-256秒。
- Stanley R.枚举组合。第1卷-M .: Mir,1990 .- 440p。
- Stanley R.枚举组合。T.2.-M.:Mir,2005.-767s。
- Shikhanovich Yu.A. 现代数学概论。初始概念。-M.:纳卡(Nauka),1965年。-376p。