Finitary relation

Original article: w:Finitary relation

수학(mathematics)에서, 집합 $X_{1},\cdots ,X_{n}$에 걸쳐 유한항 관계(finitary relation)는 데카르트 곱 $X_{1}\times \cdots \times X_{n}$의 부분집합입니다; 즉, 그것은 $X_{i}$의 원소 $x_{i}$로 구성된 $n$-튜플 $(x_{1},\cdots ,x_{n})$의 집합입니다. 전형적으로, 그 관계는 $n$-튜플의 원소 사이의 가능한 연결을 설명합니다. 예를 들어, "$x$는 $y$와 $z$로 나눌 수 있습니다"라는 관계는 각각 $x$, $y$, 및 $z$로 치환될 때 문장을 참으로 만듦을 만족하는 3-튜플의 집합으로 구성됩니다.

관계에서 "자리(places)"의 개수를 제공하는 비-음의 정수 $n$은 관계의 애리티(arity), adicity, 또는 degree라고 불립니다. $n$ "자리"를 갖는 관계는 $n$-항 관계(n-ary relation), $n$-진수 관계(n-adic relation) 또는 차수 $n$의 관계(relation of degree n)로 다양하게 불립니다. 유한한 개수의 자리를 갖는 관계는 유한항 관계(finitary relations) (또는 문맥이 명확하면 간단히 관계)라고 불립니다. 무한 수열(infinite sequences)을 갖는 무한항 관계(infinitary relations)로 개념을 일반화하는 것도 가능합니다.

집합 $X_{1},\cdots ,X_{n}$에 걸쳐 $n$-항 관계는 $X_{1}\times \cdots \times X_{n}$의 거듭제곱 집합(power set)의 원소입니다.

0-항 관계는 오직 두 개의 원소를 셉니다: 하나는 항상 유지된다는 것이고, 다른 하나는 결코 유지되지 않는다는 것입니다. 이것은 하나의 0-튜플, 빈 튜플 ()만 있기 때문입니다. 그것들은 때때로 귀납법(induction) 논증의 기본 경우를 구성하는 데 유용합니다.

단항 관계는 일부 속성 (예를 들어, 노벨상을 수상했었다는 속성)을 갖는 구성원의 모음 (예를 들어, 노벨상 수상자의 모음)으로 볼 수 있습니다.

이항 관계(Binary relations)는 유한항 관계의 가장 공통적으로 연구된 형태입니다. $X_{1}=X_{2}$일 때 그것은 동종 관계(homogeneous relation)라고 불립니다. 예를 들면 다음이 있습니다:

• 상등(Equality)과 부등식(inequality), "5 < 12"와 같은 명제에서 = 및 <와 같은 기호에 의해 표시됩니다. 또는
• 나눔가능성(Divisibility), "13|143"와 같은 명제에서 기호 | 에 의해 표시됩니다.

그렇지 않으면 그것은 이종 관계(heterogeneous relation)입니다. 예를 들면 다음이 있습니다:

• 집합 구성원(Set membership), "1 ∈ N"와 같은 명제에서 기호 ∈에 의해 표시됩니다.

Example

다음에 의해 정의된, 사람들 P = {Alice, Bob, Charles, Denise}의 집합에 걸쳐 삼항 관계 R "x는 y가 z를 좋아한다고 생각합니다"를 생각해 보십시오:

R = {(Alice, Bob, Denise), (Charles, Alice, Bob), (Charles, Charles, Alice), (Denise, Denise, Denise)}.

R은 다음 테이블에 의해 동등하게 표현될 수 있습니다:

Relation R "x thinks that y likes z"

P	P	P
Alice	Bob	Denise
Charles	Alice	Bob
Charles	Charles	Alice
Denise	Denise	Denise

여기서, 각 행은 R의 세-쌍을 나타냅니다. 즉, "x는 y가 z를 좋아한다고 생각합니다" 형식의 명제를 만듭니다. 예를 들어, 첫 번째 행은 "Alice는 Bob이 Denise를 좋아한다고 생각합니다"라고 명시되어 있습니다. 모든 행은 구별됩니다. 행의 순서는 중요하지 않지만 열의 순서는 중요합니다.

위의 테이블은 역시 관계형 데이터베이스(relational database)의 간단한 예이기도 하며, 관계 대수(relational algebra)에 뿌리를 둔 이론과 데이터 관리에서 응용을 갖는 데이터베이스입니다. 컴퓨터 과학자, 논리학자, 및 수학자들은, 어쨌든, 일반 관계가 무엇이며 무엇으로 구성되는지에 대해 서로 다른 개념을 갖는 경향이 있습니다. 예를 들어, 데이터베이스는 정의에 의해 유한한 경험적 데이터를 다루도록 설계되었지만, 수학에서는 무한한 에러티 (즉, 무한항 관계)도 고려됩니다.

Definitions

마음 속에서 함께 보는 두 대상, 성질, 클래스, 또는 속성이 어떤 연결 아래에서 보일 때, 해당 연결은 관계라고 불립니다.

— Augustus De Morgan

수학에서 접하는 관계의 첫 번째 정의는 다음과 같습니다:

정의 1

집합 $X_{1},\cdots ,X_{n}$에 걸쳐 $n$-항 관계 $R$은 데카르트 곱 $X_{1}\times \cdots \times X_{n}$의 부분집합입니다.

관계의 두 번째 정의는 수학에서 공통적인 관용구의 사용을 만들며, 이런저런 수학적 대상이 $n$ 원소를 갖는 수학적 대상의 지정에 의해 결정됨을 보장하기 위해 "이런저런 것은 $n$-튜플"이라고 규정합니다. $n$ 집합에 걸쳐 관계 $R$의 경우에서, 지정하기 위해 $n+1$ 항목, 즉, $n$ 집합 더하기 그것들의 데카르트 곱의 부분집합이 있습니다. 관용구에서, 이것은 $R$이 $n+1$-튜플임을 말함으로써 표현됩니다.

정의 2

집합 $X_{1},\cdots ,X_{n}$에 걸쳐 $n$-항 관계 $R$은 $n+1$-튜플 $(X_{1},\cdots ,X_{n},G)$이며, 여기서 $G$는 $R$의 그래프라고 불리는 데카르트 곱 $X_{1}\times \cdots \times X_{n}$의 부분집합입니다.

원칙적으로, 현재 응용에 가장 적합한 정의가 그 목적을 위해 선택되고, 두 정의 사이를 구별하는 것이 필요하게 되면, 두 번째 정의를 만족시키는 엔터티는 삽입된 관계 또는 포함된 관계라고 불릴 수 있습니다.

두 명제 (첫 번째 정의 아래에서) $(x_{1},\cdots ,x_{n})\in R$와 (두 번째 정의 아래에서) $(x_{1},\cdots ,x_{n})\in G$는 "$x_{1},\cdots ,x_{n}$은 $R$-관계되었다"라고 읽고 접두 표기법(prefix notation)을 사용하여 $Rx_{1}\cdots x_{n}$에 의해 표시되고 후위 표기법(postfix notation)을 사용하여 $x_{1}\cdots x_{n}R$에 의해 표시됩니다. $R$이 이항 관계인 경우에서, 그들 명제는 중위 표기법(infix notation)을 사용하여 $x_{1}Rx_{2}$에 의해 표시됩니다.

두 정의 중 하나에 다음 고려 사항이 적용됩니다:

• 집합 $X_{i}$는 $R$의 $i$번째 도메인이라고 불립니다. 첫 번째 정의 아래에서, 관계는 주어진 도메인의 수열을 고유하게 결정하지 않습니다. $R$이 이항 관계인 경우에서, $X_{1}$은 역시 단순히 $R$의 도메인(domain) 또는 출발의 집합이라고도 불리고 $X_{2}$는 $R$의 코도메인(codomain) 또는 목적지 집합이라고도 불립니다.
• $X_{i}$의 원소가 관계이면, $X_{i}$는 $R$의 비-단순 도메인(nonsimple domain)이라고 불립니다.
• $Rx_{1}\cdots x_{i-1}x_{i}x_{i+1}\cdots x_{n}\;$을 만족하는 $(x_{1},\cdots ,x_{i-1},x_{i+1},\cdots ,x_{n})\in X_{1}\times \cdots \times X_{x-1}\times X_{i+1}\times \cdots \times X_{n}\;$이 존재하는 ∀x_i ∈ X_i의 집합은 $R$의 $i$번째 정의의 도메인 또는 $i$번째 활동 도메인이라고 불립니다. $R$이 이항 관계인 경우에서, 그것의 첫 번째 정의의 도메인은 간단히 $R$의 정의의 도메인(domain of definition) 또는 활동 도메인이라고 불리고, 그것의 두 번째 정의의 도메인은 역시 $R$의 정의의 코도메인(codomain of definition) 또는 활동 코도메인이라고 불립니다.
• $R$의 $i$번째 정의의 도메인이 $X_{i}$와 같을 때, $R$은 $X_{i}$ 위에 전체(total)라고 말합니다. $R$이 이항 관계인 경우에서, $R$은 $X_{1}$ 위에 전체일 때, 그것은 왼쪽-전체(left-total) 또는 직렬(serial)이라고도 말하고, $R$이 $X_{2}$위의 전체일 때, 그것은 오른쪽-전체(right-total) 또는 전사(surjective)라고 말합니다.
• ∀x ∀y ∈ X_i. ∀z ∈ X_j. xR_ij z ∧ yR_ij z ⇒ x = y일 때, 여기서 i ∈ I, j ∈ J, R_ij = π_ij R이고, {I, J}는 {1, …, n}의 분할(partition)이며, $R$은 {X_i}_{i ∈ I}에서 고유하다고 말하고, {X_i}_{i ∈ J}는 $R$의 주요 키(primary key)라고 불립니다. $R$이 이항 관계인 경우에서, $R$은 $\{X_{1}\}$에서 고유할 때, 그것은 왼쪽-고유(left-unique) 또는 단사(injective)라고 말하고, $R$이 $\{X_{2}\}$에서 고유할 때, 그것은 역시 오른쪽-고유(right-unique) 또는 함수형(functional)이라고 말합니다.
• 모든 $X_{i}$가 같은 집합 $X$일 때, $R$을 동종 관계(homogeneous relation)라고 불리는 $X$에 걸쳐 $n$-항 관계로 참조하는 것이 더 간단합니다. 그렇지 않으면, $R$은 이종 관계(heterogeneous relation)라고 불립니다.
• $X_{i}$의 어떤 것이 빈 것일 때, 정의하는 데카르트 곱은 빈 것이고, 도메인의 그러한 수열에 걸쳐 유일한 관계는 빈 관계 $R=\phi$입니다. 따라서 공통적으로 도메인의 모두가 비-빈어어야 한다고 규정되어 있습니다.

부울 도메인(Boolean domain) B를 두-원소 집합, 말하자면, B = {0, 1}으로 놓습니다. 그것의 원소는 전형적으로 0 = false와 1 = true인 논리 값으로 해석될 수 있습니다. χ_R로 표시되는 $R$의 특성 함수(characteristic function)는 부울-값 함수(Boolean-valued function) χ_R: X₁ × ⋯ × X_n → B이며, Rx₁⋯x_n이면 χ_R((x₁, ⋯, x_n)) = 1으로 그렇지 않으면 χ_R((x₁, ⋯, x_n)) = 0으로 표시됩니다.

응용 수학, 컴퓨터 과학(computer science), 및 통계에서, 부울-값 함수를 $n$-항 술어(predicate)로 참조하는 것이 공통적입니다. 형식 논리(formal logic)와 모델 이론(model theory)의 보다 추상적인 관점에서, 관계 $R$은 일부 $n$-항 술어의 많은 가능한 해석(interpretations) 중 하나 역할을 하는 논리적 모델(logical model) 또는 관계형 구조(relational structure)를 구성합니다.

관계는 수학(mathematics)과 논리(logic)의 많은 가지뿐만 아니라 많은 과학 분야에서 발생하기 때문에, 용어에 상당한 차이가 있습니다. 관계형 개념 또는 용어의 집합-이론적(set-theoretic) 확장(extension) 외에도, "관계"라는 용어는 해당 논리적 엔터디, 관계에서 모든 원소에 의해 공유된 의도 또는 추상 속성의 전체성인 논리적 이해(logical comprehension), 또는 그밖에 이들 원소와 의도를 나타내는 기호를 나타내기 위해 사용될 수도 있습니다. 게다가, 후자의 확신의 몇몇 저자들은 (주어진 관계 개념의 집합-이론적 확장을 위한 "관계형 구조"와 같은) 보다 구체적인 의미를 가진 용어를 소개합니다.

History

See also: Algebraic logic § History

논리학자 오거스터스 드 모르간(Augustus De Morgan)은 1860년경에 출판된 연구에서 그것의 현재와 같은 의미로 관계의 개념을 처음으로 분명히 했습니다. 그는 역시 관계 이론에서 첫 번째 형식적 결과를 언급했습니다 (De Morgan and relations, Merrill 1990을 참조하십시오).

Charles Peirce, Gottlob Frege, Georg Cantor, Richard Dedekind, 등은 관계 이론을 발전시켰습니다. 그들의 많은 아이디어, 특히 순서(orders)라고 하는 관계에 대한 아이디어는 버트런드 러셀(Bertrand Russell)이 이들 결과를 자유롭게 사용했던 The Principles of Mathematics (1903)에 요약되어 있습니다.

1970년 Edgar Codd는 데이터베이스에 대한 관계형 모델(relational model)을 제안하여, 데이터베이스 관리 시스템(data base management systems)의 발전을 예견했습니다.

See also

• Incidence structure
• Hypergraph
• Logic of relatives
• Logical matrix
• Partial order
• Predicate (mathematical logic)
• Projection (set theory)
• Reflexive relation
• Relation algebra
• Relational algebra
• Relational model
• Relations (philosophy)

Bibliography

• Codd, Edgar Frank (1990). The Relational Model for Database Management: Version 2 (PDF). Boston: Addison-Wesley. ISBN 978-0201141924.
• Bourbaki, N. (1994) Elements of the History of Mathematics, John Meldrum, trans. Springer-Verlag.
• Carnap, Rudolf (1958) Introduction to Symbolic Logic with Applications. Dover Publications.
• Halmos, P.R. (1960) Naive Set Theory. Princeton NJ: D. Van Nostrand Company.
• Lawvere, F.W., and R. Rosebrugh (2003) Sets for Mathematics, Cambridge Univ. Press.
• Lewis, C.I. (1918) A Survey of Symbolic Logic, Chapter 3: Applications of the Boole—Schröder Algebra, via Internet Archive
• Lucas, J. R. (1999) Conceptual Roots of Mathematics. Routledge.
• Maddux, R.D. (2006) Relation Algebras, vol. 150 in 'Studies in Logic and the Foundations of Mathematics'. Elsevier Science.
• Merrill, Dan D. (1990) Augustus De Morgan and the logic of relations. Kluwer.
• Peirce, C.S. (1870), "Description of a Notation for the Logic of Relatives, Resulting from an Amplification of the Conceptions of Boole's Calculus of Logic", Memoirs of the American Academy of Arts and Sciences 9, 317–78, 1870. Reprinted, Collected Papers CP 3.45–149, Chronological Edition CE 2, 359–429.
• Peirce, C.S. (1984) Writings of Charles S. Peirce: A Chronological Edition, Volume 2, 1867-1871. Peirce Edition Project, eds. Indiana University Press.
• Russell, Bertrand (1903/1938) The Principles of Mathematics, 2nd ed. Cambridge Univ. Press.
• Suppes, Patrick (1960/1972) Axiomatic Set Theory. Dover Publications.
• Tarski, A. (1956/1983) Logic, Semantics, Metamathematics, Papers from 1923 to 1938, J.H. Woodger, trans. 1st edition, Oxford University Press. 2nd edition, J. Corcoran, ed. Indianapolis IN: Hackett Publishing.
• Ulam, S.M. and Bednarek, A.R. (1990), "On the Theory of Relational Structures and Schemata for Parallel Computation", pp. 477–508 in A.R. Bednarek and Françoise Ulam (eds.), Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators, University of California Press, Berkeley, CA.
• Ulam, S.M. (1990) Analogies Between Analogies: The Mathematical Reports of S.M. Ulam and His Los Alamos Collaborators in A.R. Bednarek and Françoise Ulam, eds., University of California Press.
• Roland Fraïssé (2000) [1986] Theory of Relations, North Holland