반환 (수학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

반환(semiring)은 덧셈과 곱셈 연산이 정의된 대수 구조로, 덧셈에 대해 가환 모노이드를 이루고 곱셈에 대해 모노이드를 이루며 분배 법칙과 0과의 곱 연산을 만족한다. 반환은 환의 일반화된 형태로, 덧셈에 대한 역원의 존재를 요구하지 않는다. 가환 반환은 곱셈이 교환 법칙을 만족하는 반환이며, 멱등 반환은 덧셈이 멱등 연산인 반환이다. 반환은 완비성, 연속성, 스타 반환 등의 확장된 개념을 가지며, 그래프 이론, 최적화 문제, 확률적 모델링 등 다양한 분야에 응용된다. 일반화된 구조로는 헤미링, 준반환, 근환 등이 있다.

2. 정의

반환은 덧셈과 곱셈 연산이 정의된 집합에 대한 대수 구조로, 다음 성질들을 만족한다.^[4]

덧셈에 대해 결합 법칙과 교환 법칙이 성립하며, 덧셈 항등원 0이 존재하여 가환 모노이드를 이룬다.
곱셈에 대해 결합 법칙이 성립하며, 곱셈 항등원 1이 존재하여 모노이드를 이룬다.
덧셈과 곱셈 사이에 분배 법칙이 성립한다.
임의의 원소에 0을 곱하면 항상 0이 된다. (0은 흡수 원소)

환에서는 0과의 곱이 항상 0이라는 성질이 다른 공리들로부터 유도되지만, 반환에서는 이 조건을 명시적으로 요구해야 한다. 반환은 환과 달리 덧셈에 대해 가환군이 아니라 가환 모노이드이기만 하면 된다는 차이점이 있다.

곱셈 연산 기호는 생략 가능하며(예: ''ab'' = ''a'' · ''b''), 곱셈은 덧셈보다 연산 우선순위를 가진다.

곱셈이 교환 법칙을 만족하면 가환 반환(commutative semiring)이라고 부른다.^[1] 덧셈이 멱등 연산(모든 a에 대해 a + a = a)이면 멱등 반환(idempotent semiring) 또는 디오이드(dioid)라고 부른다.

일부 문헌에서는 반환에 0과 1이 반드시 존재해야 한다는 조건을 제외하기도 하는데, 이 경우 여기서 정의된 반환은 'rig'라고 불린다.

2. 1. 반환

semiring^영어

(R,0,+,1,\cdot)

은 다음과 같은 연산이 갖추어진 대수 구조이다.^[4]

$(R,0,+)$ 는 덧셈에 대해 결합 법칙, 교환 법칙이 성립하고 항등원 0을 가지는 가환 모노이드이다.
$(R,1,\cdot)$ 는 곱셈에 대해 결합 법칙이 성립하고 항등원 1을 가지는 모노이드이다.
분배 법칙이 성립한다.
영원(0)과의 곱은 항상 0이다.

곱셈이 가환인 반환을 '''가환 반환''' (''commutative semiring'')이라고 한다. 덧셈이 멱등 연산이 되는(즉, 임의의 ''a''가 ''a'' + ''a'' = ''a''를 만족하는) 반환을 '''멱등 반환''' (''idempotent semiring'', '''dioid''')이라고 한다.

문헌에 따라서는 반환이 0과 1을 가질 것을 가정하지 않는 것도 있다. 이 경우, 본 항목에서 말하는 "반환"의 개념을 특히 ''rig''라고 불러 구분하기도 한다.

2. 2. 유사 반환

pseudo-semiring^영어 또는 hemiring^영어이라고 불리는 유사 반환은 곱셈 항등원(1)의 존재를 요구하지 않는다는 점을 제외하면 반환과 유사한 대수 구조이다.

유사 반환

(R, 0, +, \cdot)

은 다음 조건을 만족한다.

$(R, 0, +)$ 는 가환 모노이드이다. 즉, 다음이 성립한다.
*(덧셈의 결합 법칙) 모든 원소 $r, s, t \in R$ 에 대하여 $(r + s) + t = r + (s + t)$ 이다.
*(덧셈의 교환 법칙) 모든 원소 $r, s \in R$ 에 대하여 $r + s = s + r$ 이다.
*(덧셈의 항등원) 모든 원소 $r \in R$ 에 대하여 $r + 0 = r$ 이다.
$(R, \cdot)$ 는 반군을 이룬다.
*(곱셈의 결합 법칙) 모든 원소 $r, s, t \in R$ 에 대하여 $(rs)t = r(st)$ 이다.
(분배 법칙) 모든 원소 $r, s, t \in R$ 에 대하여, $r(s + t) = rs + rt$ 이며 $(s + t)r = sr + tr$ 이다.
(0과의 곱) 모든 원소 $r \in R$ 에 대하여, $0r = r0 = 0$ 이다.

2. 3. 가환 반환

곱셈이 교환 법칙을 만족하는 반환이다. 세미링은 곱셈 또한 가환적이면 '''가환 세미링'''이라고 한다.^[1] 이의 공리는 간결하게 표현할 수 있다. 이는 하나의 집합에 대한 두 개의 가환 모노이드

\langle +, 0\rangle

와

\langle \cdot, 1\rangle

로 구성되며, 여기서

a\cdot 0 = 0

및

a\cdot (b+c)=a\cdot b + a\cdot c

이다.

세미링의 중심은 부분 세미링이며, 가환적이라는 것은 스스로의 중심이라는 것과 동등하다.

자연수의 가환 세미링은 이 종류의 시작 대상이며, 이는

{\mathbb N}

에서 모든 가환 세미링으로의 구조를 보존하는 유일한 사상이 존재함을 의미한다.

유계 분배 격자는 부분 순서를 가지는 가환 세미링이며, 분배성과 멱등성에 관련된 특정 대수 방정식을 충족한다. 따라서 이들의 쌍대 또한 그러하다.

2. 4. 멱등 반환

모든 원소가 덧셈 멱등원인, 즉 모든 원소

x

에 대해

x+x=x

인 세미링을 '''(덧셈) 멱등 세미링'''이라고 한다.

3. 성질

반환은 덧셈과 곱셈이 결합 법칙을 따르고, 덧셈에 대한 항등원 0과 곱셈에 대한 항등원 1이 존재하며, 분배 법칙이 성립하는 대수 구조이다. 반환의 기본적인 성질은 다음과 같다.

1은 좌영인자나 우영인자가 아니다. 즉, 1을 곱해도 원래 원소가 변하지 않는다.^[3]
0과 1은 모두 멱등원이다. 즉, 자기 자신을 제곱해도 자기 자신이 된다.^[3]

체는 곱셈 역원이 존재하는 반체이며, 환은 덧셈 역원이 존재하는 반환이다. 반환은 환과 달리 덧셈 역원의 존재를 요구하지 않으며, 가환 모노이드만 필요하다. 환은 곱셈 영원의 존재를 가정하지만, 반환에서는 명시적으로 지정해야 한다.^[3]

세미링이 가환적이면 '''가환 세미링'''이라고 한다. 가환 세미링의 공리는 두 개의 가환 모노이드

\langle +, 0\rangle

와

\langle \cdot, 1\rangle

로 구성되며,

a\cdot 0 = 0

및

a\cdot (b+c)=a\cdot b + a\cdot c

를 만족한다. 세미링의 중심은 부분 세미링이며, 가환적이라는 것은 스스로의 중심이라는 것과 같다.

자연수의 가환 세미링은 이 종류의 시작 대상이며,

{\mathbb N}

에서 모든 가환 세미링으로의 구조를 보존하는 유일한 사상이 존재한다.^[3]

유계 분배 격자는 부분 순서를 가지는 가환 세미링이며, 분배성과 멱등성에 관련된 특정 대수 방정식을 충족한다. 따라서 이들의 쌍대 또한 그러하다. 순서의 개념은 엄격, 비엄격 또는 2차 공식으로 정의될 수 있으며, 교환성과 같은 추가적인 속성은 공리를 단순화한다.^[3]

3. 1. 순서 관계

Semiring^영어에서 덧셈을 통해 정의되는 전순서 관계(≤pre)는 다음과 같이 정의된다.

: ''x'' ≤pre ''y''는 어떤 ''d''에 대해 ''x'' + ''d'' = ''y'' 를 만족하는 경우이다.

이 관계는 반환의 덧셈 연산에 대해 정의되며, 항상 오른쪽 표준 전순서 관계를 구성한다. 반사성(''y'' ≤pre ''y'')은 항등원에 의해 증명된다. 또한, 0 ≤pre ''y''는 항상 유효하며, 따라서 0은 이 전순서에 대한 최소 원소이다. 특히 가환 덧셈에 대해 고려할 때, "오른쪽"의 구분은 무시될 수 있다. 예를 들어, 음이 아닌 정수 N^영어에서 이 관계는 반대칭적이며 강하게 연결되어 있으며, 따라서 실제로 (비 엄격한) 전순서이다.^[3]

모든 원소 ''x''에 대해 ''x'' + ''x'' = ''x''인 멱등 Semiring^영어에서, ''x'' ≤pre ''y''는 ''x'' + ''y'' = ''y''와 동일하며, 항상 부분 순서를 구성한다. 이때는 ''x'' ≤ ''y''로 표기한다. 특히, 이 경우 ''x'' ≤ 0 ↔ ''x'' = 0 이다. 따라서 덧셈 멱등 Semiring^영어은 영합이 아니고, 실제로 모든 덧셈 역원을 갖는 유일한 덧셈 멱등 Semiring^영어은 자명환이므로 이 속성은 Semiring^영어 이론에 특수하다. 덧셈과 곱셈은 순서를 존중한다. 즉, ''x'' ≤ ''y''이면 ''x'' + ''t'' ≤ ''y'' + ''t''이고, 모든 ''x'', ''y'', ''t'' 및 ''s''에 대해 ''s'' · ''x'' ≤ ''s'' · ''y''와 ''x'' · ''s'' ≤ ''y'' · ''s''를 의미한다.^[3]

3. 2. 멱등성

모든 원소

x

에 대해

x+x=x

인 반환을 '''(덧셈) 멱등 반환'''이라고 한다.

1 + 1 = 1

임을 증명하는 것으로 충분하다. 때로는 곱셈 규칙과 관계없이 이것을 단순히 멱등 반환이라고 부르기도 한다.

이러한 반환에서

x\le_\text{pre} y

는

x + y = y

와 동일하며 항상 부분 순서를 구성하며, 여기서는

x\le y

로 표기한다. 특히,

x \le 0\leftrightarrow x = 0

이다. 따라서 덧셈 멱등 반환은 영합이 아니고, 실제로 모든 덧셈 역원을 갖는 유일한 덧셈 멱등 반환은 자명환이므로 이 속성은 반환 이론에 특수하다. 덧셈과 곱셈은

x \le y

가

x + t \leq y + t

를 의미하고, 더 나아가 모든

x, y, t

및

s

에 대해

s\cdot x \le s\cdot y

와

x\cdot s \le y\cdot s

를 의미한다는 점에서 순서를 존중한다.

R

이 덧셈 멱등이면,

R[X^*]

의 다항식도 그렇다.

기초 집합에 격자 구조가 있는 반환은 합이 만남과 일치하고

x + y = x\lor y

, 곱이 결합 아래에 있으면

x\cdot y \le x\land y

이면 '''격자 정렬'''이라고 한다. 반환의 아이디얼의 격자 정렬 반환은 격자 구조에 대해 반드시 분배 격자는 아니다.

단순히 덧셈 멱등성보다 더 엄격하게, 반환은 모든

x

에 대해

x+1=1

이면 '''단순'''이라고 한다. 그러면 또한

1+1=1

이고 모든

x

에 대해

x \le 1

이다. 여기서

1

은 덧셈으로 무한한 요소와 유사하게 기능한다.

R

이 덧셈 멱등 반환이면, 상속된 연산을 가진

\{x\in R\mid x+1=1\}

는 단순한 하위 반환이다. 단순하지 않은 덧셈 멱등 반환의 예로는 표준 순서에 따라 2항 최댓값 함수를 덧셈으로 사용하는

{\mathbb R}\cup\{-\infty\}

에 대한 트로피칼 반환이 있다. 이 반환의 단순한 하위 반환은 자명하다.

'''c-반환'''은 임의의 집합에 대해 정의된 덧셈을 가진 멱등 반환이다.

곱셈이 멱등원인 덧셈 멱등 반환, 즉

x^2=x

는 '''덧셈 및 곱셈 멱등 반환'''이라고 하지만, 때로는 그냥 멱등 반환이라고도 한다. 해당 속성을 가진 가환적이고 단순한 반환은 고유한 최소 및 최대 원소를 갖는 경계 분배 격자(이는 단위이다)와 정확히 일치한다. 헤이팅 대수는 그러한 반환이고, 부울 대수는 특별한 경우이다.

또한, 두 개의 경계 분배 격자가 주어지면, 구조의 직접 합보다 더 복잡한 가환적 덧셈-멱등 반환을 생성하는 구성이 있다.

3. 3. 완비성 및 연속성

완전 모노이드인 덧셈 모노이드를 갖는 반환은 '''완전 반환'''이다. 이는 임의의 인덱스 집합

I

에 대한 무한 합 연산

\Sigma_I

를 가지며, 다음의 (무한) 분배 법칙이 성립해야 함을 의미한다.^[2]

:

{\textstyle\sum}_{i \in I}{\left(a \cdot a_i\right)} = a \cdot \left({\textstyle\sum}_{i \in I}{a_i}\right), \qquad {\textstyle\sum}_{i \in I}{\left(a_i \cdot a\right)} = \left({\textstyle\sum}_{i \in I}{a_i}\right) \cdot a.

완전 반환의 예시로는 결합에 대한 모노이드의 멱집합과 완전 반환에 대한 행렬 반환이 있다.

'''연속 반환'''은 덧셈 모노이드가 연속 모노이드인 것으로 유사하게 정의된다. 즉, 최소 상한 속성을 가진 부분 순서 집합이며, 덧셈과 곱셈이 순서와 상한을 존중한다. 일반적인 덧셈, 곱셈, 순서로 확장된 반환

\N \cup \{ \infty \}

는 연속 반환이다.

모든 연속 반환은 완비이다.^[2]

3. 4. 스타 반환

스타 반환(star semiring)은 추가적인 단항 연산

{}^*

를 가진 반환으로, 다음을 만족한다.^[2]

:

a^* = 1 + a a^* = 1 + a^* a.

클레이니 대수(Kleene algebra)는 멱등적인 덧셈과 몇 가지 추가적인 공리를 가진 스타 반환이다. 이는 형식 언어와 정규 표현식 이론에서 중요하다.

'''완전 별 반환'''에서 별 연산자는 일반적인 클레이니 스타처럼 작동한다. 완전 반환의 경우, 무한 합 연산자를 사용하여 클레이니 스타의 일반적인 정의를 제공한다.^[2]

:

a^* = {\textstyle\sum}_{j \geq 0}{a^j},

여기서

:

a^j = \begin{cases}1,                                 & j = 0,\\a \cdot a^{j-1} = a^{j-1} \cdot a, & j > 0.\end{cases}

별 반환은 *-대수와는 관련이 없는데, *-대수에서 별 연산은 복소 켤레로 생각해야 한다.

'''컨웨이 반환'''은 다음의 합-별 및 곱-별 방정식을 만족하는 별 반환이다.

:

\begin{align}(a + b)^* &= \left(a^* b\right)^* a^*, \\(ab)^* &= 1 + a(ba)^* b.\end{align}

모든 완전 별 반환은 컨웨이 반환이기도 하지만,^[2] 그 역은 성립하지 않는다. 완전하지 않은 컨웨이 반환의 예로는, 일반적인 덧셈과 곱셈을 사용하는 확장된 음이 아닌 유리수 집합

\Q_{\geq 0} \cup \{ \infty \}

가 있다(이는 확장된 음이 아닌 실수에 대한 예시를 무리수를 제거하여 수정한 것이다).^[2]

'''반복 반환'''은 존 컨웨이가 별-반환의 그룹과 연관지어, 컨웨이 그룹 공리를 만족하는 컨웨이 반환이다.

스타 연산을 갖춘 구조는 다음과 같다.

어떤 기본 집합 $U$ 에 대한 이진 관계의 세미링은 모든 $R\subseteq U \times U$ 에 대해 $R^* = \bigcup_{n \geq 0} R^n$ 이다. 이 스타 연산은 $R$ 의 반사적 폐포와 추이적 폐포이다(즉, $R$ 을 포함하는 $U$ 에 대한 가장 작은 반사적이고 추이적인 이진 관계).^[2]
형식 언어의 세미링 또한 완전한 스타 세미링이며, 스타 연산은 클레이니 스타와 일치한다(집합/언어의 경우).^[2]
확장된 실수의 음이 아닌 집합 $[0, \infty]$ 는 실수의 일반적인 덧셈 및 곱셈과 함께 $0 \leq a < 1$ 에 대해 $a^* = \tfrac{1}{1 - a}$ (즉, 등비 급수) 및 $a \geq 1$ 에 대해 $a^* = \infty$ 로 주어진 스타 연산과 함께 완전한 스타 세미링이다.^[2]
$0^* = 1^* = 1.$ 을 갖는 부울 세미링^[2]
확장된 덧셈과 곱셈을 사용하는 $\N \cup \{ \infty \},$ 에 대한 세미링, 그리고 $0^* = 1, a^* = \infty$ for $a \geq 1.$ ^[2]

4. 예시

모든 환과 유사환은 반환을 이룬다.
모든 환과 반체는 반환이다.
자연수 집합 $\mathbb N = \{0, 1, 2, \dots \}$ 은 표준적인 덧셈과 곱셈 연산에 대해 반환을 이룬다.
음이 아닌 유리수와 음이 아닌 실수는 가환 순서 반환이다.^[3] 이들은 확률 반환이라고도 불린다.
확장된 자연수 $\N \cup \{ \infty \}$ 는 덧셈 및 곱셈이 확장되어 $0 \cdot \infty = 0$ 이 되는 반환이다.
자연수 계수를 갖는 다항식 집합( $\N[x]$ 로 표시)은 가환 반환을 형성한다. 이는 단일 생성자 $\{ x \}$ 에 대한 자유 가환 반환이다.
음이 아닌 종료 분수 $\tfrac{\N}{b^{\N}} := \left\{ mb^{-n} \mid m, n \in \N \right\}$ 는 주어진 밑수 $b\in \N$ 에 대한 자리 표기법에서 유리수의 하위 반환을 형성한다.
열대 반환은 반환 덧셈(항등원 $- \infty$ )으로 $\max(a, b)$ 를 사용하고 반환 곱셈으로 일반 덧셈(항등원 0)을 사용하는 가환 반환 $\R \cup \{ - \infty \}$ 이다.
우카시에비치 반환은 덧셈이 인수의 최댓값을 취하고( $\max(a, b)$ ) 곱셈이 $\max(0, a + b - 1)$ 로 주어지는 닫힌 구간 $[0, 1]$ 이며, 다치 논리에 나타난다.
비터비 반환은 기본 집합 $[0, 1]$ 에서 정의되며 최댓값을 덧셈으로 갖지만, 곱셈은 실수의 일반적인 곱셈이며, 확률적 구문 분석에 나타난다.
주어진 반환의 모든 아이디얼 집합은 아이디얼의 덧셈과 곱셈에서 반환을 형성한다.
모든 경계 분배 격자는 합집합과 교집합에서 가환 반환이다. 불 대수는 이러한 특수한 경우이다.
$1 + 1 = 1$ 로 정의된 두 원소 부울 대수에 의해 형성된 가환 반환은 부울 반환이라고도 한다.^[3]
모든 단위 퀀탈은 합집합과 곱셈에서 반환이다.
환 $R$ 에서 정규 왜곡 격자는 곱셈과 nabla 연산( $a \nabla b = a + b + ba - aba - bab$ 로 정의)에 대한 반환이다.
가환 모노이드 $M$ 에서 반환 $\operatorname{End}(M)$ 을 구성할 수 있다. 반환 $R$ 이 주어지면, $n\times n$ 행렬은 또 다른 반환을 형성한다. 예를 들어, 음이 아닌 항목을 갖는 행렬 ${\mathcal M}_n(\N)$ 은 행렬 반환을 형성한다.^[3]
알파벳(유한 집합) Σ가 주어지면, $\Sigma$ 에 대한 형식 언어의 집합( $\Sigma^*$ 의 부분 집합)은 문자열 연결 $L_1 \cdot L_2 = \left\{ w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2 \right\}$ 에 의해 유도된 곱셈을 사용하고 언어의 합집합을 사용한 덧셈을 사용하는 반환이다.
$(M, e, \cdot)$ 가 모노이드이면, $M$ 의 유한 멀티셋 집합은 반환을 형성한다.
집합 $U$ 가 주어지면, $U$ 에 대한 이항 관계 집합은 덧셈이 합집합이고 곱셈이 관계의 합성인 반환이다.
조합론적 클래스의 동형 클래스는 덧셈으로 클래스의 분리 합집합, 곱셈으로 클래스의 데카르트 곱을 포함한다.
분배 범주의 객체의 동형 클래스는 공합 및 곱 연산에서 Burnside rig로 알려진 반환을 형성한다.
Kleene algebra^영어는 클리니 스타라고 불리는 단항 연산 ∗: ''R'' → ''R''을 갖춘 멱등 반환 ''R''이다. 클리니 대수는 형식 문법이나 정규 표현식의 이론에서 중요하다.

4. 1. 일반적인 예시

모든 환은 반환을 이루며, 모든 유사환은 유사 반환을 이룬다.^[3]
환 $R$ 속의 양쪽 아이디얼들의 집합은 아이디얼의 덧셈과 곱셈에 대하여 반환을 이룬다. 이 경우 덧셈 항등원은 영 아이디얼 $\{0\}$ 이며, 곱셈 항등원은 전체 아이디얼 $R$ 이다.
모든 유계 분배 격자 (예를 들어, 불 대수)는 만남과 이음을 통하여 반환을 이룬다. 이 경우, 덧셈을 만남으로, 곱셈을 이음으로 삼거나, 또는 곱셈을 만남으로, 덧셈을 이음으로 삼아 두 개의 반환 구조를 줄 수 있다. 덧셈이 만남일 경우 덧셈 항등원은 최소 원소 $\bot$ , 곱셈 항등원은 최대 원소 $\top$ 이며, 덧셈이 이음일 경우 덧셈 항등원은 $\top$ , 곱셈 항등원은 $\bot$ 이다.
자연수의 가환 반환은 이 종류의 시작 대상이며, 이는 ${\mathbb N}$ 에서 모든 가환 반환으로의 구조를 보존하는 유일한 사상이 존재함을 의미한다.
음이 아닌 유리수와 음이 아닌 실수도 가환 순서 반환을 형성한다.^[3] 후자는 확률 반환이라고 한다.
확장된 자연수 $\N \cup \{ \infty \}$ 는 덧셈 및 곱셈이 확장되어 $0 \cdot \infty = 0$ 이 된다.
자연수 계수를 갖는 다항식 집합은 $\N[x],$ 로 표시되며 가환 반환을 형성한다. 이것은 단일 생성자 $\{ x \}$ 에 대한 자유 가환 반환이다.
열대 반환은 다양하게 정의된다. 반환 $\R \cup \{ - \infty \}$ 는 반환 덧셈(항등원 $- \infty$ )으로 $\max(a, b)$ 를 사용하고 반환 곱셈으로 일반 덧셈(항등원 0)을 사용하는 가환 반환이다.
우카시에비치 반환: 덧셈이 인수의 최댓값을 취하여 ( $\max(a, b)$ ) 주어지고 곱셈이 $\max(0, a + b - 1)$ 로 주어지는 닫힌 구간 $[0, 1]$ 이 다치 논리에 나타난다.
비터비 반환도 기본 집합 $[0, 1]$ 에서 정의되며 최댓값을 덧셈으로 갖지만, 곱셈은 실수의 일반적인 곱셈이다. 이는 확률적 구문 분석에 나타난다.
주어진 반환의 모든 아이디얼 집합은 아이디얼의 덧셈과 곱셈에서 반환을 형성한다.
모든 경계 분배 격자는 합집합과 교집합에서 가환 반환이다. 불 대수는 이러한 특수한 경우이다.
$1 + 1 = 1$ 로 정의된 두 원소 부울 대수에 의해 형성된 가환 반환. 이는 부울 반환이라고도 한다.^[3]
모든 단위 퀀탈은 합집합과 곱셈에서 반환이다.
환 $R$ 에서 정규 왜곡 격자는 곱셈과 nabla 연산에 대한 반환이며, 후자 연산은 $a \nabla b = a + b + ba - aba - bab$ 로 정의된다.
알파벳(유한 집합) Σ가 주어지면, $\Sigma$ 에 대한 형식 언어의 집합( $\Sigma^*$ 의 부분 집합)은 문자열 연결 $L_1 \cdot L_2 = \left\{ w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2 \right\}$ 에 의해 유도된 곱셈을 사용하고 언어의 합집합(즉, 집합으로서의 일반 합집합)을 사용한 덧셈을 사용하는 반환이다.
집합 $U$ 가 주어지면, $U$ 에 대한 이항 관계 집합은 덧셈이 합집합(집합으로서의 관계)이고 곱셈이 관계의 합성인 반환이다.
조합론적 클래스의 동형 클래스는 덧셈으로 클래스의 분리 합집합, 곱셈으로 클래스의 데카르트 곱을 포함한다.
분배 범주의 객체의 동형 클래스는 공합 및 곱 연산에서 Burnside rig로 알려진 반환을 형성한다.
Kleene algebra^영어는 클리니 스타라고 불리는 단항 연산 ∗: ''R'' → ''R''을 갖춘 멱등 반환 ''R''이다. 클리니 대수는 형식 문법이나 정규 표현식의 이론에서 중요하다.

4. 2. 구체적인 예시

자연수 집합 $\mathbb N = \{0, 1, 2, \dots \}$ 은 표준적인 덧셈과 곱셈 연산에 대해 반환을 이룬다.
음이 아닌 유리수와 음이 아닌 실수도 가환 순서 반환을 이룬다.^[3] 이들은 확률 반환이라고도 불린다.
주어진 반환의 모든 아이디얼 집합은 아이디얼의 덧셈과 곱셈에서 반환을 형성한다.
모든 경계 분배 격자는 합집합과 교집합에서 가환 반환이다. 부울 대수는 이러한 특수한 경우이다.
환 $R$ 에서 정규 왜곡 격자는 곱셈과 nabla 연산에 대한 반환이며, 후자 연산은 $a \nabla b = a + b + ba - aba - bab$ 로 정의된다.
가환 모노이드 $M$ 에서 반환 $\operatorname{End}(M)$ 을 구성할 수 있다. 반환 $R$ 이 주어지면, $n\times n$ 행렬은 또 다른 반환을 형성한다. 예를 들어, 음이 아닌 항목을 갖는 행렬 $_n(\N),$ 은 행렬 반환을 형성한다.^[3]
알파벳(유한 집합) Σ가 주어지면, $\Sigma$ 에 대한 형식 언어의 집합( $\Sigma^*$ 의 부분 집합)은 문자열 연결 $L_1 \cdot L_2 = \left\{ w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2 \right\}$ 에 의해 유도된 곱셈을 사용하고 언어의 합집합(즉, 집합으로서의 일반 합집합)을 사용한 덧셈을 사용하는 반환이다.
$(M, e, \cdot)$ 가 모노이드이면, $M$ 의 유한 멀티셋 집합은 반환을 형성한다.
집합 $U$ 가 주어지면, $U$ 에 대한 이항 관계 집합은 덧셈이 합집합(집합으로서의 관계)이고 곱셈이 관계의 합성인 반환이다.
우카시에비치 반환: 덧셈이 인수의 최댓값을 취하여 ( $\max(a, b)$ ) 주어지고 곱셈이 $\max(0, a + b - 1)$ 로 주어지는 닫힌 구간 $[0, 1]$ 이 다치 논리에 나타난다.
비터비 반환도 기본 집합 $[0, 1]$ 에서 정의되며 최댓값을 덧셈으로 갖지만, 곱셈은 실수의 일반적인 곱셈이다. 이는 확률적 구문 분석에 나타난다.
열대 반환: 반환 $\R \cup \{ - \infty \}$ 는 반환 덧셈(항등원 $- \infty$ )으로 $\max(a, b)$ 를 사용하고 반환 곱셈으로 일반 덧셈(항등원 0)을 사용하는 가환 반환이다. 이는 대수적 다양체를 구간별 선형 다양체 구조와 연결하는 활발한 연구 분야이다.

5. 확장

순서 이론에는 몇 가지 상반되는 이산성 개념이 있다. 반환에 엄격한 순서가 주어지면, 그러한 개념 중 하나는 1이 양수이고 0을 덮는 것으로 주어진다. 즉, 단위 사이에는 원소 x가 없다. (¬(0 < x ∧ x < 1)) 이 맥락에서 순서는 이것이 충족되고, 반환의 모든 원소가 음수가 아니므로 반환이 단위로 시작하는 경우 '이산적'이라고 한다.

$\mathsf{PA}^-$ 는 엄격한 순서를 대수적 구조와 관련시키는 위의 네 가지 속성을 검증하는 가환적이고 이산적으로 정렬된 반환의 이론으로 표기한다. 모든 모델은 모델 $\N$ 을 초기 세그먼트로 가지며, 괴델의 불완전성과 타르스키의 무정의성이 이미 $\mathsf{PA}^-$ 에 적용된다. 가환적이고 이산적으로 순서화된 환의 음수가 아닌 원소는 항상 $\mathsf{PA}^-$ 의 공리를 검증한다. 따라서 이론의 약간 더 이국적인 모델은 다항식 환 $\mathbb{Z}[X]$ 의 양의 원소로 주어지며, $p = \textstyle\sum_{k=0}^n a_k X^k$ 에 대한 양수 조건은 마지막 0이 아닌 계수 $0 < p := (0 < a_n)$ 과 같이 $p < q := (0 < q - p)$ 에 대해 정의된다. $\mathsf{PA}^-$ 은 $\N$ 에 대해 참인 모든 $\Sigma_1$ -문장을 증명하지만, 이 복잡성을 넘어서면 $\mathsf{PA}^-$ 에서 독립적인 간단한 진술을 찾을 수 있다. 예를 들어, $\N$ 에 대해 참인 $\Pi_1$ -문장은 방금 정의한 다른 모델에도 여전히 참이지만, 다항식 $X$ 를 검사하면 모든 숫자가 $2q$ 또는 $2q+1$ ("홀수 또는 짝수") 형태라는 $\Pi_2$ -주장에 대한 $\mathsf{PA}^-$ 의 독립성이 나타난다. 또한 $\mathbb{Z}[X, Y]/(X^2 - 2Y^2)$ 을 이산적으로 정렬할 수 있음을 보여주면 0이 아닌 $x$ 에 대한 $\Pi_1$ -주장 $x^2 \neq 2y^2$ ("어떤 유리수 제곱도 2와 같지 않다")가 독립적임을 보여준다. 마찬가지로, $\mathbb{Z}[X, Y, Z]/(XZ - Y^2)$ 에 대한 분석은 $\N$ 에서 참인 인수분해에 대한 일부 진술의 독립성을 보여준다. $\mathsf{PA}^-$ 이 숫자 2에 대해 검증하지 않는 소수성의 $\mathsf{PA}$ 특성화가 있다.

다른 방향으로, $\mathsf{PA}^-$ 의 모든 모델에서 순서화된 환을 구성할 수 있으며, 이는 순서와 관련하여 음수인 원소를 가지며, 1이 0을 덮는다는 점에서 여전히 이산적이다. 이를 위해 원래 반환에서 쌍의 동치 클래스를 정의한다. 대략적으로, 환은 이전 구조의 원소의 차이에 해당하며, 초기 환 $\mathbb{Z}$ 이 $\N$ 에서 정의될 수 있는 방식을 일반화한다. 이는 실제로 모든 역원을 추가하고, 전순서는 $\forall x. x \le_\text{pre} 0$ 에서 사소하다.

두 원소 대수의 크기를 넘어, 간단한 반환은 단위로 시작하지 않는다. 이산적으로 정렬되는 것은 단위 사이에서 밀집되어 있는 음수가 아닌 유리수의 반환 $\mathbb{Q}_{\ge 0}$ 에 대한 표준 정렬과 대조된다. 또 다른 예로, $\mathbb{Z}[X]/(2X^2 - 1)$ 은 순서를 매길 수 있지만 이산적으로는 순서를 매길 수 없다.

5. 1. 형식 언어 및 오토마타

클레이니 대수(Kleene algebra)는 멱등적인 덧셈과 몇 가지 추가적인 공리를 가진 스타 반환이며, 형식 언어와 정규 표현식 이론에서 중요하다.^[1] 스타 반환(star semiring)은 때때로 'starsemiring'으로 표기되며, 추가적인 단항 연산자

{}^*

를 가진 반환으로, 다음을 만족한다.^[1]

:

a^* = 1 + a a^* = 1 + a^* a.

^[1]

6. 응용

열대 반환의 $(\max, +)$ 와 $(\min, +)$ 는 이산 사건 시스템의 성능 평가에 자주 사용된다.^[1] 실수는 "비용" 또는 "도착 시간"을 나타내는데, "max" 연산은 모든 사건의 전제 조건이 갖춰질 때까지 기다려야 하므로 최대 시간이 걸리는 것을 의미하고, "min" 연산은 가장 좋고 비용이 적은 선택을 할 수 있음을 뜻하며, "+"는 동일한 경로를 따라 값이 누적되는 것을 의미한다.^[1]

이러한 반환의 개념은 최단 경로 문제나 은닉 마르코프 모델에서 최적의 상태 시퀀스를 찾는 문제 등 다양한 분야에 응용된다.^[1]

6. 1. 그래프 이론

최단 경로를 구하는 플로이드-워셜 알고리즘은 (min, +) 대수 연산으로 재구성될 수 있다.^[1] 마찬가지로, 은닉 마르코프 모델에서 관측 시퀀스에 해당하는 가장 확률이 높은 상태 시퀀스를 찾는 비터비 알고리즘도 확률에 대한 (max, ×) 대수 연산으로 공식화될 수 있다.^[1] 이러한 동적 프로그래밍 알고리즘은 큰 수의 항에 대해 각 항을 열거하는 것보다 효율적으로 계산하기 위해 관련 반환의 분배 법칙에 의존한다.^[1]

6. 2. 최적화 문제

열대 반환

(\max, +)

와

(\min, +)

는 이산 사건 시스템의 성능 평가에 자주 사용된다. 실수는 "비용" 또는 "도착 시간"을 나타낸다. "max" 연산은 모든 사건의 전제 조건을 기다려야 하므로 최대 시간이 걸리는 것에 해당하고, "min" 연산은 가장 좋고 비용이 적은 선택을 할 수 있음에 해당하며, "+"는 동일한 경로를 따라 누적되는 것에 해당한다.

최단 경로를 구하는 Floyd-Warshall 알고리즘은

(\min, +)

대수 연산으로 재구성될 수 있다. 마찬가지로, 은닉 마르코프 모델에서 관측 시퀀스에 해당하는 가장 확률이 높은 상태 시퀀스를 찾는 비터비 알고리즘도 확률에 대한

(\max, \times)

대수 연산으로 공식화될 수 있다. 이러한 동적 프로그래밍 알고리즘은 관련된 반환의 분배 법칙에 의존하여, 각 항을 열거하는 것보다 효율적으로 계산한다.^[1]

6. 3. 확률적 모델링

은닉 마르코프 모델에서 관측되는 사건열에 대응하는 그럴듯한 상태열을 구하는 비터비 알고리즘은 확률상의 맥스타임즈 대수 상의 계산으로 귀착된다.^[1] 이러한 동적 계획법 알고리즘은 부수하는 반환의 분배성에 의존하여, 매우 방대한 수의 항을 가진 양에 대한 계산을 효율적으로 수행한다.^[1]

7. 일반화

반환은 덧셈과 곱셈 연산을 가지는 대수 구조로, 여러 방식으로 일반화될 수 있다.

순서 이론에서 반환에 엄격한 순서가 주어지고, 1이 양수이고 0을 덮는 경우(즉, 0과 1 사이에 다른 원소가 없는 경우) 이 순서를 이산적이라고 한다. 가환적이고 이산적으로 정렬된 반환의 이론은 ${\mathsf {PA}}^-$ 로 표기하며, 자연수의 모델 $\N$ 을 초기 세그먼트로 가진다. 괴델의 불완전성 정리와 타르스키의 무정의성 정리가 ${\mathsf {PA}}^-$ 에 적용된다.

${\mathsf {PA}}^-$ 는 $\N$ 에 대해 참인 모든 $\Sigma_1$ -문장을 증명하지만, 이 복잡성을 넘어서면 독립적인 명제들이 존재한다. 예를 들어, "모든 숫자가 $2q$ 또는 $2q+1$ 형태이다"(홀수 또는 짝수)라는 명제는 ${\mathsf {PA}}^-$ 에서 독립적이다. 또한, "어떤 유리수 제곱도 $2$ 와 같지 않다"라는 명제도 독립적이다.

곱셈 항등원의 존재를 요구하지 않는 헤미링(hemiring)과 덧셈의 가환성과 분배 법칙을 모두 가정하지 않는 근반환(near-ring)이 있다. 순서수는 근환을 이룬다.

범주론에서, 반환 범주(2-rig)는 환의 연산과 유사한 함자 연산을 가진 범주이다. 집합의 범주는 반환 범주의 예시이다.

7. 1. 헤미링 (유사 반환)

곱셈 항등원의 존재를 요구하지 않아 곱셈이 반군이 되도록 하며, 모노이드가 되지 않는 반환의 일반화된 형태를 hemiring|헤미링^영어 또는 사전 반환이라고 한다. 왼쪽 사전 반환은 오른쪽 분배성을 요구하지 않으며, (또는 왼쪽 분배성을 요구하지 않는 오른쪽 사전 반환도 있다).^[1]

7. 2. 근반환 (Near-ring)

반환의 정의에서 덧셈의 가환성과 오른쪽 분배 법칙을 모두 가정에서 제외하면 근반환(near-ring)의 개념을 얻을 수 있다.^[1] 순서수는 근반환을 이룬다.^[1]

7. 3. 반환 범주 (2-rig)

범주론에서 '''반환 범주'''(2-rig^영어)는 반환 연산과 유사하게 대응하는 함자 연산을 갖춘 범주이다. "기수 전체가 반환을 이룬다"는 것을 범주화하여 "집합의 범주 (또는 더 일반적으로 임의의 토포스)가 반환 범주를 이룬다"는 것을 말할 수 있다.^[4]

8. 집합 반환

'''집합 반환'''(semiring of sets) 또는 단순히 '''반환'''은 공집합이 아닌 집합족 ''S''가 다음 세 가지 조건을 만족하는 경우를 말한다.

# ∅ ∈ ''S''

# ''E'' ∈ ''S'' 이고 ''F'' ∈ ''S''이면, ''E'' ∩ ''F'' ∈ ''S''

# ''E'' ∈ ''S'' 이고 ''F'' ∈ ''S''이면, 상호소 집합인 유한 수열 ''C''_''i'' ∈ ''S'' (''i'' = 1, …, ''n'')이 존재하여, $E \smallsetminus F = \bigcup_{i=1}^n C_i$ 를 만족한다.

집합 반환은 측도론에서 사용된다. 예를 들어 실수의 모든 반개구간 형태로 구성된 집합족이 집합 반환에 해당한다.

참조

_[1] 서적 Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16–20, 1990, Proceedings Springer-Verlag
_[2] 서적 Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement Springer-Verlag
_[3] 서적 Surveys in Contemporary Mathematics Cambridge University Press
_[4] 서적 Berstel & Perrin (1985)
_[5] 웹사이트 Caratheodory's Extension http://www.probabili[...] Noel Vaillant

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com