집합 X 와 그 멱집합 P(X) 사이에는 1:1 대응이 존재하지 않음을 보이시오. (A 의 멱집합은 A 의 모든 부분집합을 원소로 갖는 집합)
은근히 유명한 문제니까 아는사람들은 쉿...모 수학과 교수가 만약 이걸 완전히 처음보고 답을 맞게 냈다면 그사람은 자부심을 갖고 본인은 수학에 재능이 있다고 말해도 된다고 했음.
은근히 유명한 문제니까 아는사람들은 쉿...모 수학과 교수가 만약 이걸 완전히 처음보고 답을 맞게 냈다면 그사람은 자부심을 갖고 본인은 수학에 재능이 있다고 말해도 된다고 했음.
상식적으로 X가 n개의 원소가 있으면 멱집합 가능갯수는 nC1 + nC2 + nC3 + ... != n 이니까 1:1 대응이 불가능한거 아님?;
nC0도 되나?
무한집합 말하는듯
n이 2개라도 1 + 2 + 1, 총 멱집합 갯수 4개 뜨니까 n(X) = 2 n(P(X)) = 4 3개부터는 더 심해질꺼고
멱집합 원소의 갯수는 그냥 2^n 임. 그리고 ㅁㄴ 말대로 그렇게 하면 무한집합에서 문제가 생김. 사실 저거 틀린사람들 과반수 이상이 그렇게 유한케이스만 갖고 수학적 귀납법이나 기타등등 써서 하다가 오답...
무한집합에서 뭔 문제가 생김?
이 lim (n-> inf) (2^n - n) = inf 이므로 무한집합에서도 성립 안하는거 같은데
무한집합은 뭐랄까 성질이 좀 elastic 함. 예를들어 유한집합에서는 A 랑 A 에다가 원소 하나 더 넣은거랑 때려죽어도 일대일 대응이 성립하지 않지만 무한집합인 자연수랑 자연수에다가 원소 하나 더 집어넣은거랑은 일대일 대응이 성립함. 심지어 1차원 수직선이랑 거기다가 무한개의 원소를 더한 2차원 좌표평면 사이에도 일대일 대응이 존재함.
지금 구글링 했는데 continuum hypothesis(연속체 가설)이 성립한다면, 무한집합에서 성립할수도 있는데 가설이 성립 안한다면 무한집합도 똑같이 성립 안한다네.. 근데 continuum hypothesis 를 증명, 반증할수도 없다함 지금은
즉 문제 자체 오류 ㅡㅡ
아니 그러니까 원소의 갯수로 접근하면 안되지. 그런거 모르는 이산수학에서 나온 문젠데. 힌트를 주자면 멱집합, 일대일대응 함수의 성질을 이용하는 논리문제임.
continuum hypothesis가 맞을경우 sdf 말이 맞고 continuum hypothesis가 틀린경우 내말이 맞음.. 근데 지금 누가 continuum hypothesis 자체가 증명 불가능한 명제라고 이미 증명해서 필즈상 받음. 즉, 답이 없음
수학적 귀납법은 countable한 대상에 대해서 성립하는건데 실수 집합 X에 대해서도 멱집합 P(X)와 일대일 대응이 존재하지 않음
아니 continuum hypothesis 는 aleph 0 과 aleph 1 사이에 다른 aleph 가 없다는 명제임. 이것과는 다름.
여러 가지로 무한집합의 크기는 독특하다. 자연수 집합과 정수의 집합의 크기가 같다. 전체가 부분보다 크다는 공리가 성립하지 않는다. 오죽하면 칸토어마저 신의 영역을 침범한 것이 아닐까 걱정하였을까? 칸토어는 어떤 집합의 크기는 그 집합의 멱집합의 크기보다 항상 작음을 증명하였다. |Z+|<|P(Z+)| 다시 적으면 ℵ0<2ℵ0 ℵ0과 c 사이에 기수(집합의 크기)가 존재하지 않는다는 가설이 연속체 가설이다. 다시 말하면 ℵ0<|A|<c인 집합 A가 존재하지 않는다는 가설이다.
http://ko.wikipedia.org/wiki/멱집합
그리고 연속체 가설은 aleph zero와 c 사이에 cardinality가 존재하지 않는다는 거고 연속체 가설을 인정하지 않아도 멱집합의 cardinality는 항상 원래 집합보다 큼
무한 집합의 멱집합은 비가산 집합이며, 그 크기는 |\mathcal P(S)|=2^{|S|}\ge|S|^+>|S| 이다. 여기서 2^{|S|}는 기수의 거듭 제곱이다. 여기서 |S|^+는 |S|보다 더 큰 최소의 기수이며, 만약 일반화 연속체 가설이 성립한다면 위의 부등식 \ge은 등식이 된다.
이 문제랑 아무 상관이 없다는 말임
칸토어의 원리를 아느냐 모르느냐. 이걸 혼자 생각해냈으면 수학과로 가야된다
이건 연속체 가설을 참으로 놓건 거짓으로 놓건 항상 성립하는 명제임.
무한집합의 멱집합하고 연속체 가설하고 상관관계 있는거 같은데 검색해보면
지금 너는 계속 원소의 갯수로 접근하려고 하니까 cardinality 가 튀어나오는거임.
For any infinite sets A and B, if there is an injection from A to B then there is an injection from subsets of A to subsets of B. Thus for any infinite cardinals A and B, A < B \to 2^A \le 2^B. If A and B are finite, the stronger inequality A < B \to 2^A < 2^B \! holds. GCH implies that this strict, stronger inequality holds for infinite cardinals as well as finite cardinals.
http://en.wikipedia.org/wiki/Continuum_hypothesis
아니.. 원소의 갯수가 무한일때 연속체 가설이 참이면 2^n = n 이 되고 연속체 가설이 거짓이면 2^n > n이래잖아
아니 뭘 말하려는건지 알고있는데 그게 다 필요없이 단순한 논리로 증명이 되는거라니깐...
Cantor's diagonal argument shows that the power set of a set (whether infinite or not) always has strictly higher cardinality than the set itself (informally the power set must be larger than the original set). 답떳다
아니네 잠깐 문제를 오해했엉
거기 쓰여있는건 A < B이면 2^A ≤ 2^B라는 거고 여기선 A < 2^A를 말하는 거잖아. 연속체 가설은 A < X < 2^A인 X가 없다는 거고
이 문제 증명은 diagonal argument 와도 사실 상관이 없음.
아니 A랜다. aleph_0 < X < 2^aleph_0가 없다는 거
암튼, ordinal, cardinal 개념이 등장하기 이전에 나오는 문제임. 집합의 갯수가지고 접근할게 아님.
근데 이산수학을 배운적이 없어서 이해하기 힘드네
뭐 이산수학에서 나온 문제라지만 이산수학이랑도 별 관련은 없음. 사실상 사용하는게 멱집합의 성질(부분집합을 원소로 갖음.), 1:1 대응 함수(injective, surjective)의 성질 이 2개정도임. 그래서 푸는데 요구되는 지식은 거의 없는데, 아주 기발한 방식으로 풀리는 문제라...ㅎㅎ
http://en.wikipedia.org/wiki/Cantor's_theorem
여기서 A detailed explanation of the proof when X is countably infinite 이거임?
궁금한데 답 안보고 버텨봐야지...
전에 어디서 읽은거 같긴 한데 기억이 전혀 안남
맞음 그 위쪽 proof 파트.
러셀의 역설이랑 비슷하게 아주 단순한 논리만으로 증명이 되는 떡밥문제. 어떤 프랑스인 교수의 이산수학 1번문제였음. - _-;
추상대수 섹션0 에 나오는 연습문제 가지고 질질싸고있네