set

수학에서 집합은 특정 조건을 만족하는 서로 다른 원소들의 모임으로 정의된다. 집합을 구성하는 각각의 대상이 원소이며, 집합의 가장 기본적인 성질은 원소의 중복을 허용하지 않고 원소들 사이에 순서가 없다는 점이다.

집합을 표기하는 방법에는 크게 원소나열법과 조건제시법이 있다. 원소나열법은 집합의 모든 원소를 중괄호 {} 안에 쉼표로 구분하여 나열하는 방식이다. 예를 들어, 1, 2, 3이라는 세 개의 원소로 이루어진 집합은 {1, 2, 3}으로 표기한다. 조건제시법은 집합에 속하는 원소가 만족해야 하는 조건을 명시하여 표기하는 방식으로, {x | x가 만족하는 조건}의 형태를 가진다.

집합은 일반적으로 대문자 A, B, C 등으로 나타내고, 원소는 소문자 a, b, c 등으로 나타낸다. 어떤 원소 a가 집합 A에 속하는 것은 기호 ∈를 사용하여 a ∈ A로 표현한다. 반대로, 원소 a가 집합 A에 속하지 않을 때는 a ∉ A로 표현한다. 이러한 포함 관계는 집합론의 가장 기본적인 관계이다.

빈 집합은 원소를 하나도 포함하지 않는 집합으로, 기호 ∅ 또는 {}로 표기한다. 또한, 집합의 원소 개수, 즉 집합의 크기는 |A|와 같이 절댓값 기호를 사용하여 나타낸다.

집합 간에는 여러 기본적인 연산이 정의된다. 가장 대표적인 연산으로는 합집합, 교집합, 차집합, 대칭차집합이 있으며, 이들은 두 개 이상의 집합으로부터 새로운 집합을 만들어낸다.

합집합은 두 집합 A와 B 중 적어도 하나에 속하는 모든 원소들의 집합이다. 기호로는 A ∪ B로 표기한다. 교집합은 두 집합 A와 B 모두에 속하는 원소들의 집합이며, A ∩ B로 나타낸다. 차집합은 한 집합에는 속하지만 다른 집합에는 속하지 않는 원소들의 집합으로, A에서 B를 뺀 차집합은 A \ B 또는 A - B로 표기한다. 대칭차집합은 두 집합 중 정확히 하나에만 속하는 원소들의 집합이며, A △ B로 나타낸다.

또한, 특정 전체집합 U를 기준으로 한 여집합 연산도 중요하다. 집합 A의 여집합은 전체집합 U에는 속하지만 A에는 속하지 않는 모든 원소의 집합이며, A^c, A', 또는 ∁U A 등으로 표기한다. 이들 연산은 드 모르간의 법칙과 같은 여러 유용한 항등식을 만족시킨다.

집합의 연산은 논리학의 명제 연산과 직접적으로 대응된다. 예를 들어, 합집합은 논리합(OR)에, 교집합은 논리곱(AND)에, 여집합은 부정(NOT)에 해당한다. 이러한 관계는 불 대수의 개념을 집합론에 적용하는 기초가 된다.

수학에서 다루는 집합은 그 성질에 따라 여러 종류로 구분된다. 가장 기본적인 분류는 집합이 포함하는 원소의 개수에 따른 것이다. 유한개의 원소로 이루어진 집합을 유한집합이라 한다. 반면 원소의 개수가 무한한 집합을 무한집합이라고 하며, 자연수의 집합이나 실수의 집합이 대표적인 예이다. 특히 원소가 하나도 없는 집합을 공집합이라고 하며, 기호로는 ∅ 또는 {}로 표기한다.

집합들 사이의 관계를 통해 정의되는 특별한 집합들도 있다. 어떤 집합의 모든 원소를 포함하는 더 큰 집합을 전체집합이라고 하며, 논의의 맥락에서 정해진다. 주어진 집합의 원소가 아닌 모든 것들의 집합을 여집합이라고 정의한다. 또한, 두 집합 사이에 일대일 대응이 존재할 때, 즉 두 집합의 원소 개수가 같을 때를 대등하다고 하며, 이는 무한집합의 크기를 비교하는 기수 개념의 기초가 된다.

집합의 원소가 특정한 구조를 가질 때 그 집합의 이름이 붙기도 한다. 예를 들어, 수만을 원소로 갖는 집합을 수집합이라고 부르며, 정수 집합, 유리수 집합, 실수 집합, 복소수 집합 등이 여기에 속한다. 점이나 선, 면 등의 기하학적 객체들로 이루어진 집합은 점집합이라고 불리기도 한다.

컴퓨터 과학에서 추상 데이터 타입으로서의 집합은 수학적 집합의 핵심 성질을 모델링한 데이터 구조이다. 이는 원소의 중복을 허용하지 않고, 원소 간 순서가 없으며, 주어진 원소가 집합에 속하는지 여부를 효율적으로 확인할 수 있는 연산을 제공하는 것을 특징으로 한다. 이러한 추상화는 데이터의 고유성 검사나 멤버십 테스트가 필요한 다양한 알고리즘과 응용 프로그램에서 광범위하게 활용된다.

집합 추상 데이터 타입이 제공하는 주요 연산으로는 원소 추가(add 또는 insert), 원소 삭제(remove 또는 delete), 그리고 특정 원소의 멤버십 확인(contains 또는 in)이 있다. 또한 수학적 집합 연산인 합집합(union), 교집합(intersection), 차집합(difference), 그리고 한 집합이 다른 집합의 부분집합(subset)인지 판별하는 연산도 포함되는 경우가 많다. 이러한 연산들은 내부 구현 방식과 무관하게 일관된 인터페이스를 통해 사용자에게 제공된다.

이 추상 데이터 타입의 구체적인 구현 방식은 성능 요구사항에 따라 달라진다. 대표적으로 해시 테이블을 기반으로 한 해시 세트는 원소의 추가, 삭제, 탐색 연산을 평균적으로 상수 시간에 수행할 수 있어 가장 일반적으로 사용된다. 반면, 이진 탐색 트리를 이용한 구현은 원소들을 정렬된 상태로 유지할 수 있는 장점이 있다. 프로그래밍 언어의 표준 라이브러리에는 이러한 추상 데이터 타입의 구현체가 포함되어 있으며, 예를 들어 파이썬의 set, 자바의 HashSet과 TreeSet 등이 있다.

컴퓨터 과학에서 집합이라는 추상 데이터 타입을 구현하는 일반적인 방법은 해시 테이블을 기반으로 하는 해시 세트이다. 해시 세트는 각 원소를 해시 함수를 사용하여 고유한 인덱스로 변환하고, 이 인덱스를 통해 버킷 배열에서 해당 원소의 존재 여부를 빠르게 확인한다. 이 방식은 원소의 추가, 삭제, 그리고 특정 원소의 포함 여부를 확인하는 연산을 평균적으로 상수 시간에 수행할 수 있게 해준다. 그러나 해시 함수의 충돌이나 부하 인자가 높아지면 성능이 저하될 수 있으며, 원소들 사이에 명시적인 순서를 유지하지 않는다는 특징이 있다.

순서가 중요하거나 원소들을 정렬된 상태로 유지해야 하는 경우에는 이진 탐색 트리를 기반으로 하는 트리 세트를 사용한다. 대표적으로 레드-블랙 트리나 AVL 트리와 같은 자가 균형 이진 탐색 트리가 활용되어, 원소들을 항상 정렬된 상태로 저장한다. 이 구현 방식은 원소의 추가, 삭제, 탐색 연산을 로그 시간에 수행하며, 정렬된 순서로 원소들을 순회하는 것이 가능하다. 따라서 원소의 범위 검색이나 최솟값/최댓값 찾기와 같은 연산이 필요한 경우에 유용하다.

구현 방식의 선택은 애플리케이션의 요구사항에 따라 달라진다. 빠른 검색과 순서가 중요하지 않은 경우에는 해시 세트가 일반적이며, 자바의 HashSet이나 파이썬의 내장 set 타입이 이에 해당한다. 반면에 정렬된 데이터가 필요하거나 순서에 따른 연산이 빈번한 경우에는 트리 세트를 사용하며, 자바의 TreeSet이 대표적인 예이다. 각 구현체는 내부적으로 메모리 사용량, 연산의 시간 복잡도, 그리고 스레드 안전성 등의 다른 특성들도 가지고 있다.

파이썬의 set은 수학의 집합 개념을 구현한 내장 데이터 타입이다. 파이썬 2.4 버전부터 도입되었으며, 가변 객체로서 중괄호 {}를 사용하여 생성하거나 set() 생성자를 통해 빈 집합을 만들 수 있다. 파이썬 set의 가장 큰 특징은 수학적 집합과 마찬가지로 중복된 원소를 허용하지 않으며, 원소 간의 순서를 보장하지 않는다는 점이다. 이러한 특성 덕분에 리스트나 튜플에서 중복 항목을 제거하는 용도로 자주 활용된다.

파이썬 set은 합집합, 교집합, 차집합, 대칭차집합과 같은 기본적인 집합 연산을 지원한다. 각각 |, &, -, ^ 연산자로 표현할 수 있으며, union(), intersection(), difference(), symmetric_difference() 메서드로도 동일한 연산이 가능하다. 또한 한 집합이 다른 집합의 부분집합 또는 진부분집합인지 확인하는 issubset(), issuperset() 메서드와, 두 집합이 서로소인지 판별하는 isdisjoint() 메서드도 제공한다.

파이썬 set은 해시 테이블을 기반으로 구현되어 있어, 원소의 추가(add()), 제거(remove(), discard()), 포함 여부 확인(in 연산자) 등의 연산이 평균적으로 상수 시간(O(1))에 이루어진다. 이는 리스트에서의 포함 여부 확인이 선형 시간(O(n))이 걸리는 것에 비해 큰 장점이다. 단, set에 저장할 수 있는 원소는 해시 가능 객체여야 하므로, 가변 객체인 리스트나 다른 set은 원소로 포함시킬 수 없다. 대신 불변 객체인 튜플은 원소로 사용 가능하다.

파이썬에는 frozenset이라는 불변 집합 타입도 존재한다. frozenset은 생성 후 내용을 변경할 수 없으며, 해시 가능하기 때문에 다른 set이나 사전의 키로 사용될 수 있다는 특징이 있다. 이는 set 자체는 가변이므로 다른 set의 원소나 사전의 키가 될 수 없는 점과 대비된다.

자바에서는 컬렉션 프레임워크의 일부로 집합을 다루기 위한 Set 인터페이스를 제공한다. Set 인터페이스는 수학적 집합의 핵심 성질인 원소의 중복을 허용하지 않으며, 원소 간 순서를 보장하지 않는 특성을 가진다. 이 인터페이스의 대표적인 구현 클래스로는 HashSet과 TreeSet이 있다.

HashSet 클래스는 해시 테이블을 기반으로 구현되어 있다. 원소의 저장, 검색, 삭제 연산이 평균적으로 매우 빠른 상수 시간(O(1))에 수행되는 것이 특징이다. 그러나 원소들이 추가된 순서나 특정 정렬 순서를 전혀 유지하지 않는다. HashSet은 내부적으로 각 원소의 해시 코드를 사용하므로, 저장할 객체에 대해 equals()와 hashCode() 메서드가 적절히 오버라이드되어 있어야 올바르게 동작한다.

반면에 TreeSet 클래스는 레드-블랙 트리라는 자가 균형 이진 탐색 트리를 기반으로 구현된다. 따라서 원소들이 자동으로 정렬된 상태를 유지한다는 점이 HashSet과의 가장 큰 차이점이다. 기본적으로는 자연 순서(Comparable 인터페이스)에 따라 정렬되며, 생성 시 컴퍼레이터를 제공하여 사용자 정의 정렬 순서를 지정할 수도 있다. 이로 인해 원소의 추가, 검색, 삭제 연산의 시간 복잡도는 O(log n)이다.

두 구현체의 선택은 애플리케이션의 요구사항에 따라 달라진다. 순서가 중요하지 않고 최고의 성능이 필요할 때는 HashSet이 일반적이며, 원소들이 정렬된 상태로 유지되어야 하거나 범위 검색(예: 부분 집합 추출)이 필요할 때는 TreeSet이 더 적합하다. 두 클래스 모두 Set 인터페이스를 구현하므로, 중복된 원소의 추가 시도는 무시된다는 공통점을 가진다.

공리적 집합론은 집합을 다루는 수학적 이론의 기초를 엄밀한 논리 체계 위에 세우기 위한 접근법이다. 이는 집합론의 근본 개념과 연산을 몇 가지 기본적인 공리로부터 출발하여 체계적으로 유도하고, 모순 없이 전개하는 것을 목표로 한다. 이러한 공리적 접근은 러셀의 역설과 같은 역설로 인한 기존 소박한 집합론의 한계를 극복하기 위해 발전했다.

가장 널리 사용되는 공리계는 체르멜로-프렝켈 집합론으로, 약칭 ZF 또는 선택 공리를 추가한 ZFC로 불린다. 이 공리계는 공집합의 존재, 쌍집합의 형성, 합집합과 멱집합의 구성, 그리고 무한 공리 등을 포함하여 집합의 기본적 성질을 규정한다. 특히 선택 공리는 무한한 집합들로부터 원소를 선택하는 것이 항상 가능함을 주장하는 논쟁적인 공리로, ZFC 체계의 핵심을 이룬다.

공리적 집합론은 수학 기초론의 근간을 제공하며, 모든 수학적 객체를 집합으로 구성할 수 있는 토대가 된다. 예를 들어, 자연수는 공집합을 0으로 정의하고, 그 후속자를 특정 방식의 집합으로 정의하는 폰 노이만 순서수 구성 등을 통해 집합론 내에서 엄밀하게 정의된다. 이는 실수 체계나 함수와 같은 더 복잡한 개념들도 궁극적으로 집합론의 언어로 환원될 수 있음을 의미한다.

집합 개념의 역사는 고대 그리스의 철학자와 수학자들까지 거슬러 올라간다. 유클리드의 저작에서도 기하학적 대상들을 모음으로 다루는 초기 형태가 나타나지만, 현대적 의미의 집합론은 19세기 말 게오르크 칸토어에 의해 창시되었다. 그는 실수의 집합과 자연수의 집합의 크기를 비교하는 연구를 통해 무한 집합의 이론을 체계화했으며, 이는 수학의 기초를 재정립하는 계기가 되었다.

그러나 칸토어의 이론은 러셀의 역설과 같은 모순을 내포하고 있음이 발견되면서 위기를 맞았다. 이는 스스로를 원소로 포함하지 않는 모든 집합의 집합을 생각할 때 발생하는 논리적 문제였다. 이러한 모순을 해결하기 위해 20세기 초 여러 수학자들이 공리적 집합론 체계를 제안했다. 가장 널리 받아들여진 체계는 체르멜로와 프렝켈이 정립한 ZFC 공리계이다.

집합론의 발전은 현대 수학 전체에 지대한 영향을 미쳤다. 거의 모든 수학적 구조—수, 함수, 공간—가 집합을 기초로 정의될 수 있게 되었으며, 이로 인해 집합론은 수학의 기초를 제공하는 언어이자 틀로 자리 잡았다. 또한 집합의 개념은 컴퓨터 과학의 자료 구조 이론과 데이터베이스의 관계 대수 등 여러 분야로 확장되어 적용되고 있다.

원소(element)는 집합을 구성하는 개별적인 대상이다. 집합은 이러한 원소들의 모임으로 정의되며, 집합과 원소 사이의 관계는 소속 관계라고 한다. 원소가 특정 집합에 속한다는 것은 그 집합의 정의나 조건을 만족함을 의미한다. 예를 들어, 자연수 집합의 원소는 1, 2, 3 등이다.

원소와 집합의 관계는 기호로 명확히 표현된다. 어떤 원소 *a*가 집합 *A*에 속할 때는 *a* ∈ *A*로 표기하고, 속하지 않을 때는 *a* ∉ *A*로 표기한다. 집합을 표기하는 방법 중 하나는 이 원소들을 직접 중괄호 안에 나열하는 원소 나열법이다. 예를 들어, 1, 2, 3이라는 세 원소로 이루어진 집합은 {1, 2, 3}으로 쓴다.

집합의 핵심 성질은 원소의 중복을 허용하지 않는다는 점과 원소 간에 순서가 없다는 점이다. 따라서 집합 {1, 2, 3}과 {3, 2, 1, 2}는 동일한 집합으로 간주된다. 후자의 표기에서 원소 2가 두 번 나열되었고 순서가 다르지만, 중복은 무시되며 순서는 중요하지 않기 때문이다.

원소의 개념은 집합론의 기초를 이루며, 부분집합, 합집합, 교집합과 같은 모든 집합 연산과 개념의 기본 단위가 된다. 또한, 원소가 하나도 없는 집합을 공집합이라고 한다.

부분집합은 한 집합의 모든 원소가 다른 집합에도 포함되는 관계를 말한다. 집합 A의 모든 원소가 집합 B의 원소일 때, A는 B의 부분집합이라고 하며, 기호로 A ⊆ B로 나타낸다. 예를 들어, 집합 A = {1, 2}이고 집합 B = {1, 2, 3}이라면, A의 원소 1과 2는 모두 B에 속하므로 A ⊆ B가 성립한다. 만약 A가 B의 부분집합이지만, B의 모든 원소를 A가 가지고 있지는 않을 때, 즉 A와 B가 정확히 같지 않을 때, A를 B의 진부분집합이라고 하며 A ⊂ B로 표기하기도 한다.

부분집합의 개념은 집합의 포함 관계를 논리적으로 정의하는 데 필수적이다. 모든 집합은 자기 자신의 부분집합이며, 공집합은 어떤 집합의 부분집합이 된다. 부분집합의 관계는 추이성을 가진다. 즉, A ⊆ B이고 B ⊆ C이면, A ⊆ C가 성립한다. 이 관계는 집합들을 비교하고 분류하는 데 널리 사용되며, 수학의 여러 분야와 컴퓨터 과학의 알고리즘 분석, 데이터베이스의 관계 모델 등에서 기초가 된다.

부분집합을 판별하거나 나열하는 것은 조합론의 중요한 주제이다. 유한집합의 경우, 원소의 개수가 n개이면, 가능한 모든 부분집합의 개수는 2^n개이다. 이는 각 원소마다 부분집합에 포함되거나 포함되지 않는 두 가지 선택지가 있기 때문이다. 이러한 모든 부분집합의 모임을 원래 집합의 멱집합이라고 부른다. 부분집합의 개념은 더 나아가 합집합, 교집합, 차집합과 같은 다양한 집합 연산과 깊이 연관되어 있다.

합집합, 교집합, 차집합은 두 개 이상의 집합에 대해 정의되는 기본적인 집합 연산이다. 이 연산들은 새로운 집합을 생성하며, 논리학의 논리합, 논리곱, 차등과 각각 대응되는 개념이다.

합집합은 주어진 집합들 중 적어도 하나에 속하는 모든 원소들로 구성된 집합이다. 두 집합 A와 B의 합집합은 A ∪ B로 표기하며, "A 합집합 B"라고 읽는다. 예를 들어, A = {1, 2, 3}이고 B = {3, 4, 5}라면, A ∪ B = {1, 2, 3, 4, 5}가 된다. 교집합은 주어진 모든 집합에 공통으로 속하는 원소들로 구성된 집합이다. 두 집합 A와 B의 교집합은 A ∩ B로 표기하며, "A 교집합 B"라고 읽는다. 앞선 예에서 A ∩ B = {3}이다. 만약 공통된 원소가 없다면, 그 교집합은 공집합(∅)이 된다.

차집합은 한 집합에는 속하지만 다른 집합에는 속하지 않는 원소들로 구성된 집합이다. 집합 A에 대한 B의 차집합은 A \ B 또는 A - B로 표기하며, "A 차집합 B"라고 읽는다. 이는 A에 속하는 원소 중에서 B에도 속하는 원소들을 제외한 나머지 원소들의 집합을 의미한다. 앞선 예에서 A \ B = {1, 2}이고, B \ A = {4, 5}가 된다. 대칭차집합은 두 집합의 합집합에서 교집합을 뺀, 즉 (A \ B) ∪ (B \ A)로 정의되는 연산으로, 두 집합 중 오직 하나에만 속하는 원소들의 집합이다.

이러한 기본 연산들은 드 모르간의 법칙과 같은 중요한 집합의 항등식을 구성하며, 집합론의 기초를 이룬다. 또한 불린 대수와 직접적으로 연결되어 컴퓨터 과학의 논리 회로 설계나 데이터베이스의 쿼리 처리, 그리고 여러 프로그래밍 언어에서 자료구조로 구현된 세트의 연산 기능 근간이 된다.