관계대수 (수학)

수학 및 추상대수학에서 관계대수(relation algebra)는 대합이라고 불리는 단항연산인 역으로 잔여 불 대수가 확장된 것이다. 관계대수의 동기 부여 예시는 집합 X에 대한 모든 이항 관계의 대수인 2^X 2이다. 즉, 곱집합 X²의 부분 집합이며, R•S는 이항 관계 R과 S의 일반적인 합성으로 해석되고, R의 역은 역관계로 해석된다.

관계대수는 19세기 오거스터스 드 모르간과 찰스 샌더스 퍼스의 연구에서 시작되었으며, 이는 에른스트 슈뢰더의 대수 논리에서 정점을 찍었다. 여기서 다루는 관계대수의 등식 형태는 1940년대부터 알프레트 타르스키와 그의 학생들이 개발했다. 타르스키와 기반트(1987)는 관계대수를 공리적 집합론의 변수 없는 처리에 적용했으며, 이는 집합론에 기반을 둔 수학 자체가 변수 없이 수행될 수 있음을 의미했다.

정의

관계대수 (L, ∧, ∨, ⁻, 0, 1, •, I, ˘)는 불 연산인 논리곱 x∧y, 논리합 x∨y, 부정 x⁻, 불 상수 0과 1, 관계 연산인 합성 x•y 및 역 x˘, 그리고 관계 상수 I로 구성된 대수 구조이며, 이 연산과 상수는 관계 계산의 공리화를 구성하는 특정 방정식을 만족한다. 대략적으로, 관계대수는 공집합(0), 전체(1), 항등((I)) 관계를 포함하고 이 다섯 가지 연산에 대해 닫혀 있는 집합에 대한 이항 관계 시스템에 대한 것으로, 군이 항등 순열을 포함하고 합성 및 역에 대해 닫혀 있는 집합의 순열 시스템에 대한 것과 같다. 그러나 관계대수의 1차 이론은 그러한 이항 관계 시스템에 대해 완전하지 않다.

욘슨과 치나키스(1993)에 따르면, 추가 연산 x ◁ y = x • y˘, 그리고 이중적으로 x ▷ y = x˘ • y를 정의하는 것이 편리하다. 욘슨과 치나키스는 I ◁ x = x ▷ I이며, 둘 다 x˘와 같다는 것을 보여주었다. 따라서 관계대수는 대수 구조 (L, ∧, ∨, ⁻, 0, 1, •, I, ◁, ▷)로도 정의될 수 있다. 이 서명이 일반적인 서명보다 유리한 점은 관계대수가 단순히 I ◁ x가 대합인 잔여 불 대수로 완전히 정의될 수 있다는 것이다. 즉, I ◁ (I ◁ x) = x. 후자의 조건은 일반 산술 역수에 대한 방정식 1/(1/x) = x의 관계적 대응물로 생각할 수 있으며, 일부 저자는 역수를 역의 동의어로 사용한다.

잔여 불 대수는 유한한 항등식으로 공리화되므로 관계대수도 마찬가지이다. 따라서 후자는 다양체인 관계대수의 다양체 RA를 형성한다. 위 정의를 방정식으로 확장하면 다음 유한 공리화가 산출된다.

공리

아래 공리 B1-B10은 기번트(2006: 283)에서 가져왔으며, 1948년 타르스키가 처음 제시했다.^[1]

L은 이항 논리합 ∨와 단항 여원 ()⁻에 대한 불 대수이다:

B1: A ∨ B = B ∨ A

B2: A ∨ (B ∨ C) = (A ∨ B) ∨ C

B3: (A⁻ ∨ B)⁻ ∨ (A⁻ ∨ B⁻)⁻ = A

이 불 대수 공리화는 헌팅턴 (1933)에 의한 것이다. 함축된 불 대수의 만남(meet)이 • 연산자가 아니며(비록 만남처럼 ∨에 분배되더라도), 불 대수의 1이 I 상수도 아니라는 점에 유의하라.

L은 이항 합성 (•) 및 널리 항등 I에 대한 모노이드이다:

B4: A • (B • C) = (A • B) • C

B5: A • I = A

단항 역 ()˘는 합성에 대한 대합이다:

B6: A˘˘ = A

B7: (A • B)˘ = B˘ • A˘

공리 B6은 변환을 대합으로 정의하는 반면, B7은 합성에 대한 변환의 반분배 법칙을 표현한다.^[2]

역과 합성은 논리합에 대해 분배된다:

B8: (A ∨ B)˘ = A˘ ∨ B˘

B9: (A ∨ B) • C = (A • C) ∨ (B • C)

B10은 오거스터스 드 모르간이 발견한 A • B ≤ C⁻ ${\displaystyle \leftrightarrow }$ A˘ • C ≤ B⁻ ${\displaystyle \leftrightarrow }$ C • B˘ ≤ A⁻라는 사실의 타르스키 등식 형태이다.

B10: (A˘ • (A • B)⁻) ∨ B⁻ = B⁻

이 공리들은 ZFC 정리이다. 순수히 불 대수인 B1-B3의 경우 이 사실은 자명하다. 다음 각 공리 뒤에는 ZFC에 대한 해설인 Suppes(1960) 3장의 해당 정리 번호가 나와 있다. B4 27, B5 45, B6 14, B7 26, B8 16, B9 23.

RA에서 이항 관계의 속성 표현

다음 표는 이항 관계의 일반적인 속성 중 다수가 간결한 RA 등식 또는 부등식으로 어떻게 표현될 수 있는지를 보여준다. 아래에서, A ≤ B 형태의 부등식은 불 대수 방정식 A∨B = B의 약어이다.

이러한 종류의 가장 완전한 결과 집합은 Carnap(1958)의 C장으로, 여기의 표기법과는 상당히 다르다. Suppes(1960)의 3.2장에는 더 적은 결과가 ZFC 정리로 제시되어 있으며, 이 항목의 표기법과 더 유사한 표기법을 사용한다. 카르나프와 서피스 모두 이 항목의 RA를 사용하거나 등식적인 방식으로 결과를 공식화하지 않았다.

R은	필요충분조건:
함수적	R˘ • R ≤ I
왼쪽-전사	I ≤ R • R˘ (R˘는 전사)
함수	함수적이고 왼쪽-전사.
단사	R • R˘ ≤ I (R˘는 함수적)
전사	I ≤ R˘ • R (R˘는 왼쪽-전사)
전단사	R˘ • R = R • R˘ = I (단사 전사 함수)
추이적	R • R ≤ R
반사적	I ≤ R
코리플렉시브	R ≤ I
비반사적	R ∧ I = 0
대칭적	R˘ = R
반대칭적	R ∧ R˘ ≤ I
비대칭적	R ∧ R˘ = 0
강하게 연결된	R ∨ R˘ = 1
연결된	I ∨ R ∨ R˘ = 1
멱등	R • R = R
원순서	R은 추이적이며 반사적이다.
동치	R은 대칭 원순서이다.
부분 순서	R은 반대칭 원순서이다.
전순서	R은 강하게 연결된 부분 순서이다.
엄격 부분 순서	R은 추이적이며 비반사적이다.
엄격 전순서	R은 연결된 엄격 부분 순서이다.
조밀	R ∧ I− ≤ (R ∧ I−) • (R ∧ I−).

표현력

RA의 메타수학은 타르스키와 기반트 (1987)에서 자세히 논의되며, 기반트 (2006)에서 더 간략하게 다루어진다.

RA는 균일한 대체와 등가물에 대한 등가물 대치 외에는 아무것도 사용하지 않고 조작되는 방정식으로만 구성된다. 두 규칙 모두 학교 수학 및 일반적으로 추상대수학에서 매우 친숙하다. 따라서 RA 증명은 일반적으로 수리논리학의 경우와 달리 모든 수학자에게 친숙한 방식으로 수행된다.

RA는 세 개 이하의 변수를 포함하는 1차 논리(FOL) 공식을 표현할 수 있다. (주어진 변수는 여러 번 정량화될 수 있으며, 따라서 변수를 "재사용"하여 한정 기호를 임의로 깊게 중첩할 수 있다.) 놀랍게도, 이 FOL 조각은 페아노 산술과 거의 모든 공리적 집합론을 표현하기에 충분하다. 따라서 RA는 사실상 FOL과 그 논리 연산, 한정 기호, 턴스타일 (기호), 전건 긍정 없이 거의 모든 수학을 대수화하는 방법이다. RA는 페아노 산술과 집합론을 표현할 수 있으므로, 괴델의 불완전성 정리가 적용된다. RA는 불완전하며, 완전화될 수 없고, 결정 불가능하다. (참고: RA의 불 대수 조각은 완전하고 결정 가능하다.)

표현 가능한 관계대수는 클래스 RRA를 형성하며, 특정 집합에 대한 이항 관계로 구성되고 RA 연산의 의도된 해석에 따라 닫힌 일부 관계대수와 동형사상인 관계대수이다. 예를 들어, 준원시 클래스 방법을 사용하여 RRA가 유니버설 혼 이론으로 공리화될 수 있는 준다양체임을 쉽게 증명할 수 있다. 1950년에 로저 린든은 RA에서는 성립하지 않지만 RRA에서는 성립하는 방정식의 존재를 증명했다. 따라서 RRA에 의해 생성된 다양체는 다양체 RA의 적절한 부분 다양체이다. 1955년에 알프레트 타르스키는 RRA 자체가 다양체임을 보여주었다. 1964년에 도널드 몽크는 정의상 유한하게 공리화된 RA와 달리 RRA는 유한 공리화가 없음을 보여주었다.

Q-관계대수

RA는 B1-B10 외에, (타르스키와 기반트 1987: §8.4)와 같이 일부 A와 B가 존재하면 Q-관계대수(QRA)이다.

Q0: A˘ • A ≤ I

Q1: B˘ • B ≤ I

Q2: A˘ • B = 1

본질적으로 이 공리들은 우주가 (비전사적) 짝 관계를 가지며, 그 투영은 A와 B임을 의미한다. 모든 QRA가 RRA라는 것은 정리이다 (매덕스에 의한 증명, 타르스키 & 기반트 1987: 8.4(iii) 참조).

모든 QRA는 표현 가능하다 (Tarski and Givant 1987). 모든 관계대수가 표현 가능하지 않다는 점은 RA가 QRA 및 불 대수와 근본적으로 다른 점이다. 스톤의 불 대수 표현 정리에 따르면 불 대수는 항상 합집합, 교집합, 여집합에 대해 닫힌 특정 집합의 부분 집합으로 표현 가능하다.

예시

1. 어떤 불 대수도 논리곱을 합성(모노이드 곱셈 •)으로 해석함으로써 RA로 변환할 수 있다. 즉, x • y는 x∧y로 정의된다. 이 해석은 역이 항등(ў = y)을 해석하고, 잔여 y\x와 x/y 둘 다 조건부 y → x (즉, ¬y ∨ x)를 해석하도록 요구한다.
2. 관계대수의 동기 부여 예시는 집합 X에 대한 이항 관계 R을 어떤 부분 집합 R ⊆ X²로 정의하는 것에 달려 있으며, 여기서 X²는 X의 곱집합이다. X에 대한 모든 이항 관계로 구성된 멱집합 2^X 2는 불 대수이다. 위의 예 (1)에 따라 R • S = R ∧ S로 2^X 2를 관계대수로 만들 수 있지만, •의 표준 해석은 대신 x(R • S)z = ∃y : xRy.ySz이다. 즉, 순서쌍 (x, z)가 관계 R • S에 속하는 것은 X에 y가 존재하여 (x, y) ∈ R 및 (y, z) ∈ S일 때이다. 이 해석은 R \S를 모든 x ∈ X에 대해 xRy이면 xSz인 모든 쌍 (y, z)로 구성되도록 고유하게 결정한다. 이중적으로, S/R은 X의 모든 z에 대해 yRz이면 xSz인 모든 쌍 (x, y)로 구성된다. 그러면 번역 ў = ¬(y\¬I)는 R의 역 R˘가 (x, y) ∈ R인 모든 쌍 (y, x)로 구성됨을 확립한다.
3. 이전 예제의 중요한 일반화는 E ⊆ X²가 집합 X에 대한 어떤 동치 관계인 멱집합 2^E이다. 이것은 X² 자체가 동치 관계, 즉 모든 쌍으로 구성된 완전한 관계이기 때문에 일반화이다. E ≠ X²일 때 2^E는 2^X 2의 부분 대수가 아니지만 (이 경우 관계 X²를 포함하지 않으며, 상위 요소 1은 X² 대신 E이기 때문), 연산의 동일한 정의를 사용하여 관계대수로 변환된다. 그 중요성은 어떤 집합 X에 대한 어떤 동치 관계 E에 대한 관계대수 2^E의 부분 대수와 동형인 관계대수로 표현 가능한 관계대수의 정의에 있다. 이전 섹션에서 관련 메타수학에 대해 더 자세히 설명한다.
4. G가 군이라고 하자. 그러면 멱집합 ${\displaystyle 2^{G}}$는 명백한 불 대수 연산, 군 부분 집합의 곱으로 주어진 합성, 역 부분 집합(${\displaystyle A^{-1}=\{a^{-1}\!:a\in A\}}$)으로 주어진 역, 그리고 싱글턴 부분 집합 ${\displaystyle \{e\}}$로 주어진 항등을 가진 관계대수이다. 각 부분 집합 ${\displaystyle A\subset G}$를 관계 ${\displaystyle R_{A}=\{(g,h)\in G\times G:h\in Ag\}}$로 보내는 ${\displaystyle 2^{G}}$를 ${\displaystyle 2^{G\times G}}$에 삽입하는 관계대수 동형사상이 있다. 이 동형사상의 이미지는 G에 대한 모든 오른쪽 불변 관계들의 집합이다.
5. 군의 합 또는 곱이 합성을 해석하고, 군의 역원이 역을 해석하고, 군의 항등원이 I를 해석하며, R이 일대일 대응이어서 R˘ • R = R • R˘ = I이면,^[3] L은 모노이드뿐만 아니라 군이다. B4-B7은 군론의 잘 알려진 정리가 되므로, RA는 불 대수뿐만 아니라 군론의 적절한 확장이 된다.

역사적 참고 사항

드 모르간은 1860년에 RA를 창립했지만, C. S. 퍼스는 이를 훨씬 더 발전시키고 그 철학적 힘에 매료되었다. 드 모르간과 퍼스의 연구는 주로 에른스트 슈뢰더가 그의 Vorlesungen (1890–1905) 3권에서 제시한 확장되고 명확한 형태로 알려지게 되었다. 수학 원리는 슈뢰더의 RA를 강하게 참조했지만, 그를 표기법의 발명자로만 인정했다. 1912년, 알윈 코젤트는 한정 기호가 네 단계로 중첩된 특정 공식이 RA 동등물이 없음을 증명했다.^[4] 이 사실은 타르스키 (1941)가 이에 대해 쓰기 시작할 때까지 RA에 대한 관심 상실로 이어졌다. 그의 학생들은 오늘날까지 RA를 계속 발전시켜 왔다. 타르스키는 1970년대에 스티븐 기반트의 도움을 받아 RA로 돌아왔다. 이 협력은 이 주제에 대한 결정적인 참고 자료인 타르스키와 기반트 (1987)의 모노그래프로 이어졌다. RA의 역사에 대한 더 자세한 내용은 매덕스 (1991, 2006)를 참조하라.

소프트웨어

• RelMICS / Relational Methods in Computer Science 보관됨 2020-02-01 - 웨이백 머신 Wolfram Kahl에 의해 관리됨
• Carsten Sinz: ARA / An Automatic Theorem Prover for Relation Algebras
• Stef Joosten, Ampersand 컴파일러를 사용한 프로그래밍 언어로서의 관계대수, Journal of Logical and Algebraic Methods in Programming, Volume 100, April 2018, Pages 113–129. (참조 https://ampersandtarski.github.io/)

같이 보기

• 대수 논리
• 우화 (범주론)
• 이항 관계
• 곱집합
• 카테시안 제곱
• 원통 대수
• 확장 (술어 논리)
• 대합 (수학)
• 관계 논리
• 이진 행렬
• 술어 함자 논리
• 콴탈레
• 관계 (수학)
• 관계 구성
• 관계대수
• 잔여 불 대수
• 공간-시간 추론
• 관계 이론
• 삼항 관계