집합론(Set theory)

집합의 연산(Set operations)

두 집합⁠(set)⁠에서 새 집합을 만드는 방법들. 합집합(또는), 교집합(그리고), 차집합(빼고), 여집합(아닌 것).

A \cup B,\quad A \cap B,\quad A \setminus B,\quad A^c,\quad A \,\triangle\, B

먼저 보면 좋은 개념집합

집합 두 개가 있으면 논리 연산으로 새 집합을 만들 수 있습니다. "A 또는 B"는 합집합⁠(union)⁠, "A 그리고 B"는 교집합⁠(intersection)⁠, "A인데 B는 아닌"은 차집합⁠(set difference)⁠, "A가 아닌"은 여집합입니다. 아래 사각형 안의 점 하나하나가 전체집합의 원소입니다. 연산을 (으)로 골라 보세요. 결과는 의 점입니다.

파란 원이 A, 분홍 원이 B입니다. 두 원의 중심을 끌어 겹침을 바꿔 보세요.

지금 $|A| =$ , $|B| =$ , $|A \cap B| =$ 이고 $|A \cup B| =$ 입니다. 합집합은 두 크기를 더한 뒤 두 번 센 겹침을 한 번 빼면 됩니다. 이 셈법을 일반화한 것이 포함배제 원리⁠(inclusion–exclusion principle)⁠입니다.

사각형 안의 점 하나를 고르게(모든 점을 같은 확률⁠(probability)⁠로) 뽑는다고 하면, 점의 개수를 전체 개수로 나눈 값이 확률입니다. 확률의 덧셈 법칙 $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ 은 이 그림 그대로이고, B 안에서 A가 차지하는 비율이 조건부 확률⁠(conditional probability)⁠입니다.

한 집합의 부분집합⁠(subset)⁠을 모두 모으면 멱집합⁠(power set)⁠이 됩니다. 각 부분집합은 "각 원소⁠(element)⁠가 들어가나?"에 대한 예/아니오의 줄, 곧 이진수로 적을 수 있어서, 원소가 4개면 부분집합은 $2^4 = 16$ 개입니다.

두 집합이 얼마나 닮았는지는 교집합 크기를 합집합 크기로 나누어 잴 수 있습니다(자카드 지수⁠, Jaccard index⁠). 교집합 크기의 두 배를 두 집합 크기의 합으로 나누면 쇠렌센–다이스 계수⁠(Sørensen–Dice coefficient)⁠입니다. 둘 다 두 집합이 같을 때 1, 겹침이 없을 때 0입니다.

집합 A를 하나 고정하면 모든 X, Y에 대해 $A\cap X\subseteq Y \iff X\subseteq A^{c}\cup Y$ 입니다. 'A와 교집합'과 'A의 여집합⁠(complement)⁠과 합집합'이 이렇게 짝을 이루는 것이 갈루아 연결⁠(Galois connection)⁠의 한 예이고, 논리로 옮기면 '그리고'와 '이면'의 관계입니다.

관련된 시대와 장소모스크바 수학 학파

이 개념이 나오는 큰 생각쌍대성

이 개념이 나오는 긴 글

확률 도박판에서 온 편지 1654년, 도중에 멈춘 내기의 판돈을 어떻게 나눌까? 두 수학자가 주고받은 편지에서 확률론이 태어났다. 집합론 무한에도 크기가 있다 자연수와 짝수는 어느 쪽이 많을까? 칸토어는 무한을 세는 법을 찾았고, 무한이 하나가 아님을 보였다. 거리와 유사도 까마귀와 택시 까마귀는 곧장 날고 택시는 블록을 돌아간다. '얼마나 먼가'에는 답이 하나가 아니고, 어떤 거리를 고르느냐가 통계와 기계 학습의 답을 바꾼다. 매칭과 흐름 짝을 찾는 알고리즘 의대 졸업생과 병원, 신장 기증자와 환자, 철도와 화물. 누구를 누구와 이을지 정하는 수학은 냉전의 철도 지도에서 노벨 경제학상까지 이어진다. 범주론 화살표만으로 본 수학 최대공약수와 교집합과 '그리고'는 같은 것이고, 화살표를 뒤집으면 최소공배수와 합집합과 '또는'이 된다. 무엇으로 만들었는지 묻지 않고 어떻게 이어지는지만 보는 언어로, '자연스럽다'는 말의 뜻, 관계만으로 대상을 알아보는 요네다의 생각, 함자로 본 연쇄법칙, 어디에나 있는 수반까지 사이트의 여러 분야를 가로지른다.

이 개념 위에 세워진 것

포함배제 원리 자카드 지수 쇠렌센–다이스 계수 불 대수 정규 표현식 기술 집합론 갈루아 연결

이 개념을 언급하는 페이지

확률
… 하나라도 일어날 확률 P(A\cup B) 는 두 넓이를 더하고 두 번 센 겹친 부분을 한 번 빼서 입니다.집합의 연산을 넓이로 옮긴 것이고, 사건이 셋 이상이면 포함배제 원리가 됩니다. 넓이를 모르더라도 점을 무작위로 …
베이즈 정리
… 확률"입니다. 둘을 잇는 다리가 양성인 사람 전체의 수 P(+) 입니다. 격자에서 보면 양성(큰 점)이라는집합으로 표본공간을 좁히고, 그 안에서 빨간 점이 차지하는 몫을 센 것입니다. 증거를 보기 전의 …
생일 문제
… 확률(분홍)과 지수함수 근사(점선). "겹치는" 경우는 여러 방식이 얽혀 있어 세기 어렵습니다. 그래서여집합, 곧 "모두 다를" 확률을 셉니다. 두 번째 사람은 첫 사람과 다를 확률이 364/365, 세 번째는 앞 …
집합
… 담습니다. 원 반지름 r = . 집합은 수학 전체의 바닥 공사입니다. 두 집합을 합치고 겹치는 연산은집합의 연산, 원소를 짝지어 크기를 비교하는 일은 집합의 크기입니다. 확률에서는 일어날 수 있는 결과 전체가 …
포함배제 원리
합집합의 크기를 셀 때 각 집합의 크기를 그냥 더하면 겹친 부분을 여러 번 세게 됩니다. 두 번 센 것은 한 …
멱집합
… n 개를 던져 앞면이 k 개 나오는 경우의 수와 같습니다(이항분포). 부분집합을 0과 1의 줄로 적으면집합의 연산은 비트 연산이 됩니다. 합집합은 OR, 교집합은 AND, 여집합은 NOT이고, 이 계산 규칙이 ⟦불 …
중국인의 나머지 정리
… 동치류 두 개(' m 으로 나눈 나머지가 같은 수들'과 ' n 으로 나눈 나머지가 같은 수들')의교집합이고, 그것이 곧 mn 으로 나눈 나머지가 같은 수들의 동치류 하나입니다.
자카드 지수
… 청록 점은 교집합, 노랑과 파랑은 한쪽에만 있는 것, 회색은 아무도 담지 않은 것입니다. 자카드 지수는교집합의 크기를 합집합의 크기로 나눈 값, 지금 J = 입니다. 공통점이 없으면 0, 같은 집합이면 1입니다. …
쇠렌센–다이스 계수
… D = 입니다. 같은 그림의 자카드 지수(영상에서는 IoU라고 부릅니다)는 겹친 부분을 한 번 세어합집합과 비교하고, J = 입니다. 포함배제 원리 |A\cup B| = |A|+|B|-|A\cap B| 를 …
해밍 거리
… 있는 자리들의 집합'으로 보면, 해밍 거리는 둘 중 한쪽에만 있는 원소들의 모임(대칭차)의 크기입니다(집합 연산). 0/1 벡터 사이의 맨해튼 거리와도 같습니다. 컴퓨터는 두 비트열을 XOR(자리마다 두 비트가 …
불 대수
… 속한다'를 참·거짓으로 읽으면 \land 는 교집합, \lor 는 합집합, \lnot 은 여집합이 됩니다(집합의 연산). 한 집합의 모든 부분집합, 곧 멱집합이 불 대수를 이루는 까닭이고, 확률에서 사건을 …
유한 오토마톤
… 나란히 돌리면 합집합과 교집합을, 받아들임 상태를 뒤집으면 여집합을 인식합니다. 그래서 정규 언어 둘에집합의 연산을 하면 다시 정규 언어가 됩니다. 이것을 정규 언어가 집합의 연산에 대해 닫혀 있다고 말합니다. 한 …
정규 표현식
… r에 맞는 조각을 0번 이상 잇습니다. 식 하나가 뜻하는 것은 문자열들의 집합, 곧 언어이고, 선택은합집합입니다. 예를 들어 (a|b)*abb는 'a와 b로 된 아무 문자열 뒤에 abb'이니, abb로 끝나는 …
보편 성질: 곱, 쌍대곱, 극한
… 모노이드⟧의 '하나뿐인 연장'도 보편 성질입니다. 순서에서의 곱과 쌍대곱은 불 대수의 AND·OR이자집합의 연산의 교집합·합집합이고, 나누어떨어짐에서는 최대공약수와 최소공배수이며, 소인수분해로 보면 소수마다 …
수반 함자
… 선형변환에서 이미 본 수반입니다. 합집합은 보존하지만 교집합은 보존하지 않는 상(image)의 성질은집합의 연산에서 직접 확인할 수 있습니다. 순서 사이의 수반을 따로 갈루아 연결이라 부르며, 프로그램 실행의 최강 …
갈루아 연결
… = \min(\lfloor x/k\rfloor, \lfloor y/k\rfloor) 입니다.집합의 연산에도 갈루아 연결이 있습니다. 집합 A를 하나 고정하면 모든 X, Y에 대해 A\cap X\subseteq …

이 페이지가 가리키는 개념

불 대수 포함배제 원리 확률 조건부 확률 멱집합 자카드 지수 쇠렌센–다이스 계수 갈루아 연결