멱집합(Power set)

이 개념 위에 세워진 것

이 개념을 언급하는 페이지

• 확률

  확률의 무대는 표본공간 \Omega , 곧 일어날 수 있는 모든 결과의 집합입니다. 사건은 그부분집합이고, 확률은 사건이 표본공간에서 차지하는 몫 입니다. 주사위를 한 번 던지면 표본공간은 {1, 2, 3, …

• 집합

  … 비교하는 일은 집합의 크기입니다. 확률에서는 일어날 수 있는 결과 전체가 집합(표본공간)이고 사건은 그부분집합입니다(확률). 소수를 모은 소수 집합, 나머지가 같은 수끼리 묶는 동치류도 모두 집합입니다. …

• 집합의 연산

  … 그림 그대로이고, B 안에서 A가 차지하는 비율이 조건부 확률입니다. 한 집합의 부분집합을 모두 모으면멱집합이 됩니다. 각 부분집합은 "각 원소가 들어가나?"에 대한 예/아니오의 줄, 곧 이진수로 적을 수 있어서, …

• 집합의 크기

  … 아닙니다. 실수 전체는 어떻게 짝지어도 빠지는 수가 생기고(대각선 논법), 어떤 집합이든 그멱집합은 원래 집합보다 엄격히 큽니다. 무한에도 크기의 층이 끝없이 있습니다. 전단사로 짝지을 수 있다는 관계는 …

• 가산 집합

  … 글자열")을 언어 라 부릅니다. 글자열 전체는 가산 무한이고 언어는 그 부분집합이니, 언어 전체는 자연수의멱집합처럼 셀 수 없이 많습니다. 문법은 셀 수 있을 만큼뿐이고 언어는 셀 수 없이 많으니, 어떤 문법이나 …

• 칸토어의 대각선 논법

  … 하면, 1, 0, 1, 0, 0, 0, …은 {1, 3}을 뜻합니다. 그래서 같은 논법으로 자연수의멱집합(부분집합 전체)이 자연수보다 크다는 것도 나옵니다. 유리수는 가산이니, 실수에서 유리수를 빼고 남은 …

• 소인수분해

  … 하나는 "어떤 소수를 고를까"라는 선택, 곧 소인수 집합의 부분집합 하나입니다. 그래서 약수의 개수는멱집합의 크기 2^k 이 됩니다. 30의 약수는 2^3 = 8 개입니다. 소인수를 알면 오일러 피 함수도 …

• 파스칼의 삼각형

  … 이항분포 \binom nk / 2^n 입니다. 크기 k 인 부분집합의 개수이므로 한 줄을 모두 더하면멱집합의 크기 2^n 입니다. 이제 각 수를 m = 으로 나눈 나머지로 칠해 봅시다(모듈러 연산). 줄 수는 …

• 진법

  … 선택입니다. 그래서 앞자리 0을 허용한 k 자리 2진수(0부터 2^k - 1 까지)는 k 개짜리 집합의부분집합과 정확히 일대일로 대응합니다. 소수점 아래도 같습니다. 0과 1 사이의 분수 \tfrac{p}{q} 를 …

• 이항계수

  … b = 1 을 넣으면 \sum_k \binom nk = 2^n , 원소가 n개인 집합의 부분집합 전체, 곧멱집합의 크기입니다(지금 ). 1665년 무렵 뉴턴은 지수가 정수가 아닐 때에도 (1+x)^\alpha = …

• 연속체 가설

  … 2 × 2 × 2 = 8개입니다. 원소가 n개면 2^n 개입니다. 이것을 본떠 자연수의 부분집합 전체(멱집합)의 크기를 2^{\aleph_0} ('2의 알레프 0 제곱')라 적습니다. 0과 1 사이의 실수를 ⟦이진 …

• 그래프

  … 개(파스칼의 삼각형)이고, 이름 붙은 n개 점 위의 그래프는 그 자리들의 부분집합마다 하나씩, 곧멱집합의 크기인 2^{\binom{n}{2}} 가지입니다. 꼭짓점의 이름만 다르고 연결 모양이 같은 두 그래프는 …

• 4색 정리

  … 원리⟧로 셉니다. 나쁜 조건을 고른 변들의 모임마다 더하거나 빼므로, 변 집합의 모든 부분집합, 곧멱집합에 대한 합이 됩니다. 이어지는 곳. 구면 위의 지도도 네 색이면 됩니다. 구면에서 한 점을 빼면 …

• 불 대수

  … \lor 는 합집합, \lnot 은 여집합이 됩니다(집합의 연산). 한 집합의 모든 부분집합, 곧멱집합이 불 대수를 이루는 까닭이고, 확률에서 사건을 '그리고·또는·아니다'로 묶는 계산도 같은 대수입니다. …

• 러셀의 역설

  … 기본 원리였기 때문입니다. 이 논증은 칸토어의 대각선 논법과 같은 모양입니다. 칸토어는 집합 A에서멱집합으로 가는 어떤 함수 f도 모든 부분집합에 닿지 못함을, 부분집합 \{x \in A : x \notin …

• P 대 NP 문제

  … 답을 찾으려면 부분집합을 하나씩 시도할 수 있습니다. n개의 수에서 만들 수 있는 부분집합은멱집합의 크기인 2^n 개입니다. 탐색은 부분집합에 0부터 2^n - 1 까지의 이진수 번호를 붙여 차례로 …

• 유한 오토마톤

  … 기계는 상태들의 부분집합을 새 상태로 삼아 결정적 기계로 바꿀 수 있고, 그래서 상태가 최대 2^k 개(멱집합)로 늘어날 수 있습니다. 한계도 분명합니다. a를 n개 쓰고 b를 n개 쓴 문자열 a^n b^n 만 …

• 촘스키 위계

  … 가산 개입니다. 반면 언어는 Σ*(Σ의 글자로 만들 수 있는 모든 유한 문자열의 집합)의 부분집합이라멱집합만큼, 곧 대각선 논법에 따라 셀 수 없이 많습니다. 따라서 어떤 문법으로도 적을 수 없는 언어가 셀 …

• 정규 표현식

  … '지금 있을 수 있는 상태들의 집합'을 새 상태로 삼으니, 상태 n개짜리 기계가 최대 2^n 개, 곧멱집합의 크기만큼 불어날 수 있습니다. '끝에서 k번째 글자가 a'라는 패턴은 비결정적 오토마톤으로는 상태 …

• 트리

  … 것입니다. 꼭짓점 개면 트리는 개인데, 같은 점들 위의 그래프는 모두 2^{\binom{n}{2}} 개(멱집합의 크기)로 개입니다. 이어진 그래프가 주어지면, 그 그래프의 변만 써서 모든 꼭짓점을 잇는 트리를 신장 …

• 홀의 정리

  … 변 수의 곱 정도입니다(점근 표기법). 반면 홀 조건을 하나하나 확인하려면 사람들의 모든 부분집합, 곧멱집합의 원소 2^n 개를 봐야 합니다. 지금 매칭의 크기는 이고, 조건을 어기는 무리는 이 알고리즘은 증명도 …

• 공리와 공준

  … 집합을 원소로 갖는 집합이 있다. 집합들의 원소를 모두 모은 합집합이 있다. 모든 부분집합을 모은 집합(멱집합)이 있다. 0, 1, 2, …를 모두 담는 무한집합이 있다. 이미 있는 집합에서 조건에 맞는 원소만 …

• 기술 집합론

  칸토어의 집합론에 따르면 실수의 부분집합은멱집합의 크기만큼, 곧 실수보다도 많습니다. 그런데 유한한 글자로 적을 수 있는 규칙은 셀 수 있을 만큼뿐이니, …

• 대수적 자료형

  … A → 2는 A의 원소를 참과 거짓으로 가르는 방법이니 A의 부분집합과 하나씩 짝지어지고, 그래서멱집합의 크기가 2^{|A|} 입니다. 지수 법칙도 프로그램입니다. c^{ab} = (c^b)^a 는 (A …

• 함자

  … 함자는 흔합니다. 군에서 연산을 잊고 원소의 집합만 남기는 '잊는 함자' Grp → Set, 집합을멱집합으로 보내고 함수를 '상(image)을 구하는 함수'로 보내는 함자, 대상이 하나인 범주로 본 모노이드 …

• 데카르트 닫힌 범주

  … 도구가 증명 보조기입니다. 함수 집합의 크기 |B^A| = |B|^{|A|} 에서 A를 무한으로 보내면멱집합과 무한집합의 크기 이야기가 됩니다. 곱을 복사와 버리기가 없는 텐서곱으로 바꿔 커링하면 ⟦모노이드 …

• 영역 이론: 스콧과 재귀의 의미

  … 이것이 크나스터–타르스키 정리입니다. 1928년 크나스터와 타르스키가 한 집합의 부분집합 전체(멱집합)에 대해 증명했고, 1955년 타르스키가 모든 완비 격자로 넓혔습니다. 다만 이 정리는 있다는 것만 말할 …

• F-대수와 fold: 재귀와 귀납의 범주론

  … 고정점을 찾는 클리니 반복과 같은 모양입니다. 람벡 보조정리는 '없다'는 판정에도 쓰입니다. 집합을멱집합으로 보내는 함자 P에는 시작 대수가 없습니다. 있다면 X\cong P(X) 일 텐데, ⟦칸토어의 대각선 …

• 토포스: 집합을 닮은 우주

  … 와 정확히 하나씩 대응합니다. 그래서 원소가 n개인 집합의 부분집합은 2^n 개입니다(멱집합). 범주론의 말로 하면, 두 원소 집합 Ω = {참, 거짓}은 '부분집합을 분류하는 대상'입니다. …

이 페이지가 가리키는 개념