Please enable JavaScript.

Coggle requires JavaScript to display documents.

계산할 수 없는 문제 (이 장에서 배울 내용 (이 장에서 배울 내용 (귀류법, '셀 수 있는'의 개념, 계산 할 수…

- - - - 우선 증명하고자 하는 명제의 부정이 성립한다고 가정한다.
        
        그 가정을 기본으로 증명을 진행하여 모순을 유도한다.
      - 증명하고자 하는 것의 부정을 가정하면 모순이 생긴다.
      - ex) Q. '최대 정수'라는 것은 존재하지 않는다. 왜?
        
        A. 귀류법으로 최대 정수가 없음을 증명한다. '최대 정수'가 있다고 가정하고 그 수를 M이라고 한다면 M + 1은 M 보다 크게 되기 때문에 최대정수라는 것은 존재하지 않는다.
    - - 귀류법으로 소수는 무한이 많다라는 것을 증명
        
        소수: 1과 자기 자신의 수만으로 나누어떨어지는 2 이상의 수
      - ex) Q. 소수가 무한이 많음을 증명하라
        
        A. 소수의 개수는 유한하다고 가정한다.
        
        소수를 적으면 2, 3, 5, 7, ...., P로 나타낼 수 있다.
        
        모든 소수를 곱한 다음 1을 더한 수를 Q라고 하면 Q = 2 3 5 7 ... * P + 1
        
        Q는 어떤 소수보다 크다라는 것은 Q는 소수가 아니다라는 것을 의미한다.
        
        하지만 Q는 어느 수로 나누든 나머지가 1이 남고 1과 자신만으로 나눠지므로 Q는 소수이다.
        
        따라서 귀류법에 따라 소수는 무한이 많다는 것을 증명한다.
    - - 귀류법을 할 때에는 잘못된 가정에서 시작되어야 한다.
        
        그래야 모순을 이끌어 낼 수 있기 때문이다.
- - - - 집합의 요소 개수가 한정되거나 집합의 모든 요소를 1 이상의 정수와 1 대 1로 대응할 수있다.
      - 모든 요소를 누락이나 중복없이 센다는 것
        
        1 이상의 정수와 1 대 1로 대응
    - - 유한 집합은 셀 수 있음
      - 0 이상의 짝수 전체 집합은 셀 수 있음
      - 정수 전체 집합은 셀 수 있음
      - 유리수 전체 집합은 셀 수 있음
      - 프로그램 집합은 셀 수 있음
    - - 1 이상의 정수가 대응할 수 없는 집합
        
        누락이 생기게 된다
- - - - 정수열 == 정수를 무한이 나열한 열
- - - - 프로그램으로 푸는 것이 원리적으로 불가능한 문제