Cartesian product

Original article: w:Cartesian product

"Cartesian square" redirects here. For Cartesian squares in category theory, see Cartesian square (category theory).

Cartesian product $\scriptstyle A\times B$ of the sets $\scriptstyle A=\{x,y,z\}$ and $\scriptstyle B=\{1,2,3\}$

수학(mathematics), 구체적으로 집합 이론(set theory)에서, 두 집합(sets) A와 B의 데카르트 곱(Cartesian product)은, A × B으로 표시되며, 모든 순서 쌍(ordered pair) (a, b)의 집합이며, 여기서 a는 A 안에 있고 b는 B 안에 있습니다. 집합-구성 표기법(set-builder notation)의 관점에서, 즉

$A\times B=\{\,(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\,\}.$

테이블은 행의 집합과 열의 집합의 데카르트 곱을 취함으로써 생성될 수 있습니다. 만약 데카르트 곱 행 × 열이 취해지면, 테이블의 셀은 형식 (행 값, 열 값)의 순서 쌍을 포함합니다.

우리는 n 집합의 데카르트 곱을 비슷하게 정의할 수 있으며, 역시 n-겹 데카르트 곱(n-fold Cartesian product)이라고 알려져 있으며, 이것은 n-차원 배열로써 표현될 수 있습니다. 여기서 각 원소는 n-튜플(tuple)입니다. 순서쌍은 2-튜플 또는 커플(2-tuple or couple)입니다. 보다 일반적으로 여전히, 우리는 집합의 인덱스 가족(indexed family)의 데카르트 곱을 정의할 수 있습니다.

데카르트 곱은 르네 데카르트(René Descartes)의 이름을 따서 지어졌으며, 해석 기하학(analytic geometry)의 그의 공식이 그 개념을 만들어 냈으며, 이것은 직접 곱(direct product)의 관점에서 나아가서 일반화됩니다.

Examples

A deck of cards

Standard 52-card deck

실례가 되는 예제는 표준 52-카드 덱(standard 52-card deck)입니다. 표준 플레잉 카드(standard playing card) 등급 {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2}은 13-원소 집합을 형성합니다. 카드 짝 {♠, ♥, ♦, ♣} 은 4-원소 집합을 형성합니다. 이들 집합의 데카르트 곱은 모든 52 가능한 플레잉 카드에 해당하는 52 순서 쌍(ordered pairs)으로 구성된 52-원소 집합을 반환합니다.

등급 × 짝은 형식 {(A, ♠), (A, ♥), (A, ♦), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}의 집합을 반환합니다.

짝 × 등급은 형식 {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}의 집합을 반환합니다.

이들 두 집합은 구별되며, 심지어 서로소입니다.

A two-dimensional coordinate system

Cartesian coordinates of example points

주요 역사적 예제는 해석적 기하학(analytic geometry)에서 데카르트 평면(Cartesian plane)입니다. 기하학적 모양을 수치적 방법에서 표현하고 모양의 수치적 표현으로부터 수치적 정보를 추출하기 위해, 르네 데카르트(René Descartes)는 평면에서 각 점을 그것의 좌표라고 불리는 한 쌍의 실수(real number)로 할당했습니다. 보통, 그러한 쌍의 첫 번째와 두 번째 성분은 각각 x와 y 좌표라고 불립니다 (그림을 참조하십시오). 모든 그러한 쌍의 집합 (즉, 실수를 나타내는 ℝ을 갖는 데카르트 곱 ℝ×ℝ)이 따라서 평면에서 모든 점의 집합에 할당됩니다.

Most common implementation (set theory)

Main article: Implementation of mathematics in set theory

집합-이론적(set-theoretical) 원리로부터 데카르트 곱의 공식적인 정의는 순서 쌍(ordered pair)의 정의를 따릅니다. 순서 쌍의 가장 공통적인 정의, 쿠라토프스키 정의(Kuratowski definition)는 $(x,y)=\{\{x\},\{x,y\}\}$입니다. 이 정의 아래에서, $(x,y)$는 ${\mathcal {P}}({\mathcal {P}}(X\cup Y))$의 원소이고, $X\times Y$는 해당 집합의 부분-집합이며, 여기서 ${\mathcal {P}}$는 거듭-제곱 집합(power set) 연산자를 나타냅니다. 그러므로, ZFC에서 임의의 두 집합의 데카르트 곱의 존재는 쌍화(pairing), 합집합(union), 거듭-제곱 집합(power set), 및 명세화(specification)의 공리를 따릅니다. 함수(functions)는 보통 관계(relations)의 특수한 경우로 정의되고, 관계는 보통 데카르트 곱의 부분-집합으로 정의되기 때문에, 두-집합 데카르트 곱의 정의는 필연적으로 대부분의 다른 정의보다 우선합니다.

Non-commutativity and non-associativity

A, B, C, 및 D를 집합으로 놓습니다.

데카르트 곱 A × B는 교환적(commutative)이 아닌데,

$A\times B\neq B\times A,$

왜냐하면 순서 쌍(ordered pair)은 다음 조건 중 적어도 하나가 만족되지 않은 한 순서가 뒤바뀌게 되기 때문입니다:

• A는 B와 같습니다, 또는
• A 또는 B가 빈 집합(empty set)입니다.

예를 들어:

A = {1,2}; B = {3,4}

A × B = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}

B × A = {3,4} × {1,2} = {(3,1), (3,2), (4,1), (4,2)}

A = B = {1,2}

A × B = B × A = {1,2} × {1,2} = {(1,1), (1,2), (2,1), (2,2)}

A = {1,2}; B = ∅

A × B = {1,2} × ∅ = ∅

B × A = ∅ × {1,2} = ∅

엄격하게 말하자면, 데카르트 곱은 (만약 포함된 집합 중 하나가 빈 것이 아닌 한) 결합적(associative)이 아닙니다.

$(A\times B)\times C\neq A\times (B\times C)$

만약 예를 들어 A = {1}이면, (A × A) × A = { ((1,1),1) } ≠ { (1,(1,1)) } = A × (A × A)입니다.

Intersections, unions, and subsets

Example sets

A={y∈ℝ:1≤y≤4},
B={x∈ℝ:2≤x≤5}, and C={x∈ℝ:4≤x≤7}, demonstrating
A×(B∩C) = (A×B)∩(A×C),
A×(B∪C) = (A×B)∪(A×C), and

A×(B \ C) = (A×B) \ (A×C)

Example sets

A={x∈ℝ:2≤x≤5}, B={x∈ℝ:3≤x≤7},
C={y∈ℝ:1≤y≤3}, D={y∈ℝ:2≤y≤4}, demonstrating

(A∩B)×(C∩D) = (A×C)∩(B×D).

(A∪B)×(C∪D) ≠ (A×C)∪(B×D) can be seen from the same example.

데카르트 곱은 교집합(intersections)에 관해 잘 작동합니다 (중간 그림을 참조하십시오).

$(A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)$

대부분의 경우에서, 위의 명제는 만약 우리가 교집합을 합집합(union)으로 대체하면, 참이 아닙니다 (맨 오른쪽 그림 참조하십시오).

$(A\cup B)\times (C\cup D)\neq (A\times C)\cup (B\times D)$

사실, 우리는 다음임을 가집니다:

$(A\times C)\cup (B\times D)=[(A\setminus B)\times C]\cup [(A\cap B)\times (C\cup D)]\cup [(B\setminus A)\times D]$

집합 차이에 대해 우리는 역시 다음 항등식을 가집니다:

$(A\times C)\setminus (B\times D)=[A\times (C\setminus D)]\cup [(A\setminus B)\times C]$

다음은 다른 연산자와 함께 분배성을 보여주는 몇 가지 규칙입니다 (맨 왼쪽 그림 참조하십시오):

$A\times (B\cap C)=(A\times B)\cap (A\times C),$

$A\times (B\cup C)=(A\times B)\cup (A\times C),$

$A\times (B\setminus C)=(A\times B)\setminus (A\times C),$

$(A\times B)^{\complement }=(A^{\complement }\times B^{\complement })\cup (A^{\complement }\times B)\cup (A\times B^{\complement }),$

여기서 $A^{\complement }$는 A의 절대적인 여집합(absolute complement)을 나타냅니다.

부분-집합(subset)과 관련된 다른 속성은 다음입니다:

${\text{if }}A\subseteq B{\text{ then }}A\times C\subseteq B\times C,$

${\text{if both }}A,B\neq \emptyset {\text{ then }}A\times B\subseteq C\times D\iff A\subseteq C{\text{ and }}B\subseteq D.$

Cardinality

See also: Cardinal arithmetic

집합의 카디널리티(cardinality)는 집합의 원소의 숫자입니다. 예를 들어, 두 집합: A = {a, b}와 B = {5, 6}를 정의합니다. 집합 A와 집합 B 둘 다는 각각 두 원소로 구성됩니다. 그들의 데카르트 곱은, A × B로 쓰이며, 다음 원소를 가지는 새로운 집합의 결과를 낳습니다:

A × B = {(a,5), (a,6), (b,5), (b,6)}.

A의 각 원소가 B의 각 원소와 쌍을 이룹니다. 각 쌍은 출력 집합의 한 원소를 만듭니다. 결과 집합의 각 원소에 있는 값의 숫자는 그의 데카르트 곱이 취해지게 되는 집합의 숫자와 같습니다; 이 경우에서 2입니다. 출력 집합의 카디널리티는 모든 입력 집합의 카디널리티의 곱과 같습니다. 즉,

|A × B| = |A| · |B|.

이 경우에서, |A × B| = 4

비슷하게,

|A × B × C| = |A| · |B| · |C|

그리고 이런 식으로 계속됩니다.

집합 A × B는 만약 A 또는 B 중 하나가 무한대이고 다른 집합이 빈 집합이 아니면 무한대(infinite)입니다.

Cartesian products of several sets

n-ary Cartesian product

데카르트 곱은 집합 X₁, ..., X_n에 걸쳐 n-항 데카르트 곱을 n-튜플(n-tuple)의 다음 집합으로 일반화될 수 있습니다:

$X_{1}\times \cdots \times X_{n}=\{(x_{1},\ldots ,x_{n})\mid x_{i}\in X_{i}\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}.$

만약 튜플이 중첩된 순서 쌍(nested ordered pairs)으로 정의되면, 그것은 (X₁ × ... × X_n−1) × X_n으로 식별될 수 있습니다. 만약 튜플이 i에서 그것의 값을 튜플의 i번째 요소로 취하는 {1, 2, ..., n} 에 대한 함수로 정의되면, 데카르트 곱 X₁×...×X_n은 다음 함수의 집합입니다:

$\{x:\{1,\ldots ,n\}\to X_{1}\cup \ldots \cup X_{n}\ |\ x(i)\in X_{i}\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}.$

n-ary Cartesian power

집합 X의 데카르트 제곱은 데카르트 곱 X² = X × X입니다. 예제는 2-차원 평면(plane) R² = R × R이며, 여기서 R은 실수(real number)의 집합입니다: R²은 모든 점 (x,y)의 집합이며, 여기서 x와 y는 실수입니다 (데카르트 좌표 시스템(Cartesian coordinate system)을 참조하십시오).

집합 x'의 n-항 데카르트 거듭-제곱은 다음으로 정의될 수 있습니다:

$X^{n}=\underbrace {X\times X\times \cdots \times X} _{n}=\{(x_{1},\ldots ,x_{n})\ |\ x_{i}\in X\ {\text{for every}}\ i\in \{1,\ldots ,n\}\}.$

이것의 예제는 R³ = R × R × R이며, 여기서 R은 다시 실수의 집합이고, 보다 일반적으로 Rⁿ입니다.

집합 X의 n-항 데카르트 거듭제곱은 n-원소 집합에서 X로의 함수의 공간에 동형적(isomorphic)입니다. 특수한 경우로써, X의 0-항 데카르트 거듭제곱은 한원소 집합(singleton set)으로 취할 수 있고, 코도메인(codomain) X를 갖는 빈 함수(empty function)에 해당합니다.

Infinite Cartesian products

임의적으로 (무한대(infinite)가 가능한) 집합의 인덱스된 가족(indexed family)의 데카르트 곱을 정의할 수 있습니다. 만약 I가 임의의 인덱스 집합(index set)이고, $\{X_{i}\}_{i\in I}$이 I에 의해 인덱스된 집합의 가족이면, $\{X_{i}\}_{i\in I}$ 에서 집합의 데카르트 곱은 다음으로 정의됩니다:

$\prod _{i\in I}X_{i}=\left\{\left.f:I\to \bigcup _{i\in I}X_{i}\ \right|\ (\forall i)(f(i)\in X_{i})\right\},$

즉, 특정 인덱스 i에서 함수 값이 X_i의 원소임을 만족하는 인덱스 집합(index set) 위에 정의된 모든 함수의 집합입니다. 심지어 각각의 X_i가 비-빈일지라도, 데카르트 곱은 만약 선택의 공리(axiom of choice) (이것은 모든 각 곱이 비-빈인 명제와 동일함)가 가정되지 않으면, 빈 것일 수 있습니다.

I에서 각 j에 대해, 다음 함수는

$\pi _{j}:\prod _{i\in I}X_{i}\to X_{j},$

j번째 투영 맵(projection map)이라고 불리는 $\pi _{j}(f)=f(j)$에 의해 정의됩니다.

데카르트 거듭제곱은 데카르트 곱이며 여기서 모든 인수 X_i는 같은 집합 X입니다. 이 경우에서,

$\prod _{i\in I}X_{i}=\prod _{i\in I}X$

는 I에서 X로의 모든 함수의 집합이고, 자주 X^I로 표시됩니다. 이 경우는 세는-숫자 지수화(cardinal exponentiation) 연구에서 중요합니다. 중요한 특수한 경우는 인덱스 집합이 $\mathbb {N}$, 자연수(natural numbers)일 때입니다: 이 데카르트 곱은 해당하는 집합 X_i에서 i번째 항을 갖는 모든 무한 수열의 집합입니다. 예를 들어, 다음의 각 원소는

$\prod _{n=1}^{\infty }\mathbb {R} =\mathbb {R} \times \mathbb {R} \times \cdots$

셀-수-있게 무한한 실수 성분을 갖는 벡터(vector)로 시각화될 수 있습니다. 이 집합은 자주 $\mathbb {R} ^{\omega }$, 또는 $\mathbb {R} ^{\mathbb {N} }$으로 표시됩니다.

Other forms

Abbreviated form

만약 여러 집합이, 예를 들어 X₁, X₂, X₃, …, 함께 곱해지면, 일부 저자는 데카르트 곱을 단순히 ×X_i로 축약하기로 선택합니다.

Cartesian product of functions

만약 f가 A에서 B로의 함수이고 g가 X에서 Y로의 함수이면, 그들의 데카르트 곱 f × g은 다음과 함께 A × X에서 B × Y로의 함수입니다:

$(f\times g)(a,x)=(f(a),g(x)).$

이것은 튜플(tuple)과 무한한 함수의 모음으로 확장될 수 있습니다. 이것은 집합으로 고려된 함수의 표준 데카르트 곱과 다릅니다.

Cylinder

$A$를 함수로 놓고 $B\subseteq A$로 놓습니다. 그런-다음 $A$에 관한 $B$의 실린더(cylinder)는 $B$와 $A$의 데카르트 곱 $B\times A$입니다.

통상적으로, $A$가 문맥의 전체-집합으로 고려되고 제외됩니다. 예를 들어, 만약 $B$가 자연수 $\mathbb {N}$의 부분-집합이면, $B$의 실린더는 $B\times \mathbb {N}$입니다.

Definitions outside set theory

Category theory

비록 데카르트 곱이 전통적으로 집합으로 적용되지만, 카테고리 이론(category theory)은 수학적 구조의 곱(product)의 보다 일반적인 해석을 제공합니다. 이것은 카테고리 이론에서 데카르트 제곱(Cartesian square)의 개념과, 비록 관련이 있을지라도, 구별되며, 이것은 올 곱(fiber product)의 일반화입니다.

지수화(Exponentiation)는 데카르트 곱의 오른쪽 인접(right adjoint)입니다; 따라서 데카르트 곱 (및 최종 대상(final object))을 갖는 임의의 카테고리는 데카르트 닫힌 카테고리(Cartesian closed category)입니다.

Graph theory

그래프 이론(graph theory)에서, 두 그래프 G와 H의 데카르트 곱은 그의 꼭짓점(vertex) 집합이 (보통) 데카르트 곱 V(G) × V(H)이고 두 꼭짓점 (u,v) 및 (u′,v′)이 G × H에서 인접하는 것과 u = u′와 v가 H에서 v′와 인접함, 또는 v = v′와 u는 G에서 u′와 인접하는 것이 필요충분 조건을 만족하는 G × H에 의해 표시되는 그래프입니다. 그래프의 데카르트 곱은 카테고리 이론의 의미에서 곱(product)이 아닙니다. 대신에, 카테고리의 곱은 그래프의 텐서 곱(tensor product of graphs)으로 알려져 있습니다.

See also

• Binary relation
• Concatenation of sets of strings
• Coproduct
• Empty product
• Euclidean space
• Exponential object
• Finitary relation
• Join (SQL) § Cross join
• Orders on the Cartesian product of totally ordered sets
• Axiom of power set (to prove the existence of the Cartesian product)
• Product (category theory)
• Product topology
• Product type
• Ultraproduct

External links

• Cartesian Product at ProvenMath
• "Direct product", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• How to find the Cartesian Product, Education Portal Academy