세트빌더 표기법

세트 이론과 논리, 수학, 컴퓨터 과학에 대한 그것의 응용에서, 세트빌더 표기법은 그 요소들을 열거함으로써 세트를 기술하거나, 그것의 구성원들이 충족시켜야 하는 속성을 명시함으로써 세트를 기술하기 위한 수학적 표기법이다.^[1]

속성별로 집합을 정의하는 것은 집합 이해, 집합 추상화 또는 집합의 억양을 정의하는 것으로도 알려져 있다.

열거에 의해 정의된 집합

집합은 다음 두 가지 예에서와 같이 곱슬 괄호 사이에 있는 모든 요소를 열거하여 직접 설명할 수 있다.

• ${\displaystyle \{}$ ${\displaystyle 7}$,${\displaystyle }$3,${\displaystyle 15,}$ ${\displaystyle 31}$} ${\displaystyle \{7,3,15,31\}}$은(는) 숫자 3, 7, 15, 31의 네 개 숫자를 포함하는 세트인데$$, 다른 것은 아무것도 없다.
• ${\displaystyle \{}$ ${\displaystyle a,}$ ${\displaystyle c,}$ ${\displaystyle b}$ ${\displaystyle \}}$=${\displaystyle }${ ${\displaystyle a,}$ ${\displaystyle b,}$ ${\displaystyle c}$ ${\displaystyle \}}$ ${\displaystyle \{a,c,b\}=\{a,b,c\}}}$은 a, b,c가 들어 있는 세트인데$$, 그 외의 다른 것은 없다(세트 원소 사이에 순서가 없다).

이것은 때때로 세트를 지정하기 위한 "로스터 방식"이라고 불린다.^[2]

정규 시퀀스의 원소를 포함하는 집합을 나타내려고 할 때, 다음 예에서와 같이 타원 표기법을 사용할 수 있다.

• ${\displaystyle \{}$ ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle }$3,${\displaystyle \dots ,}$ ${\displaystyle 100}$ ${\displaystyle \}}$ ${\displaystyle \{1,2,3,\ldots,100\}$은(는) 1에서 100 사이의 정수 집합이다.
• ${\displaystyle \{}$ ${\displaystyle 1}$,${\displaystyle 2}$,${\displaystyle 3}$,${\displaystyle \dots \}}$ ${\displaystyle \{1,2,3,\ldots \}}}$은(는) 자연수의 집합이다.
• ${\displaystyle \{}$ ${\displaystyle \dots ,}$- ${\displaystyle 2}$,${\displaystyle }$- 1, ${\displaystyle 0,}$ 1, ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle \dots \}}$ =${\displaystyle }${ ${\displaystyle 0,1}$,${\displaystyle }$- ${\displaystyle 1}$, ${\displaystyle 2}$,${\displaystyle }$-${\displaystyle 1}$, 2,${\displaystyle \dots \}}${\$displaystyle$\{\$dots,-2,-1,1$,1$,2,\ldots \}=\{0,1,1,2,\dots \}}}}$는 모든 정수의 집합이다.

집합의 요소들 사이에는 순서가 없지만(이것은 마지막 예시의 동일성을 설명하고 검증한다), 우리는 줄임표 표기법과 함께 줄임표 앞(또는 뒤에) 순서 순서를 사용하여 집합에 어떤 요소가 있는지 설명하기 위한 편리한 공칭적 수단으로 사용한다.시퀀스의 처음 몇 개의 요소가 표시된 다음, 타원은 시퀀스를 계속하기 위해 가장 간단한 해석을 적용해야 함을 나타낸다.타원 오른쪽에 종료 값이 나타나지 않으면 시퀀스가 무한대로 간주된다.

In general, ${\displaystyle \{1,\dots ,n\}}$ denotes the set of all natural numbers ${\displaystyle i}$ such that ${\displaystyle 1\leq i\leq n}$. Another notation for ${\displaystyle \{1,\dots ,n\}}$ is the bracket notation ${\displaystyle [n]}$. A subtle special case is $$${\displaystyle n=0}$, in which ${\displaystyle [0]=\{1,\dots ,0\}}$ is equal to the empty set ${\displaystyle \emptyset }$. Similarly, ${\displaystyle \{a_{1},\dots ,a_{n}\}}$ denotes the set of all ${\displaystyle a_{i}}$ for ${\displaystyl$$e 1$$leq$ i$\leq n}$

앞의 각 예에서 각 집합은 그 요소를 열거하여 설명한다.모든 세트가 이런 식으로 설명될 수 있는 것은 아니며, 가능하다면, 그들의 열거가 너무 길거나 너무 복잡해서 유용하지 않을 수도 있다.따라서, 많은 집합은 그들의 요소를 특징짓는 속성에 의해 정의된다.이 특성화는 다음의 예와 같이 일반 산문을 사용하여 비공식적으로 행해질 수 있다.

• ${\displaystyle }$파인 스트리트에 있는$$ ${\$$displaystyle$$\{}$ 주소는 파인 스트리트에 있는 모든 주소의 집합이다$.$

그러나 산문적 접근법은 정확성이 부족하거나 모호할 수 있다.따라서, 세트빌더 표기법은 다음 절에서 설명한 것처럼 정의되는 세트의 요소들을 서술하는 술어와 함께 종종 사용된다.

술어에 의해 정의된 설정

세트빌더 표기법은 술어로 정의되는 집합, 즉 집합의 요소에 대해 참으로 평가하고 그렇지 않으면 거짓으로 평가하는 논리 공식에 사용할 수 있다.^[3]이 형태에서 세트빌더 표기법에는 변수, 대장 또는 수직 막대 구분자, 술어의 세 부분이 있다.따라서 구분자 왼쪽에는 변수가 있고, 그 오른쪽에는 규칙이 있다.이 세 부분은 곱슬곱슬한 괄호로 되어 있다.

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

또는

${\displaystyle \{x:\Phi (x)\}}$

세로 막대(또는 대장)는 "그러한", "어떤 용도로" 또는 "그 속성을 가진" 것으로 읽을 수 있는 구분자 입니다.φ(x) 공식은 규칙 또는 술어라고 한다.술어가 (참)을 갖는 x의 모든 값은 정의되는 집합에 속한다.술어가 보유하지 않는 x의 모든 값은 집합에 속하지 않는다.따라서${\displaystyle }${ ${\displaystyle x}$ ${\displaystyle \mid }$ ${\displaystyle \mathrm{\phi }}$( ${\displaystyle x}$) ${\displaystyle \}}$ ${\displaystyle \{x\mid \Phi (x)\}}$은 공식 φ을 충족하는 x의 모든 값의 집합이다$$.^[4]x 값이 공식을 만족하지 않는 경우 빈 집합일 수 있다.

도메인 지정

도메인 E는 세로 막대의 왼쪽에 나타날 수 있다.^[5]

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

또는 그것을 술어에 붙임으로써:

${\displaystyle \{x\mid x\in E{\text{} 및 }\Phi (x)\}\quad {\text{or}\quad \{x\mid x\in E\land \Phi(x)\}}$

여기서 ∈ 기호는 설정된 멤버십을 나타내며, $\{{\displaystyle }$ ${\displaystyle \land$} 기호는$$ 논리적 연결로 알려진 논리적 "and" 연산자를 나타낸다.이 표기법은 술어가 참인 일부 주어진 집합 E에 속하는 x의 모든 값의 집합을 나타낸다(아래 "존재 공리 설정" 참조).If ${\displaystyle \Phi (x)}$ is a conjunction ${\displaystyle \Phi _{1}(x)\land \Phi _{2}(x)}$, then ${\displaystyle \{x\in E\mid \Phi (x)\}}$ is sometimes written ${\displaystyle \{x\in E\mid \Phi _{1}(x),\Phi _{2}(x)\}}$,기호 $\wedge {\displaystyle }$ ${\displaystyle \land}$ 대신 쉼표를 사용하여$$.

일반적으로, 담론의 영역을 정의하지 않고 세트를 고려하는 것은 좋은 생각이 아니다. 이는 술어가 참인 것으로 존재할 수 있는 모든 가능한 것들의 하위 집합을 나타낼 수 있기 때문이다.이것은 쉽게 모순과 역설로 이어질 수 있다.예를 들어 러셀의 역설은 비록 겉보기에는 세트빌더 표현으로 잘 형성되어 있지만$$ {${\displaystyle x}$ x${\displaystyle \notin }$ ${\displaystyle x\},}$ ${\displaystyle \{x~x\not \in$ x$\}}}$라는 표현은 모순을 일으키지 않고는 세트를 정의할 수 없다는 것을 보여준다.^[6]

설정 E가 맥락에서 명확할 경우 명시적으로 지정되지 않을 수 있다.저자가 미리 도메인을 기술한 다음 세트빌더 표기법에 명시하지 않는 것은 문헌에 흔히 있는 일이다.예를 들어, 저자는 "별도가 명시되지 않는 한, 변수는 자연수로 간주되어야 한다"와 같은 것을 말할 수 있지만, 도메인을 가정할 수 있는 덜 공식적인 맥락에서, 서면 언급은 종종 불필요하다.

예

다음 예는 술어를 통한 세트빌더 표기법으로 정의된 특정 집합을 예시한다.각각의 경우, 세로 막대의 왼쪽에 도메인이 지정되고, 오른쪽에는 규칙이 지정된다.

• x> ${\displaystyle \{x\in \mathb {R} \mid x>0\}}$은$(,{\displaystyle }$ ) ${\displaystyle (0,\infty )}$로 구간 표기할 수 있는 모든 엄격히 양의 실수의 집합이다$.$
• ${\displaystyle \{}$ ${\displaystyle x}$ ${\displaystyle \in }$ ${\displaystyle R\mathbb{}}$ ${\displaystyle \mid }$ ${\displaystyle x}$= ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle \{x\in \mathb {R} \mid$ x $=1\}}$은(는) 세트${\displaystyle }${${\displaystyle }$- ${\displaystyle 1}$, ${\displaystyle 1}$} ${\displaystyle$\{-$1\}$입니다$.$이 집합은 또한${\displaystyle }${ ${\displaystyle x}$∈ ${\displaystyle R\mathbb{}}$ ${\displaystyle \mid }$ x ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle 1}$ ${\displaystyle \}}$ ${\displaystyle \{x\in \mathb {R} \mid x^{2}=1\}}}}$로 정의할 수 있다$.$ 아래 동등한 술어가 동일한 집합을 산출하는지 확인하십시오.
• For each integer m, we can define ${\displaystyle G_{m}=\{x\in \mathbb {Z} \mid x\geq m\}=\{m,m+1,m+2,\ldots \}}$. As an example, ${\displaystyle G_{3}=\{x\in \mathbb {Z} \mid x\geq 3\}=\{3,4,5,\ldots \}}$ and ${\displaystyle G_{-2}=\{-}$${\displaystyle 2}$,${\displaystyle }$- ${\displaystyle 1}$,${\displaystyle 0,\dots \}}$ ${\displaystyle G_{-2}=\{-2,-1,0,\ldots$ $\backslash \}\}.$
• ( , y) 0< < >${\displaystyle \{(x,y)\in \mathb {R} \timees \mathb {R} \mid 0<f(x)\}}}}}$은 주어진 함수 f에 대해 y가 0보다 크고 f(x)보다 작은 실수 쌍의 집합이다.여기서 데카르트 제품 $R{\displaystyle \mathbb{}}$ ${\displaystyle \times }$ ${\displaystyle R\mathbb{}}$ ${\$은 순서가 지정된 실수 쌍 집합을 나타낸다$$.
• ${\displaystyle \{n\in \mathb {N} \mid (\exists k)[k\in \mathb$$}}}}$은(는) 모든 자연수의 집합이다.$\wedge {\displaystyle }$ ${\displaystyle \land }$의 부호는 논리적 연결로 알려진 "and"를 의미한다.∃ 부호는 실존적 정량화라고 알려진 "존재한다"를 의미한다.${\displaystyle 예}$를 들어 (${\displaystyle \mathrm{\exists }}$ x${\displaystyle }$) ${\displaystyle P}$( ${\displaystyle x}$) ${\displaystyle (\exist x)P(x)}$은(는) 'P(x)와 같은 x가 존재한다'로 읽힌다$$.
• $}$$}}}}$은 짝수 자연수의 같은 집합에 대한 공칭 변종이다$$.우측의 공식에 의해 함축되어 있기 때문에 n은 자연수라고 명시할 필요는 없다.
• ${\displaystyle \{a\in \mathbb {R} \mid (\exists p\in \mathbb {Z} )(\exists q\in \mathbb {Z} )[q\not =0\land aq=p]\$$}}}$은 이성적인 숫자의 집합, 즉 두 정수의 비율로 쓸 수 있는 실수의 집합이다.

표기법 왼쪽의 더 복잡한 표현식

세트빌더 표기법의 확장은 단일 변수 x를 표현식으로 대체한다.${\displaystyle \mathrm{따라서}}$ { x should${\displaystyle }$${\displaystyle \backslash }$(${\displaystyle x}$)${\displaystyle }$} ${\displaystyle \{x\mid \Phi (x)\}$ 대신 {$$(${\displaystyle x}$ )${\displaystyle }$∣ ∣${\displaystyle \mathrm{\phi }}$ (x${\displaystyle }$)${\displaystyle }$, \, {\$displaystyle \{\PSi (x)\mid \Phi (x\}}}}}}}$이)가 있을 수 있다$$$.$

$displaystyle \{\Psi (x)\mid \Phi (x)\\\$$}}=\{y\mid \exists (x),y=\PSI (x){\text{와 }}\Phi (x$

예를 들면 다음과 같다.

• ${\displaystyle \{}$ ${\displaystyle \mathrm{2n}}$ ${\displaystyle \mid n}$ ${\displaystyle \in N\mathbb{}\}}$ ${\displaystyle \{2n\mid n\in \mathb{N}$ 여기서 $N{\displaystyle \mathbb{}}$ ${\$은 모든 자연수의 집합이다.
• ${\displaystyle \{p}$ /${\displaystyle q}$ /$$q ${\displaystyle \mid }$ ${\displaystyle p\mathbb{}}$, ${\displaystyle q}$ ${\displaystyle \in }$ Z ,$$ $≠$ ${\displaystyle 0\}}$ ${\displaystyle \{p/q\mid p,q\not =0$ $여기$서 Z ${\$$displaysty \mathb$$${$Z$$}$는 모든 정수의 집합이며, $모든{\displaystyle \mathbb{}}$ 합리적인 숫자의 집합이다$.$
• ${\displaystyle \{}$ ${\displaystyle 2}$ ${\displaystyle t}$+ ${\displaystyle 1}$ ${\displaystyle \mid }$ ${\displaystyle t}$ ${\displaystyle \in }$ ${\displaystyle Z\mathbb{}}$ ${\displaystyle \}}$ ${\displaystyle \{2t+1\mid t\in \mathb {Z}$\}}}은$$ 홀수 정수 집합이다.
• ${\displaystyle \{}$( ${\displaystyle t,}$ 2 ${\displaystyle t}$+ ${\displaystyle 1}$) ${\displaystyle \mid }$ ${\displaystyle t}$ ${\displaystyle \in }$ ${\displaystyle Z\mathbb{}}$} ${\displaystyle \{(t,2t+1)\mid$ t$\in \mathb {Z}$\}}}}}}은(는) 쌍 집합을 생성하며$$, 각 쌍이 홀수 정수와 대응한다.

역함수가 명시적으로 명시될 수 있을 때, 왼쪽의 표현은 단순 치환으로 제거할 수 있다.Consider the example set ${\displaystyle \{2t+1\mid t\in \mathbb {Z} \}}$. Make the substitution ${\displaystyle u=2t+1}$, which is to say ${\displaystyle t=(u-1)/2}$, then replace t in the set builder notation to find

${\displaystyle \{2t+1\mid t\in \mathb {Z} \}=\{u\mid (u-1)/2\in \mathb {Z}}$

등가 술어는 동일한 집합을 생성함

두 세트는 동일한 요소를 가진 경우에만 동일하다.도메인 지정자를 포함한 집합 작성자 규칙이 동일한 경우에만 집합 작성자 표기법으로 정의된 집합이 동일하다.그것은

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

만약의 경우에 한해서만

$]$$\Leftrightarrow (t\in$ B$\land$ Q$(t)]]}$.

따라서 세트 빌더 표기법에 의해 정의된 두 세트의 동일성을 입증하기 위해서는 도메인 한정자를 포함한 그들의 술어의 동등성을 증명하는 것으로 충분하다.

예를 들면

${\displaystyle \{x\in \mathb {R} \mid x^{2}=1\}=\{x\in \mathb {Q} \mid x =1\}}$

두 가지 규칙 술어는 논리적으로 동일하기 때문이다.

${\displaystyle(x\in \mathb {R} \land x^{2}=1)\왼쪽 화살표(x\in \mathb {Q} \land x =1)}$

x = 1${\displaystyle$ x$=1$}을$($를) 가진 합리적인 숫자인 경우에만$$ x ${\displaystyle 2{}^{}}$= 1 ${\displaystyle$ $x$$={2}=1}$이 동등하기 때문에 이 동등성은 유지된다$.$ 특히 두 세트는 모두${\displaystyle }$집합${\displaystyle }${${\displaystyle }$- ${\displaystyle 1}$, ${\displaystyle 1}${\displaystyle$\{-1\}}\displaystystyle$ \}과 동일하다$.$

존재 공리 설정

제르멜로-프렌켈 집합 이론과 같은 많은 공식 집합 이론에서 세트 빌더 표기법은 이론의 공식 구문에 포함되지 않는다.그 대신 E가 집합이고 ((x)가 집합 이론 언어의 공식이라면, φ을 만족시키는 E의 요소인 집합 Y가 있다.

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

이 공리에서 얻은 집합 Y는 정확히 ${\displaystyle \mathrm{세트빌더}}$ 표기법에서${\displaystyle }${ x ${\displaystyle \in }$ ${\displaystyle E}$ ${\displaystyle \mid }$ ${\displaystyle \mathrm{\phi }}$ (${\displaystyle x}$) ${\displaystyle \}}$ ${\displaystyle \{x\in E\mid \Phi (x)\}}$로 기술된 집합이다$.$

프로그래밍 언어의 유사성

다수의 프로그래밍 언어에서 사용할 수 있는 유사한 표기법(Python and Haskell)은 하나 이상의 목록에 대한 지도와 필터 연산을 결합한 목록 이해법이다.

파이썬에서 세트빌더의 가새들은 각각 대괄호, 괄호 또는 곱슬 가새, 리스트, 제너레이터, 세트 오브젝트로 대체된다.파이썬은 영어 구문을 사용한다.하스켈은 세트빌더의 브레이스를 대괄호로 교체하고 표준 세트빌더 수직 막대를 포함한 기호를 사용한다.

"for" 키워드가 "수익" 키워드를 사용하여 산출된 변수 목록을 반환하는 시퀀스 포괄성을 사용하여 스칼라에서도 동일한 결과를 얻을 수 있다.^[7]

다음과 같은 프로그래밍 언어의 세트빌더 표기법 예를 참조하십시오.

	예 1	예 2
세트빌더	${\displaystyle \{l\ \in L\}}$	${\displaystyle \{(k,x)\ \k\in K\wedge x\in X\wedge P(x)\}}$
파이톤	{l 을 위해 l 에 L}	{(k, x) 을 위해 k 에 K 을 위해 x 에 X 만일 P(x)}
하스켈	[l l <- ls]	[(k, x) k <- ks, x <- xs, p x]
스칼라	을 위해 (l <- L) 양보하다 l	을 위해 (k <- K; x <- X 만일 P(x)) 양보하다 (k,x)
C#	로부터 l 에 L 선발하다 l	로부터 k 에 K 로부터 x 에 X 어디에 P(x) 선발하다 (k,x)
SQL	선택 l From L_set	선택 k, x From K_set, X_set 어디에 P(x)
루비	L.지도를 그리다{ l l}	K.상품(X).선발하다{ k,x P(x) }
얼랑	[l l <- ls]

세트 작성기 표기법과 목록 이해 표기법은 모두 0원소가 있는 모나드에 대해 지도/필터 유사 연산을 허용하는 모나드 포괄이라고 알려진 보다 일반적인 표기법 사례다.

참고 항목

• 집합론 용어집

메모들