关系代数 (抽象代数)

✍ dations ◷ 2025-10-16 02:39:46 #代数逻辑,数学关系,关系代数

在数学中,关系代数是支持叫做逆反(converse)的对合一元运算的剩余布尔代数。激发关系代数的例子是在集合 上的所有二元关系的代数 2 X 2 {\displaystyle 2^{X^{2}}} · 被解释为平常的二元关系复合。关系代数的早期形式形成于十九世纪德·摩根、皮尔士和 Ernst Schröder 的工作。它今日的纯等式形式是阿尔弗雷德·塔斯基和他的学生在 1940 年代开发的。

关系代数 (, ∧, ∨, ¬, 0, 1, ·, I, ▷, ◁,   ˘ {\displaystyle {\breve {\ }}} ▷ 可以使用复合和逆反而定义为   ˘ {\displaystyle {\breve {\ }}} ,对偶的 ◁ 定义为 · ˘ {\displaystyle {\breve {}}} , ∧, ∨, ¬, 0, 1, ·, I,   ˘ {\displaystyle {\breve {\ }}} ˘ {\displaystyle {\breve {}}} ▷I 要么 I◁,从而关系代数可以有同剩余布尔代数一样的标识。对于这个定义公理变成了 (▷I)▷I = = I◁(I◁)。但是这简单的断言了 ▷I 和 I◁ 是对合。Jónsson 和 Tsinakis 已经证明了如果任何一个是对合则另一个也是并且它们是同一个运算,也就是逆反。这导致了一个特别直接的定义:

当 ◁ 被看作某种形式的 对 的商的时候,I 可看作对应的乘法单位元,I◁ 可被理解为类似于 1/ 的 的“倒数”,某些作者使用这个术语作为逆反的同义词。

因为剩余布尔代数是用有限多等式公理化的,所以关系代数也是,因此它形成了一个有限公理化的簇。

1. 任何布尔代数都可作为关系代数,通过选用复合(幺半群乘法)为合取。这种复合的解释唯一的确定逆反为恒等 ( = ),而剩余 \ 和 / 二者都是蕴涵 →,也就是 ¬∨。

2. 激发关系代数的例子依赖于在集合 上的二元关系 作为任何子集 ⊆ 2 的定义。由在 上的所有二元关系构成的幂集 2 X 2 {\displaystyle 2^{X^{2}}} · = ∧ 它可以成为关系代数,给出的 · 的标准解释是 (·) = ∃.。就是说,有序对 (,) 属于关系 ·, 只有在存在 ∈ 使得 (,) ∈ 并且 (,) ∈ 的时候。这种解释唯一的确定 \ 构成自所有有序对 (,) 使得对于所有 ∈ ,如果 则 。对偶的说 / 构成自所有有序对 (,) 使得对于所有 ∈ ,如果 则 。转换 = ¬(y\¬I) 接着建立 的逆反   ˘ {\displaystyle {\breve {\ }}} ,) 使得 (,) ∈ 。

3. 这个例子的重要推广是幂集 2,这里的 ⊆ 2 是在集合 上任何等价关系。这是个推广因为 2 自身是等价关系,也就是由所有有序对构成的完全关系。而 2 在 ≠ 2 的时候,不是 2 X 2 {\displaystyle 2^{X^{2}}} 2,顶元素 1 是 而不是 2),它仍可作为使用相同运算定义的关系代数。它的重要性在于这个“可表示的关系代数”作为同构于在某个集合上的某个等价关系 的关系代数 2 的子代数的任何关系的定义中。可直接证明所有可表示的关系代数的类 RRA 是准簇,它生成自对某个集合 的形如 2 X 2 {\displaystyle 2^{X^{2}}} 是完全的当且仅当 I ≤ ·   ˘ {\displaystyle ^{\breve {\ }}} 是确定性的当且仅当   ˘ {\displaystyle ^{\breve {\ }}} ≤ I。

函数是不是完全和确定性的二元关系。下两个性质概括了通常只适用于函数的所有二元关系性质。

是自反的当且仅当 I ≤ 。

是传递的当且仅当 · ≤ 。预序是自反传递二元关系。

是反对称的当且仅当 ∧   ˘ {\displaystyle ^{\breve {\ }}} 是对称的当且仅当 ≤   ˘ {\displaystyle ^{\breve {\ }}} 。等价关系是对称预序。

在 Tarski 和 Givant (1987)的著作中详细讨论了RA 的元数学。RA 完全构成自只使用一致替换和对相等者的相等代入操纵的等式。二者的规则常见于对于学校的数学教育和一般的抽象代数。所以 RA 证明可以让所有数学用更熟悉的方式来完成,而不像一般的数理逻辑那样。

RA 可以表达任何(精确地说逻辑等价于)包含不多于三个变量的一阶逻辑(FOL)公式(一个给定的变量可被量化多次只要量词不嵌套)。另人惊讶,这个 FOL 片段足够表达皮亚诺算术和几乎所有已经提议的公理化集合论。所以 RA 在效果上是代数化几乎所有数学的一种方式,而免除了 FOL 和它的连结词、量词、十字转门和肯定前件。因为 RA 可以表达皮亚诺算术和集合论,哥德尔不完备性定理适用于它, RA 是不完备的、不可完备的和不可判定性的。(N.B. 这些性质不能描述 RA 的布尔逻辑片段。)

形成的类 RRA 的可表示的关系代数是同构于构成自在某个集合上的二元关系并闭合于 RA 运算的标准解释的某个关系代数的那些关系代数。比如使用伪基本类的方法就可轻易证明,就是 RRA 是个准簇,也就是可用全称 Horn 理论公理化。在 1950 年 Roger Lyndon 证明了成立于 RRA 而不成立于 RA 的等式的存在,就是说 RRA 生成的簇是簇 RA 的真子簇。在 1955 年 Alfred Tarski 证明了 RRA 自身是个簇,但是 Donald Monk 在 1964 年证明它没有有限公理化,不像 RA 可以通过定义有限公理化。不是所有关系代数都是可表示的是它同布尔代数之间的根本区别,它可以表示为某个集合的闭合在并集、交集和补集下的子集的集合。

德·摩根在 1860 年创立了 RA,而皮尔士深化了它并着迷于它的哲学力量。德·摩根和皮尔士的工作主要为人所知于 Ernst Schröder 在他的《Vorlesungen über die Algebra der Logik》(1890-1905) 中给出的扩展和终极形式中。《数学原理》受到 Schröder 的 RA 的强烈影响,但他却只被认可为这个概念的发明者。这里提供 RA 的基础论文是 Tarski (1941) 给出的;他设计了上述公理,他和他的学生直到今天仍在持续致力于 RA。Tarski 和 Givant (1987) 的很多内容是 Tarski 在 1940 年代独自完成,他在 1970 年代随着 Steven Givant 的帮助而重返这个主题。RA 的更详细的历史请参见 Maddux (2006)。

相关

  • 外交美国建交列表美利坚合众国目前已与189个国家保持外交关系(2018年9月)。联合国成员国中,伊朗、叙利亚与美国仍处于断交状态,朝鲜民主主义人民共和国因与美国相互敌对而未建交,不丹
  • 环腺苷酸环腺苷酸(英语:Cyclic adenosine monophosphate,简称为cAMP)是一种具有细胞内信息传递作用的小分子,被称为细胞内信使(intracellular messenger)或第二信使(second messengers)
  • 科西嘉人科西嘉人(英语:corsicans),是主要分布在法国科西嘉岛上的民族,总人口约32万人(2013年),使用科西嘉语,主要信仰天主教。科西嘉岛有322120人口(2013年1月估计)。) 在2011年的人口普查,科西
  • 内贾德马哈茂德·艾哈迈迪-内贾德(波斯语:محمود احمدی‌نژاد‎,转写:Mahmūd Ahmadinezhād,发音:  ( 发音),1956年10月28日-)是伊朗第6任总统,同时是伊朗保守派政治联盟伊斯
  • 林赛·沃恩林赛·沃恩(英语:Lindsey Vonn,1984年10月18日-),美国高山滑雪运动员,2010年温哥华冬奥会女子高山速降冠军,也是获得该项目奥运金牌的首个美国人。她生于美国明尼苏达州,16岁入选国家
  • 上甘岭战役联合国军:上甘岭战役是朝鲜战争后期僵持阶段的一次主要战役,为美军“摊牌行动”(Operation Showdown)的一部分。1952年夏季,美第9军计划动用美国陆军第7师,大韩民国陆军第2师及第9
  • 绍兴 (南宋)绍兴(1131年-1162年)是南宋皇帝宋高宗的第二个也是最后一个年号,共计32年,有承继前业,振兴昌盛又或是绍奕世之宏修,兴百年之丕绪之意。绍兴三十二年六月宋孝宗即位沿用。1. 郾城之
  • 后台进程后台进程()是一种在不需用户干预的情况下运行于操作系统后台的计算机进程 ,通常用于执行如日志记录(英语:Computer data logging)、系统监测、作业调度以及用户提醒(英语:Notificati
  • 华沙莫德林机场华沙莫德林机场(波兰语:Port Lotniczy Warszawa/Modlin;IATA代码:WMI;ICAO代码:EPMO)是波兰首都华沙的一座次要民用机场,亦是华沙的两座民用机场之一(另一座是华沙萧邦机场),位于该国的
  • 斯特尔米洛夫斯特尔米洛夫是捷克的城镇,位于该国南部,距离因德日赫城堡15公里,由南波希米亚州负责管辖,面积30.58平方公里,海拔高度545米,2011年人口1,456。