Set-builder notation

$\{n\in \mathbb {Z} \mid (\exists k\in \mathbb {Z} )[n=2k]\}$

The set of all even integers,
expressed in set-builder notation.

집합 이론(set theory)과 논리(logic), 수학(mathematics), 및 컴퓨터 과학(computer science)의 응용에서, 집합-구성 표기법(set-builder notation:조건 제시법)은 그것의 원소(elements)를 열거하거나, 그것의 구성원이 반드시 만족시켜야 하는 속성을 말함으로써 집합(set)을 설명하는 데 수학 표기법(mathematical notation)입니다.^[1]

속성에 의한 집합을 정의하는 것은 역시 집합 이해(set comprehension), 집합 추상화(set abstraction), 또는 집합의 내연(intension)을 정의하는 것으로 알려져 있습니다.

Sets defined by enumeration

집합(set)은 다음 두 예제와 같이 중괄호 사이에 모든 원소를 열거함으로써 직접적으로 설명될 수 있습니다:

$\{7,3,15,31\}$ 는 네 숫자 3, 7, 15, 및 31을 포함하고 나머지 어떤 것도 포함하지 않는 집합입니다.
$\{a,c,b\}=\{a,b,c\}$ 는 $a$ , $b$ , 및 $c$ 를 포함하고 나머지 어떤 것도 포함하지 않는 집합니다 (집합의 원소 사이에 순서는 없습니다).

이것은 때때로 집합을 지정하기 위한 "명단 방법(roster method)"이라고 합니다.^[2]

정규 수열의 원소를 포함하는 집합을 표시하기를 희망할 때, 다음 예제에서 보인 것처럼 생략(ellipses) 표기법이 사용될 수 있습니다:

$\{1,2,3,\ldots ,100\}$ 는 1과 100을 포함하여 그 사이의 정수의 집합입니다.
$\{1,2,3,\ldots \}$ 는 자연수(natural number)의 집합입니다.
$\{\ldots ,-2,-1,0,1,2,\ldots \}=\{0,1,-1,2,-2,\ldots \}$ 는 모든 정수의 집합입니다.

집합의 원소들 사이에는 순서가 없지만 (이것은 마지막 예제의 상등을 설명하고 검증합니다), 생략 표기법과 함께, 우리는 어떤 원소가 집합 안에 있는지를 설명하기 위한 편리한 표기법적 수단으로 생략표 앞 (또는 뒤)에 순서화된 수열을 사용합니다. 수열의 처음 몇 개의 원소가 보이고, 그런-다음 생략표는 수열을 계속하기 위해 가장 간단한 해석을 적용해야 함을 나타냅니다. 생략표의 오른쪽에 종료 값이 표시되지 않으면, 수열은 무경계로 여겨집니다.

일반적으로, $\{1,\dots ,n\}$ 는 $1\leq i\leq n$ 를 만족하는 모든 자연수 $i$ 의 집합을 나타냅니다. $\{1,\dots ,n\}$ 에 대해 또 다른 표기법은 대괄호 표기법 $[n]$ 입니다. 미묘한 특수한 경우는 $n=0$ 이며, 이것에서 $[0]=\{1,\dots ,0\}$ 은 빈 집합(empty set) $\emptyset$ 과 같습니다. 유사하게, $\{a_{1},\dots ,a_{n}\}$ 는 $1\leq i\leq n$ 에 대해 모든 $a_{i}$ 의 집합입니다.

앞의 각 예제에서, 각 집합은 그것의 원소를 열거함으로써 설명됩니다. 모든 집합이 이런 식으로 기술될 수 있는 것은 아니거나, 또는 만약 그것들이 가능하면, 그것들의 열거가 너무 길거나 너무 복잡하여 유용할 수 없습니다. 그러므로, 많은 집합이 해당 원소를 특성화하는 속성에 의해 정의됩니다. 이 특성화는 다음 예제에서 처럼 일반 산문을 사용하여 비공식적으로 수행될 수 있습니다.

$\{$ addresses on Pine Street $\}$ 는 Pine Street의 모든 주소의 집합입니다.

어쨌든, 산문 접근 방식은 정확성이 부족하거나 모호할 수 있습니다. 따라서, 집합-구성 표기법은 다음 섹션에 설명된 대로 정의되는 집합의 원소를 특성화하는 술어와 함께 자주 사용됩니다.

Sets defined by a predicate

집합-구성 표기법은 술어(predicate), 즉, 집합의 원소에 대해 참으로 평가되고, 그렇지 않으면 거짓으로 평가되는 논리 공식에 의해 정의된 집합을 설명하기 위해 사용될 수 있습니다.^[3] 이 형식에서, 집합-구성 표기법은 세 부분: 변수, 콜론 또는 세로 막대 구분 기호, 및 술어을 가집니다. 따라서 구분 기호의 왼쪽에 변수가 있고, 오른쪽에 규칙이 있습니다. 이들 세 부분은 중괄호 안에 포함되어 있습니다:

\{x\mid \Phi (x)\}

또는

\{x:\Phi (x)\}.

수직 막대 (또는 콜론)은 "다음을 만족하는", "다음을 위해", 또는 "다음 속성을 갖는"으로 읽힐 수 있는 분리 기호입니다. 수식 $Φ(x)$ 는 규칙 또는 술어라고 말합니다. 술어가 유지되는 (술어가 참인) x의 모든 값은 정의된 집합에 속합니다. 술어가 유지되지 않는 $x$ 의 모든 값은 그 지합에 속하지 않습니다. 따라서 $\{x\mid \Phi (x)\}$ 는 수식 $Φ$ 를 만족시키는 $x$ 의 모든 값의 집합입니다.^[4] 만약 수식을 만족시키는 $x$ 의 값이 없으면, 그것은 빈 집합(empty set)일 수 있습니다.

Specifying the domain

도메인 $E$ 는 수직 막대의 왼쪽 편에 나타날 수 있습니다:^[5]

\{x\in E\mid \Phi (x)\},

또는 그것을 술어에 인접함으로써:

\{x\mid x\in E{\text{ and }}\Phi (x)\}\quad {\text{or}}\quad \{x\mid x\in E\land \Phi (x)\}.

여기서 ∈ 기호는 집합 구성원(set membership)을 나태내고, 반면에 $\land$ 기호는 논리곱(logical conjunction)으로 알려진 논리적 "그리고" 연산자입니다. 이 표기법은 술어가 참인 일부 주어진 집합 $E$ 에 속하는 $x$ 의 모든 값의 집합을 나타냅니다 (아래의 "집합 존재 공리"를 참조하십시오). 만약 $\Phi (x)$ 가 논리곱 $\Phi _{1}(x)\land \Phi _{2}(x)$ 이면, $\{x\in E\mid \Phi (x)\}$ 는 때때로 기호 $\land$ 대신에 콤마를 사용하여 $\{x\in E\mid \Phi _{1}(x),\Phi _{2}(x)\}$ 로 쓰입니다.

일반적으로, 담론의 도메인 정의없이 집합을 고려하는 것은 좋은 생각이 아닌데, 왜냐하면 이것은 술어가 참인 존재할 수 있는 모든 가능한 것들의 부분집합(subset)을 나타내기 때문입니다. 이것은 쉽게 모순과 역설로 이어질 수 있습니다. 예를 들어, 러셀의 역설(Russell's paradox)은 표현 $\{x~|~x\not \in x\}$ 은, 비록 집합 구성 표현으로 잘 형성된 것처럼 보이지만, 모순을 생성하지 않고는 집합을 정의할 수 없음을 보여줍니다.^[6]

집합 E가 무낵에서 명확한 경우에서, 그것은 명시적으로 지정되지 않을 수 있습니다. 문헌에서 저자에 의해 사전에 도메인을 명시하고, 그런-다음 집합-구성 표기법으로 지정하지 않는 것은 공통적입니다. 예를 들어, 저자는 "달리 명시되지 않은 한, 변수는 자연수로 취급됩니다."와 같은 말을 할 수 있습니다. 도메인이 가정될 수 있는 덜 형식적인 문맥에서 기록된 언급이 종종 필요하지 않습니다.

Examples

다음 예제는 술어를 통해 집합-구성 표기법에 의해 정의된 특정 집합을 묘사합니다. 각 경우에서, 그 도메인은 수직 막대의 왼쪽에 지정되고, 반면에 규칙은 오른쪽에 지정됩니다.

$\{x\in \mathbb {R} \mid x>0\}$ 는 모든 엄격하게 양의(positive) 실수(real number)의 집합이며, 구간 표기법에서 $(0,\infty )$ 로 쓸 수 있습니다.
$\{x\in \mathbb {R} \mid |x|=1\}$ 는 집합 $\{-1,1\}$ 입니다. 이 집합은 역시 $\{x\in \mathbb {R} \mid x^{2}=1\}$ 로 정의될 수 있습니다; 아래의 동등한 술어가 같은 집합을 산출을 참조하십시오.
각 정수 m에 대해, 우리는 $G_{m}=\{x\in \mathbb {Z} \mid x\geq m\}=\{m,m+1,m+2,\ldots \}$ 를 정의할 수 있습니다. 예제로, $G_{3}=\{x\in \mathbb {Z} \mid x\geq 3\}=\{3,4,5,\ldots \}$ 및 $G_{-2}=\{-2,-1,0,\ldots \}$ .
$\{(x,y)\in \mathbb {R} \times \mathbb {R} \mid 0<y<f(x)\}$ 는 주어진 함수(function) f에 대해 y가 0보다 크고 f(x)보다 작음을 만족하는 실수의 쌍의 집합입니다. 여기서 데카르트 곱(cartesian product) $\mathbb {R} \times \mathbb {R}$ 은 실수의 순서쌍의 집합을 나타냅니다.
$\{n\in \mathbb {N} \mid (\exists k)[k\in \mathbb {N} \land n=2k]\}$ 는 모든 짝수(even) 자연수(natural number)의 집합입니다. $\land$ 기호는 "그리고"를 의미하며, 존재적 정량화(existential quantification)로 알려져 있습니다. 따라서 예를 들어, $(\exists x)P(x)$ 는 "P(x)를 만족하는 x가 존재합니다"로 읽습니다.
$\{n\mid (\exists k\in \mathbb {N} )[n=2k]\}$ 는 짝수 자연수의 같은 집합에 대해 표기법적 변종입니다. $n$ 이 자연수임을 지정하는 것이 필요하지 않는데, 왜냐하면 이것은 오른쪽에 공식에 의해 암시됩니다.
$\{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\}$ 는 유리수(rational number); 즉, 두 정수(integer)의 비율로 쓸 수 있는 실수의 집합입니다.

More complex expressions on the left side of the notation

집합-구성 표기법의 확장은 단일 변수 $x$ 를 표현(expression)으로 대체합니다. 따라서 $\{x\mid \Phi (x)\}$ 대신에, 우리는 $\{\Psi (x)\mid \Phi (x)\}$ 를 가질 것이며, 다음으로 읽혀야 합니다:

\{\Psi (x)\mid \Phi (x)\}=\{y\mid \exists (x),y=\Psi (x){\text{ and }}\Phi (x)\}

.

예를 들어:

$\{2n\mid n\in \mathbb {N} \}$ 는, 여기서 $\mathbb {N}$ 는 모든 자연수의 집합이며, 모든 짝수 자연수의 집합입니다.
$\{p/q\mid p,q\in \mathbb {Z} ,q\not =0\}$ 는, 여기서 $\mathbb {Z}$ 는 모든 정수의 집합이며, 모든 유리수의 집합 $\mathbb {Q}$ 입니다.
$\{2t+1\mid t\in \mathbb {Z} \}$ 는 홀수 정수의 집합입니다.
$\{(t,2t+1)\mid t\in \mathbb {Z} \}$ 는 쌍의 집합을 생성하며, 여기서 각 쌍은 정수를 대응하는 홀수 정수로 넣습니다.

역 함수가 명시적으로 말할 수 있을 때, 왼쪽에서 표현은 단순 치환을 통해 제거될 수 있습니다. 예제 집합 $\{2t+1\mid t\in \mathbb {Z} \}$ 을 생각해 보십시오. 치환 $u=2t+1$ 을 만들고, 이것은 $t=(u-1)/2$ 를 말하는 것이며, 그런-다음 다음을 찾기 위해 집합 구성 표기법에서 t를 대체하십시오:

\{2t+1\mid t\in \mathbb {Z} \}=\{u\mid (u-1)/2\in \mathbb {Z} \}.

Equivalent predicates yield equal sets

두 집합이 같은 것과 그것들이 같은 원소를 가지는 것은 필요충분 조건입니다. 집합 구성 표기법에 의해 정의된 집합이 같은 것과 도메인 지정자를 포함하여 그것들의 집합 구성 규칙이 동등한 것은 필요충분 조건입니다. 즉, 다음은

\{x\in A\mid P(x)\}=\{x\in B\mid Q(x)\}

다음과 필요충분 조건입니다:

(\forall t)[(t\in A\land P(t))\Leftrightarrow (t\in B\land Q(t))]

.

그러므로, 집합 구성 표기법에 의해 정의된 두 집합의 상등을 입증하기 위해, 도메인 한정자를 포함하여 그것들의 술어의 동등성을 증명하는 것으로 충분합니다.

예를 들어,

\{x\in \mathbb {R} \mid x^{2}=1\}=\{x\in \mathbb {Q} \mid |x|=1\}

왜냐하면 두 술어가 논리적으로 동등하기 때문입니다:

(x\in \mathbb {R} \land x^{2}=1)\Leftrightarrow (x\in \mathbb {Q} \land |x|=1).

이 동등성은 유지되는데 왜냐하면, 임의의 실수 x에 대해, 우리는 $x^{2}=1$ 를 가지는 것과 x가 $|x|=1$ 를 갖는 유리수인 것은 필요충분 조건이기 때문입니다. 특히, 두 집합은 집합 $\{-1,1\}$ 와 같습니다.

Set existence axiom

체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory)과 같은 많은 형식 집합 이론에서, 집합 구성 표기법은 이론의 형식적 구문의 일부가 아닙니다. 대신에, 만약 $E$ 가 집합이고 $Φ(x)$ 가 집합 이론의 언어에서 형식이면, 그것의 구성원이 $Φ$ 를 만족시키는 정확하게 $E$ 의 원소인 집합 $Y$ 가 있다고 말하는 집합 존재 공리 체계가 있습니다:

(\forall E)(\exists Y)(\forall x)[x\in Y\Leftrightarrow x\in E\land \Phi (x)].

이 공리로부터 얻어진 집합 $Y$ 는 집합 구성 표기법에서 $\{x\in E\mid \Phi (x)\}$ 로 묘사된 정확하게 그 집합입니다.

Parallels in programming languages

여러 프로그래밍 언어 (특히 Python과 Haskell)에서 사용할 수 있는 유사한 표기법은 하나 이상의 목록(lists)에 걸쳐 맵(map)과 필터(filter) 연산을 결합하는 목록 포함(list comprehension)입니다.

파이썬에서, 집합-구성의 중괄호는 대괄호, 괄호 또는 중괄호로 대체되어, 각각 목록, 생성기(generator), 및 집합 개체를 제공합니다. 파이썬은 영어-기반 구문을 사용합니다. Haskell은 집합-구성의 중괄호를 대괄호로 대체하고 표준 집합-구성 수직 막대를 포함한 기호를 사용합니다.

같은 것은 "for" 키워드는 "yield" 키워드를 사용하여 산출된 변수의 목록을 반환하는 Sequence Comprehensions를 사용하여 Scala에서 성취될 수 있습니다.^[7]

일부 프로그래밍 언어에서 다음 집합-구성 표기법 예제를 생각해 보십시오:

	Example 1	Example 2
Set-builder	$\{l\ \|\ l\in L\}$	$\{(k,x)\ \|\ k\in K\wedge x\in X\wedge P(x)\}$
Python	{l for l in L}	{(k, x) for k in K for x in X if P(x)}
Haskell	[l \| l <- ls]	[(k, x) \| k <- ks, x <- xs, p x]
Scala	for (l <- L) yield l	for (k <- K; x <- X if P(x)) yield (k,x)
C#	from l in L select l	from k in K from x in X where P(x) select (k,x)
SQL	SELECT l FROM L_set	SELECT k, x FROM K_set, X_set WHERE P(x)

집합 구성 표기법과 목록 포함 표기법은 모두 모나드 포함(monad comprehensions)이라고 하는 보다 일반적인 표기법의 인스턴스로, 영 원소(zero element)를 갖는 임의의 모나드(monad)에 걸쳐 맵/필터-계열 연산을 허용합니다.

Notes

^ Rosen, Kenneth (2007). Discrete Mathematics and its Applications (6th ed.). New York, NY: McGraw-Hill. pp. 111–112. ISBN 978-0-07-288008-3.
^ Richard Aufmann, Vernon C. Barker, and Joanne Lockwood, 2007, Intermediate Algebra with Applications, Brooks Cole, p. 6.
^ Michael J Cullinan, 2012, A Transition to Mathematics with Proofs, Jones & Bartlett, pp. 44ff.
^ Weisstein, Eric W. "Set". mathworld.wolfram.com. Retrieved 2020-08-20.
^ "Set-Builder Notation". mathsisfun.com. Retrieved 2020-08-20.
^ Irvine, Andrew David; Deutsch, Harry (9 October 2016) [1995]. "Russell's Paradox". Stanford Encyclopedia of Philosophy. Retrieved 6 August 2017.
^ "Sequence Comprehensions". Scala. Retrieved 6 August 2017.

[1] Rosen, Kenneth (2007). Discrete Mathematics and its Applications (6th ed.). New York, NY: McGraw-Hill. pp. 111–112. ISBN 978-0-07-288008-3.

[2] Richard Aufmann, Vernon C. Barker, and Joanne Lockwood, 2007, Intermediate Algebra with Applications, Brooks Cole, p. 6.

[3] Michael J Cullinan, 2012, A Transition to Mathematics with Proofs, Jones & Bartlett, pp. 44ff.

[4] Weisstein, Eric W. "Set". mathworld.wolfram.com. Retrieved 2020-08-20.

[5] "Set-Builder Notation". mathsisfun.com. Retrieved 2020-08-20.

[6] Irvine, Andrew David; Deutsch, Harry (9 October 2016) [1995]. "Russell's Paradox". Stanford Encyclopedia of Philosophy. Retrieved 6 August 2017.

[7] "Sequence Comprehensions". Scala. Retrieved 6 August 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]