집합의 분할
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
집합의 분할은 주어진 집합을 서로소인 부분 집합들로 나누는 것을 의미한다. 이는 공집합을 포함하지 않고, 원래 집합을 덮으며, 각 부분 집합들이 서로소인 집합족을 구성한다. 분할은 동치 관계와 밀접한 관련이 있으며, 동치 관계의 몫집합은 분할을, 분할로부터는 동치 관계를 정의할 수 있다. 분할은 원순서 및 집합론적, 순서론적 성질을 가지며, 세분 관계를 통해 격자를 형성한다. 집합의 분할은 벨 수로 표현되며, 특정 조건을 만족하는 비교차 분할은 자유 확률론에서 중요한 역할을 한다. 예를 들어, {1, 2, 3} 집합의 분할은 5가지가 존재하며, 플레잉 카드를 색깔이나 무늬별로 나누는 것도 분할의 예시이다.
더 읽어볼만한 페이지
- 집합족 - 가측 공간
가측 공간은 집합과 그의 멱집합의 부분 시그마 대수로 이루어진 순서쌍으로, 시그마 대수는 여집합과 가산 합집합에 대해 닫혀 있는 성질을 가지며, 가측 공간과 가측 함수는 구체적 범주를 이룬다. - 집합족 - 하이퍼그래프
하이퍼그래프는 그래프를 일반화하여 하나의 에지가 여러 정점을 연결할 수 있는 구조로, 만족 문제, 데이터베이스, 머신 러닝 등 다양한 분야에 활용되며, 방향성에 따라 무방향과 방향 하이퍼그래프로 구분되고, 모든 하이퍼에지 크기가 동일한 k-균일 하이퍼그래프는 여러 응용 분야에서 유용하다. - 집합론의 기본 개념 - 치역
치역은 함수에서 정의역의 모든 원소에 대한 함숫값들의 집합으로, 공역의 부분집합이며, 함수의 상을 의미하거나 공역 전체를 의미하기도 한다. - 집합론의 기본 개념 - 항등 함수
항등 함수는 집합 X의 각 원소를 자기 자신에게 대응시키는 함수로서, 정의역과 공역이 같은 집합 X에서 단사 함수이자 전사 함수이며, 함수 합성에서 항등원의 역할을 수행하는 중요한 개념이다. - 조합론 - 계승 (수학)
계승은 음이 아닌 정수 n에 대해 1부터 n까지의 자연수를 곱한 값으로, 0의 계승은 1로 정의되며, 대칭군의 크기와 같다는 성질을 통해 기수로 확장될 수 있고, 다중 계승, 지수 계승 등으로 확장 및 응용되어 다양한 분야에서 활용된다. - 조합론 - 직교 배열
직교 배열은 크기 q의 유한 집합 알파벳 Σ, 인자수 n, 실험 실행 B로 구성되며, Σⁿ의 n개 좌표 중 임의의 t개를 골랐을 때 수준의 모든 t-순서쌍이 같은 수 λt번 등장하는 부분 집합으로, 실험 설계, 부호 이론, 소프트웨어 테스트 등 다양한 분야에 응용된다.
집합의 분할 |
---|
2. 정의
집합 의 분할은 다음 세 조건을 만족하는 부분 집합들의 모임 이다.[9]
달리 표현하면, 집합족 ''P''는 다음 조건을 모두 만족하는 경우에만 ''X''의 분할이다:[3]
- ''P''는 공집합을 포함하지 않는다.
- ''P''에 있는 집합들의 합집합은 ''X''와 같다.
- ''P''에 있는 임의의 두 서로 다른 집합의 교집합은 공집합이다.
에 있는 집합들을 분할의 ''블록'', ''부분'' 또는 ''셀''이라고 부른다.[6]
3. 성질
집합 ''X''의 분할은 ''X''의 모든 원소가 정확히 하나의 부분 집합에 속하도록 하는, ''X''의 공집합이 아닌 부분 집합들의 집합이다.[2]
집합족 ''P''가 다음 조건을 모두 만족하면 ''X''의 분할이다:[3]
- ''P''는 공집합을 포함하지 않는다.
- ''P''에 있는 집합들의 합집합은 ''X''와 같다. (''P''의 집합들은 ''X''를 '''덮는다''')
- ''P''에 있는 임의의 두 서로 다른 집합의 교집합은 공집합이다. (''P''의 원소들은 쌍별 소집합이다.)
에 있는 집합들을 분할의 ''블록'', ''부분'' 또는 ''셀''이라고 한다. 일 때, 를 포함하는 셀을 로 나타낸다.
유한 집합 의 분할 의 '''계수'''는 이다.
3. 1. 동치 관계와의 관계
집합 X영어 위의 임의의 동치 관계 에 대하여, 그 몫집합 은 X영어의 분할이다. 반대로, X영어의 임의의 분할 가 주어졌을 때, X영어 위에 이항 관계:
를 정의할 수 있다. 이는 두 원소가 분할 속 어떤 같은 집합에 속하는 이항 관계를 나타낸다. 이는 X영어 위의 동치 관계이다. 동치 관계와 분할 사이의 두 연산은 서로 역연산이므로, 동치 관계와 분할의 개념은 사실 서로 동치이다.[10]
모든 분할 는 X영어에 대한 동치 관계 로 식별할 수 있다. 즉, 임의의 에 대해 인 것은 (또는 )인 경우이다. 표기법 는 동치 관계가 분할로부터 구성될 수 있다는 생각을 연상시킨다. 반대로 모든 동치 관계는 분할로 식별될 수 있다. 이것이 때때로 "동치 관계는 분할과 같다"고 비공식적으로 말하는 이유이다.
집합 위의 임의의 동치 관계에 대해, 그 동치류의 집합은 의 분할이다. 집합 의 동치 관계 로부터 그 동치류 집합으로서 의 분할을 얻는 것을, 에 의한 의 '''류별''' 또는 '''분류'''라고 부른다.[7]
반대로, 의 임의의 분할 로부터 위의 동치 관계 를 정의할 수 있다. 즉, 의 임의의 두 원소 와 가 의 같은 블록에 속할 때, 라고 하면, 이것은 동치 관계를 정한다. 이때, 동치 관계 를 분할 에 '''수반하는''' 동치 관계라고 한다.[7]
따라서, 집합에 동치 관계를 설정하는 것과 집합의 분할은 본질적으로 같다.[8]
3. 2. 원순서와의 관계
집합 위의 원순서는 의 분할과 그 분할 위의 부분 순서의 조합으로 나타낼 수 있다.3. 3. 집합론적 성질
체르멜로-프렝켈 집합론에서, 다음 두 명제는 서로 동치이며, 이를 '''분할 원리'''(partition principle영어)라고 한다.- 임의의 두 집합 에 대하여, 만약 전사 함수 가 존재한다면, 단사 함수 가 존재한다.
- 임의의 집합 및 그 분할 에 대하여, 단사 함수 가 존재한다. 즉, 집합의 분할의 크기는 집합의 크기를 넘지 않는다.
선택 공리는 분할 원리를 함의한다. 이는 선택 함수 가 존재하며, 임의의 에 대하여 이므로 가 단사 함수이기 때문이다. 그러나 선택 공리와 분할 원리가 동치인지 여부는 아직 알려지지 않았다.
집합 ''X''에 대한 모든 동치 관계에 대해, 그 동치류의 집합은 ''X''의 분할이다. 반대로, ''X''의 임의의 분할 ''P''로부터, ''x''와 ''y''가 ''P''의 동일한 부분에 있을 때 ''x'' ~ ''y''로 정의하면, ''X''에 대한 동치 관계를 정의할 수 있다. 따라서 동치 관계와 분할의 개념은 본질적으로 동일하다.
선택 공리는 집합 ''X''의 임의의 분할에 대해 분할의 각 부분에서 정확히 하나의 원소를 포함하는 ''X''의 부분 집합의 존재를 보장한다. 이는 집합에 대한 동치 관계가 주어지면 모든 동치류에서 대표 원소를 선택할 수 있음을 의미한다.
3. 4. 순서론적 성질
집합 의 두 덮개 , 가 주어졌을 때,- 만약 임의의 에 대하여, 인 를 찾을 수 있다면, 가 의 '''세분'''이라고 한다. 이를 로 적는다.
- 임의의 에 대하여, 라고 정의한다. 만약 임의의 에 대하여, 인 를 찾을 수 있다면, 가 의 '''성형 세분'''이라고 한다. 이를 라고 적는다.
세분은 덮개 집합 위의 원순서를 이룬다. 성형 세분은 추이적 관계이지만, 일반적으로 반사 관계가 아니다. 모든 성형 세분은 세분이지만, 그 역은 성립하지 않는다.
집합 의 분할 은 서로소 집합족이므로, 임의의 에 대하여
:
이다. 따라서 분할의 경우, 세분과 성형 세분은 서로 동치이다.
세분은 분할의 집합 위의 부분 순서를 이룬다. 즉, 만약 라면, 이다. 따라서, 분할의 세분 관계는 로 적을 수 있다. 세분 관계를 갖춘 분할 집합은 완비 격자를 이룬다. 즉, 임의의 분할들의 족에 대하여, 이들 모두를 세분하는 가장 엉성한 분할이 존재하며, 또한 이들 모두에 의하여 세분되는 가장 섬세한 분할이 존재한다. 구체적으로, 집합 의 임의의 분할들의 족 에 대하여,
:
는 각 분할의 원소들의 교집합들로 구성된 분할이다. 이 분할은 모든 의 세분이며, 모든 를 세분하는 임의의 분할은 이 분할의 세분이다. 또한, 집합 의 임의의 덮개 에 대하여, 인 가장 섬세한 분할 가 존재하며, 이는 다음과 같다.[12]
:
특히, 임의의 분할족 에 대하여,
:
는 분할이며, 모든 를 세분으로 갖는 분할 가운데 가장 섬세하다.
유한 집합의 분할 격자는 기하 격자를 이룬다.[11] 구체적으로, 크기 의 유한 집합 의 분할 격자는 완전 그래프 의 그래프 매트로이드의 닫힌집합 격자와 동형이다.
집합 ''X''의 분할 ''α''가 ''X''의 분할 ''ρ''의 '''세분화'''이면—즉, ''α''가 ''ρ''보다 ''세밀하다''고 말하고, ''ρ''가 ''α''보다 ''조잡하다''고 말한다면—''α''의 모든 요소가 ''ρ''의 일부 요소의 부분 집합인 경우이다. 비공식적으로, 이는 ''α''가 ''ρ''의 추가적인 분열임을 의미한다. 이 경우, ''α'' ≤ ''ρ''로 표기한다.
집합 ''X''의 분할 집합에 대한 "세밀함" 관계는 부분 순서이다. 각 요소 집합은 최소 상계("결합")와 최대 하계("만남")를 가지므로 격자를 형성하며, 더 구체적으로 (유한 집합의 분할의 경우) 기하 및 초가해 격자이다.[4][5]
분할 α와 ρ의 만남과 결합은 다음과 같이 정의된다. '''만남''' 는 ''α''의 블록과 ''ρ''의 블록의 교집합으로 구성된 분할이다(공집합 제외). 즉, 의 블록은 서로 소가 아닌 ''α''의 블록과 ''ρ''의 블록의 교집합이다. '''결합''' 를 정의하기 위해, ''A'' ~ ''B''인 경우(즉, ''A''와 ''B''가 서로 소가 아닐 경우) ''α''의 블록 ''A''와 ''ρ''의 블록 ''B''에 대한 관계를 형성한다. 그러면 는 각 블록 ''C''가 이 관계에 의해 연결된 블록족의 합집합인 분할이다.
기하 격자와 매트로이드 사이의 등가성에 기초하여, 유한 집합의 분할의 이 격자는 격자의 원자, 즉 개의 단일 집합과 하나의 2-원소 집합을 가진 분할로 구성된 매트로이드에 해당한다. 이러한 원자 분할은 완전 그래프의 변에 일대일로 대응한다. 매트로이드 폐포는 주어진 모든 원자 분할의 가장 세밀한 공통 조잡함이다. 그래프 이론 용어로, 이는 완전 그래프의 정점을 주어진 변 집합에 의해 형성된 부분 그래프의 연결 요소로 분할하는 것이다. 이러한 방식으로 분할의 격자는 완전 그래프의 그래픽 매트로이드의 플랫 격자에 해당한다.
4. 분할의 세분
집합 ''X''의 분할 ''α''가 다른 분할 ''ρ''의 '''세분'''이라는 것은, ''α''의 모든 원소가 ''ρ''의 어떤 원소의 부분 집합이라는 것을 의미한다. 이는 ''α''가 ''ρ''를 더 잘게 나눈 것임을 뜻한다. 이 경우 ''α'' ≤ ''ρ''로 표기한다.
집합 ''X''의 분할 집합에 대한 "세밀함" 관계는 부분 순서를 이룬다. 각 원소 집합은 최소 상계(결합)와 최대 하계(만남)를 가지므로 격자를 형성한다. 특히 유한 집합의 분할 격자는 기하 및 초가해 격자이다.[4][5] 4-원소 집합의 분할 격자는 15개의 원소를 가지며, 왼쪽의 하세 도표에 나타나 있다.
분할 α와 ρ의 만남과 결합은 다음과 같이 정의된다.
- '''만남''' 는 ''α''의 블록과 ''ρ''의 블록의 교집합으로 구성된 분할이다(공집합 제외). 즉, 의 블록은 서로 소가 아닌 ''α''의 블록과 ''ρ''의 블록의 교집합이다.
- '''결합''' 를 정의하기 위해, ''α''의 블록 ''A''와 ''ρ''의 블록 ''B''에 대해 ''A'' ~ ''B''인 경우(즉, ''A''와 ''B''가 서로 소가 아닐 경우)의 관계를 만든다. 그러면 는 각 블록 ''C''가 이 관계에 의해 연결된 블록족의 합집합인 분할이다.
기하 격자와 매트로이드 사이의 관계에 따르면, 유한 집합 분할 격자는 개의 단일 집합과 하나의 2-원소 집합을 가진 분할로 구성된 매트로이드에 해당한다. 이러한 원자 분할은 완전 그래프의 변과 일대일 대응된다. 매트로이드 폐포는 주어진 모든 원자 분할의 가장 세밀한 공통 조잡함이다. 그래프 이론 용어로, 이는 완전 그래프의 정점을 주어진 변 집합에 의해 형성된 부분 그래프의 연결 요소로 분할하는 것이다. 이러한 방식으로 분할 격자는 완전 그래프의 그래픽 매트로이드의 플랫 격자에 해당한다.
트럼프 카드 52장으로 이루어진 카드 덱 ''D''를 예로 들어보자. ''D''에 대한 '색깔 같음' 관계(~C)는 {빨간색 카드}와 {검은색 카드}라는 두 개의 동치류를 가진다. ~C에 해당하는 2-부분 분할은 '무늬 같음' 관계 ~S를 세분화하여 {스페이드}, {다이아몬드}, {하트}, {클럽}의 네 동치류를 생성한다.
5. 비교차 분할
'''비교차 분할'''은 집합 ''N'' = {1, 2, ..., ''n''}의 분할에서, 이에 상응하는 동치 관계 ~가 특정 성질을 만족하는 경우를 말한다. 즉, ''N''의 네 원소 ''a'', ''b'', ''c'', ''d''가 ''a'' < ''b'' < ''c'' < ''d''이고, ''a'' ~ ''c'' 및 ''b'' ~ ''d''를 만족할 때, 항상 ''a'' ~ ''b'' ~ ''c'' ~ ''d''가 성립해야 한다.
이러한 비교차 분할은 다음과 같이 시각적으로 이해할 수 있다. ''N''의 원소 1, 2, ..., ''n''을 정''n''각형의 ''n''개 정점(반시계 방향)으로 배열하고, 각 블록을 해당 원소들을 정점으로 하는 다각형으로 그린다. 이때, 이 다각형들이 서로 교차하지 않으면, 그리고 그 때에만 해당 분할은 비교차 분할이 된다.
예를 들어, 집합 ''X'' = {1, 2, 3, 4}에서 13/24는 비교차 분할이 아니다.
유한 집합의 비교차 분할은 모든 분할의 격자의 부분 집합을 형성하지만, 두 격자의 결합 연산이 일치하지 않으므로 부분 격자는 아니다.
비교차 분할 격자는 자유 확률론에서 중요한 역할을 한다.
6. 분할의 수
''n''개 원소의 집합을 분할하는 방법의 수는 벨 수이다. 처음 6개의 벨 수는 1, 1, 2, 5, 15, 52, 203이다.
벨 수는 다음과 같은 점화식을 만족한다.
:
또한, 다음과 같은 지수생성함수를 가진다.
:
벨 삼각형을 이용하여 벨 수를 계산할 수도 있다. 각 행의 첫 수는 이전 행의 마지막 수이고, 뒤따르는 수들은 왼쪽과 왼쪽 위의 수를 더한 것이다. 벨 수는 삼각형의 양옆에서 각각 차례대로 나열된다.
''n''개 원소 집합을 정확히 ''k''개의 집합으로 분할하는 방법의 수는 제2종 스털링 수이다.
''n''개 원소 집합의 비교차 분할의 개수는 카탈랑 수이다.
:
7. 예시
집합 \(\{1, 2, 3\}\)의 분할은 다음과 같이 5가지가 있다.
- \(\{\{1, 2, 3\}\}\)
- \(\{\{1\}, \{2, 3\}\}\)
- \(\{\{2\}, \{3, 1\}\}\)
- \(\{\{3\}, \{1, 2\}\}\)
- \(\{\{1\}, \{2\}, \{3\}\}\)
다음은 \(\{1, 2, 3\}\)의 분할이 아닌 예시이다.
- \(\{\emptyset, \{1, 2\}, \{3\}\}\) : 공집합을 원소로 포함하므로 분할이 아니다.
- \(\{\{1, 2\}, \{2, 3\}\}\) : 서로소가 아니므로 분할이 아니다.
- \(\{\{1\}, \{2\}\}\) : 합집합이 \(\{1, 2, 3\}\)이 아니므로 분할이 아니다.
정수는 홀수와 짝수, 또는 음수, 양수, 0으로 분류할 수 있으며, 이들은 모두 정수 집합 \(\mathbb Z\)의 분할이다.
공집합의 분할은 공집합뿐이다.
한원소 집합 \(\{x\}\)의 분할은 \(\{\{x\}\}\)뿐이다.
공집합이 아닌 집합 \(X\)에 대하여, \(\{X\}\)는 \(X\)의 분할이다.
공집합이 아닌 집합 \(X\) 및 공집합이 아닌 진부분집합 \(\varnothing \subsetneq P \subsetneq X\)에 대하여, \(\{P, X \setminus P\}\)는 \(X\)의 분할이다.
52장의 플레잉 카드 집합
:
은 색깔에 따라 2개의 집합으로 분할할 수 있다.
:
또한, 모양에 따라 4개의 집합으로 분할할 수 있다.
:
이때 모양에 따른 분할 \(\mathcal Q\)는 색깔에 따른 분할 \(\mathcal P\)의 세분이다.
참조
[1]
서적
Combinatorics: Ancient and Modern
Oxford University Press
[2]
서적
Naive Set Theory R.
https://books.google[...]
Springer
[3]
서적
Introduction to Abstract Mathematics
https://books.google[...]
Rowman & Littlefield
[4]
서적
Lattice Theory
https://books.google[...]
American Mathematical Society
[5]
서적
Semimodular Lattices. Theory and Applications
Cambridge University Press
[6]
서적
Introductory Combinatorics
Pearson Prentice Hall
[7]
서적
集合・位相入門
岩波書店
[8]
서적
Handbook of Analysis and Its Foundations
Academic Press
[9]
서적
Introduction to Abstract Mathematics
http://books.google.[...]
Rowman & Littlefield
[10]
서적 인용
Handbook of Analysis and Its Foundations
Academic Press
[11]
서적 인용
Lattice theory
American Mathematical Society
[12]
서적 인용
General topology
https://archive.org/[...]
Addison-Wesley
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com