부분집합의 개수 증명 - bubunjibhab-ui gaesu jeungmyeong

집합을 배우고 나면 원소의 개수가 n개인 집합의 부분집합의 개수는 2ⁿ인 것을 알고 계실겁니다.

하지만 왜 그럴까 진지하게 고민해본 사람은 별로 없습니다. 다만, 원소가 1개일 때 부분집합은 2개, 2개일 때 4개, 3개일 때 8개, ... 이렇게 변하는 것을 보고 아~ 그래서 2ⁿ개구나 하고 유추해 볼 뿐.

물로 이런 유추에 착안하여 수학적 귀납법이란 방법으로 손쉽게 이것을 증명할 수 있습니다.

하지만 집합을 배우는 과정은 수학적 귀납법을 배우기보다 훨씬 이전의 과정입니다.

그래서 여기서는 수학적 귀납법이 아닌 다른 방법 그 이전에 가능한 방법으로 접근해보려 합니다.

여기서 가장 중요한 점은 원소가 1개 늘어날 때 부분집합의 개수는 왜 2배가 되는지를 밝히는 것입니다. 따라서 거기에 중점을 두고 증명해보려 합니다.

원소의 갯수가 n개인 집합 A가 있다고 합시다. 그리고 A의 부분집합의 개수를 m개라 합시다.

이제 A에 a라는 원소가 하나 추가된 집합을 B라 합시다.

B의 모든 부분 집합을 두 부류로 나누어 봅시다.

하나는 a를 포함하지 않는 부분집합들, 다른 하나는 a를 포함하는 부분집합들.

이 둘은 어떤 관계가 있을까요. 서로 개수가 같다는 것을 눈치챌 수 있겠습니까?

a를 포함하지 않는 부분집합 각각에 a를 집어 넣으면 곧 a를 포함하는 부분집합이 됩니다.

이는 곧 두 부류가 1:1의 비율로 존재함을 뜻합니다. 결국 서로 개수가 같다는 뜻입니다.

자, 이제 a를 포함하지 않는 B의 부분집합들에 집중해봅시다.

이것은 a라는 원소가 추가되기 전, 즉 A의 부분집합들과 같습니다. 따라서 그 개수는 m개입니다.

그런데 앞서 내린 결론에서 두 부류의 갯수가 동일하므로 결국 두 부류의 합은 m+m=2m으로

B의 부분집합의 개수는 2m개 입니다.

즉, 원소 하나가 추가되면 그 집합의 부분 집합의 개수는 2배가 된다는 것이 증명되었습니다.

원소의 개수가 0개일 때 부분집합의 개수는 1개이므로 1을 초기값으로 취하면

원소의 개수가 n개인 부분집합의 개수는 1*2ⁿ=2ⁿ 이라는 결론이 도출 됩니다.

이 외에 또 다른 접근도 가능합니다. 경우의 수를 활용하는 방법이라 매우 쉽습니다.

원소 하나의 입장에서 볼 때, 부분집합에 대해 그 원소가 취할 수 있는 경우는 항상 두 가지 입니다.

구체적으로 포함되는 경우와 포함되지 않는 경우의 두 가지 입니다.

따라서 어떤 집합의 부분집합을 만들 때, 각 원소에 대해 2가지 경우의 수가 존재하므로 부분집합의 개수는 각 원소가 갖는 경우의 수인 2를 모두 곱해서 구할 수 있습니다. 즉, 원소의 갯수만큼 2를 곱한 값이 곧 부분집합의 개수가 되는 것입니다.

역시 알고 보면 참 쉽습니다.

수학 유도과정을 알아야 하는 이유

고1집합, 부분집합의 개수, 집합공식

#고1집합 #부분집합의개수 #집합공식

​

수학공식 유도과정 꼭 알아야 하나요?

안녕하세요, 수학강사 정진우입니다.

오늘은 유도과정 공부의 중요성을 고1집합 단원에 나오는 부분집합의 개수 공식을 통해 알아보도록 하겠습니다.

​

항상 강조하지만

공식이 나오기까지의 유도과정은 정말 중요합니다.

​

유도과정을 알면 얼마나 기억에 오래 남고, 여러 응용이 가능한지 알아보도록 하죠.

고등학교 1학년 때 배우는 ‘집합과 명제’ 단원에서는 부분집합의 개수를 구하는 공식(집합공식)을 배웁니다.

​

​

예를 들어 집합 A={a,b,c} 일 때, 원소의 개수는 a,b,c 총 3개이므로 위 공식에 n=3을 대입하면 부분집합의 개수는 2^3=8 개가 됩니다.

이 공식의 유도과정은 아주 쉬우니 천천히 같이 보도록 합시다.

​

집합 A의 부분집합은 각 원소 a,b,c가 있거나 없거나 둘 중 하나입니다.

따라서 간단하게 표로 그려볼 수 있습니다.

​

원소 a는 있거나(O) 없거나(X) 2가지의 경우의 수를 갖고, 원소 b도 있거나, 없거나 2가지의 경우의 수를 가지며, 원소 c도 2가지의 경우의 수를 갖습니다.

따라서 각각의 경우를 고려하면 총 2x2x2=8 개의 부분집합을 가질 수 있어요.

​

이 유도과정을 이해하고 스스로 연습했다면 다음의 문제를 쉽게 풀 수 있습니다.

Q1) 집합 A={a,b,c}일 때, 원소 a를 반드시 포함하는 부분집합의 개수는 몇 개인가?

Q2) 집합 A={a,b,c}일 때, 원소 a를 반드시 포함하고, 원소 b는 포함하지 않는 부분집합의 개수는 몇 개인가?

만약 유도과정을 이해하지 않고 결과 공식만 외웠다면

어? 부분집합의 개수 공식은 2^n 인데, n에 몇을 넣어야 하는 거지?

라고 생각하며 혼란에 빠질 수 있습니다.

​

반면 유도과정을 이해하고 직접 유도해 본 학생이라면

​

부분집합의 개수는 포함하는 경우와 안 하는 경우 2가지로 나뉘어서 2^n이었지. 표로 정리하면 쉽겠다.

라고 생각하며 변형된 문제도 거리낌 없이 대처할 수 있어요.

​

실제 풀이 과정은 아래와 같습니다.

Q1) 집합 A={a,b,c}일 때, 원소 a를 반드시 포함하는 부분집합의 개수는 몇 개인가?

원소 a는 반드시 포함해야 하므로 1가지의 경우의 수를 갖고, 원소 b는 있거나, 없거나 2가지의 경우의 수를 가지며, 원소 c도 2가지의 경우의 수를 갖습니다.

따라서 각각의 경우를 고려하면 총 1x2x2=4개의 부분집합을 가질 수 있습니다.

Q2) 집합 A={a,b,c}일 때, 원소 a를 반드시 포함하고, 원소 b는 포함하지 않는 부분집합의 개수는 몇 개인가?

원소 a는 반드시 포함해야 하므로 1가지의 경우의 수를 갖고, 원소 b는 반드시 포함하지 않아야 하므로 1가지의 경우의 수를 가지며, 원소 c는 2가지의 경우의 수를 갖습니다.

따라서 각각의 경우를 고려하면 총 1x1x2=2개의 부분집합을 가질 수 있습니다.

위 두 문제의 풀이 방법 아이디어는 부분집합 개수 공식의 유도과정입니다.

이처럼 공식이 유도되는 과정을 스스로 연습하고 익힌다면 변형된 문제나 고난도 문제를 푸는 데 소중한 수학적 도구를 장착하는 것과 같습니다.

모든 수학 문제는 개념에서 설명된

약속만 가지고도 풀어낼 수 있어요.

다만 공식은 중간 과정에서 소요되는 복잡한 계산을 간편하게 해주는 도구일 뿐입니다.

​

이제는 제발 공식 암기의 집착에서 벗어나도록 합시다.

눈앞에 있는 공식이 탄생하게 된 과정을 샅샅이 찾아내 보세요.

더 이상 ‘왜?’라는 질문이 나오지 않을 만큼 학습하고, 다른 사람에게 설명할 수 있는 수준을 만들어 봅시다.

​

공식의 유도과정을 비롯한 개념 공부를 하나씩 체화하다 보면 고난도 문제를 풀기 위한 수학적 재료가 어느새 차곡차곡 쌓여 있을 것입니다.

​

​

[수학공부법] 집합공식, 고1집합, 부분집합의 개수

​

유도과정 = 고난도 문제를 풀기 위한 수학적 재료