자연수 전체의 집합의 모든 부분집합을 원소로 갖는
N의 멱집합 2^N과
N에서 {0,1}로가는 모든 함수를 원소로 갖는 집합 X 사이에
전단사함수가 존재한다. 이거 주저리주저리 서술하는거말고 짦게 단박에 증명하는 법 없음? 하긴했는데 너무거추장스럽게긴느낌이라 그냥 당연한 수준의?그런거같은데 너무돌아가면서한거같음
- dc official App
자연수 전체의 집합의 모든 부분집합을 원소로 갖는
N의 멱집합 2^N과
N에서 {0,1}로가는 모든 함수를 원소로 갖는 집합 X 사이에
전단사함수가 존재한다. 이거 주저리주저리 서술하는거말고 짦게 단박에 증명하는 법 없음? 하긴했는데 너무거추장스럽게긴느낌이라 그냥 당연한 수준의?그런거같은데 너무돌아가면서한거같음
2^N의 원소 M(=N의 부분집합)을 X의 원소 1_M(M에서는 1, M의 여집합에서는 0으로 가는 함수)로 보내는 함수를 생각합시다
그렇게했는데 이게최선이었어?? - dc App
자연수번째 자릿수가 0 혹은 1인 수는 2진수임 + 어떤 2진수를 골라도 자연수임
2^N 의 원소인 N={0,1,2,...} 의 부분집합 A를 결정하는 것은 결국 0,1,2,.... 중 어떤 놈이 A의 원소냐는 거잖음.
N->{0,1} 인 함수를 이렇게 생각해보셈. 자연수마다 버튼이 있는데, 0이면 버튼이 안눌려있는거고 1이면 버튼이 눌려있는거임.
이거 내가 처음에 이렇게생각했는데 서술을 그냥 이대로 끝내놔도 되는건가?해서.. "자연수집합의 임의의부분집합 N은 저런식으로 대응되니 전단사다"..만 해도 되는건지? 대응이 다 된다고 해서 "전단사"는 아니니까. 느낌은 저함수를 채택하는것과 자연수집합의부분집합을 만드는게 완전히같은행위니까 전단사일거다 지만 이걸 서술하는게 좀 거칠어지더라 - dc App
내가 한 걸 보여줄까?잠시만 - dc App
본문에추가함 - dc App
AㄷN을 결정하기 위해서는 어떤 자연수가 A의 원소인지 파악해야함. 버튼이 눌려있는 자연수가 A의 원소이고, 안눌려있는 자연수는 A의 원소가 아니라고 생각해보셈. 그럼 직관적으로 이해 갈거임. 버튼이 눌려있는 양상만 보더라도 A에 무슨 원소가 들어있고 안들어있는지 알 수 있으니까 결국 A든, 자연수가 눌려있는 버튼(= 함수 f:N->{0,1}) 이든 표현방법만 다를 뿐 동일한 본질을 가르키고 있는거지
ㅇㅇ 그니깐 완전히같은행위다.는건 확실하게느낌이 맞게와서 그리했는데 이걸 설명을 해줘야 엄밀한증명이라할수잇지않나해서 가 궁금해서 본문처럼한거엿거든 근데 설명안해도 엄밀한가? - dc App
아직 다보진 않았는데 너가 쓴게 다 맞아보임. 그냥 글의 가독성이 떨어지는게 문제인거 같음
ㄱㄷ
근데 저기서 내가 설명한방식면 A->h가 단사 h->A가 단사라 베른슈타인정리가 필요한건가? - dc App
아아니다. 처음에 단사 규명 그후 전사규명이라 베른슈타인정리안써도되겟네 - dc App
다음의 전단사함수 g:2^N -> {0,1}^N 가 존재함을 보이면 충분하다. N의 멱집합 2^N 의 원소 A 가 주어졌다고 가정하자. 이 A에 대해 다음의 함수 h_A:N->{0,1} 을 정의하자. h_A (n)= 어쩌구저쩌구
이때, g:2^N -> {0,1}^N 를 정의하자. g(A)=h_A 위 함수 h_A는 각 AㄷN 에 대해 유일하게 존재한다(이건 증명필요) 따라서 g는 함수이다.
반대로 h:N->{0,1} 이 주어졌을 때 다음의 집합 A_hㄷN 를 정의하자 A_h= 어쩌구저쩌구 마찬가지로 A_h 는 주어진 h에 대해 유일하게 존재한다(이것도 증명필요) 따라서 다음과 같이 정의된 함수 f:{0,1}^N -> 2^N 은 함수이다. f(h)=A_h
마지막으로 f와 g는 역함수관계이다.(증명필요) 따라서 g가 전단사함수임을 보였다.
이런식으로 쓰는게 깔끔할듯
아 그 '증명필요' 부분을 증명하면 f,g는 함수일뿐만 아니라 단사라고 말해줘야 정확하겠네
결국 g라는 함수를 잘 정의하고, 그 g가 함수이고, 단사이고, 전사임을 보여야하잖음? 그 과정 하나하나를 잘게 쪼개서 내가 방금 한게 뭔지 바로바로 설명한다는 느낌으로 써나가면 읽을때 편함. 솔직히 너가 쓴 부분에서 틀린건 없음.
이게 수학적 서술 처음하는거다보니 아직 주먹구구로되는경향이있다 생각한걸 그대로써내갈려는거도 몇시간걸리고그럼 - dc App
ㅇㅇ 맞음 수학적 글쓰기가 꽤 어려움 어떤 논증을 적어내려가야 하는지는 직관적으로 알겠는데 다쓰고 읽어보면 내가 뭐라고 썼는질 하나도 모르겠어서 다시쓰고 나도 맨날그럼
그렇다고 대충 넘어갈수도 없는게 논리적으로 완벽하려고 계속 검토하다보면 내가 진짜 빠뜨린 치명적인 논리적 갭이 보일때가 있음. 그런거 채워가는게 실력향상에 도ㅗ움이 많이 됨