'모든 사람은 때때로 어떤 사람을 좋아한다'를 형식문법 wff(well formed fomula)로 표현해보자




  '때때로'는 '어떤 시간'이라고 해석할 수 있다.


그럼 '모든 사람은 때때로 어떤 사람을 좋아한다'의 부정은 무엇일까?

서술만 놓고보면 헷갈린다. 논리적으로 접근해보자.





따라서 '모든 사람은 때때로 어떤 사람을 좋아한다'의 부정은

'어떤 사람은 항상 모든 사람을 좋아하지 않는다'가 된다.


  '항상'은 '모든 시간'이라고 해석된다.





참고자료

1. Judith L.Gersting의 이산수학




Posted by 하남각목

댓글을 달아 주세요


'모든 사람은 어떤 사람을 좋아한다'는 서술을 형식문법 wff(well formed fomula)로 표현해보자.





그럼 '모든 사람은 어떤 사람을 좋아한다'의 부정는 무엇일까?

서술만 놓고 보면 잘 떠오르지 않는다. 술어논리로 접근해보자.





따라서 '모든 사람은 어떤 사람을 좋아한다'의 부정은

'어떤 사람은 모든 사람을 좋아하지 않는다'가 된다.




참고자료

1. Judith L.Gersting의 이산수학




Posted by 하남각목

댓글을 달아 주세요

지금까지 짝수, 정수, 유리수의 기수는 자연수의 기수와 같다는 것을 보였다.

이쯤 되면 '모든 무한집합의 크기는 같은 것이 아닐까?' 하는 의문이 들게 될 것 이다. 

하지만 모든 무한집합이 서로 일대일대응 할 것이라는 것은 사실이 아니다.

즉, 무한집합 간에도 기수의 차이가 있다는 것이다.




앞서 살펴보았듯이 짝수, 혹수, 자연수, 정수, 유리수의 기수는 모두 이다. 

그렇다면 어떤 집합이 보다 큰 기수를 가질까?


  무한집합 A보다 무한집합 B가 기수가 크다고 말하기 위해서는 

  집합 A는 집합 B의 부분집합이면서 일대일 대응이 불가능하다는 것을 증명해야 한다.



대표적인 예로 실수가 있다.

집합론의 창시자인 칸토어는 자연수 집합과 실수 집합 사이에 절대 일대일 대응이 존재할 수 없다는 것을 밝혔다.

이는 흔히 '칸토어의 대각선 논법(Cantor's diagonal argument)'이라 불린다.


  어떤 것이 불가능하다고 증명하는 수학적 전략은 대표적으로 귀류법(proof by contradiction)이 있다. 

  일대일 대응이 가능하다고 가정하고 모순을 찾는 것이다.




칸토어의 대각선 논법은 간단하다.

다음과 같이 우리가 어떤 일대일 대응을 찾았다고 가정해보자.


그럼 우리는 이 대응에 절대 들어가지 않는 또 다른 실수하나를 발견할 수 있다.

E0과 1번째 숫자가 다르고

E1과 2번째 숫자가 다르고

E2와 3번째 숫자가 다른 또 다른 실수 하나를 만들어 낼 수 있다.

이 말은 일대일대응이 되지 않았다는 것이고, 이는 가정에 모순이다.

따라서, 자연수 집합과 실수 집합 사이에는 일대일 대응이 존재하지 않는다.


  칸토어의 대각선 논법은 무리수를 포함하는 집합에서만 사용 가능하다.



따라서 우리는 실수집합은 자연수 집합보다 기수가 크다고 말할 수 있다.

그리고 실수의 기수를 이라 칭한다.



참고자료

1. 자연수 vs 실수 - 네이버캐스트

2. 칸토어의 대각선 논법(Cantor's diagonal argument) - 위키피디아



Posted by 하남각목

댓글을 달아 주세요

지난 시간에 짝수, 정수 집합이 자연수 집합과 기수가 같다는 것을 배웠다.

그렇다면 정수보다 훨씬 더 큰 유리수도 가산집합(countable set)일까?


자연수와 유리수의 크기를 비교하기 전에 자연수와 자연수의 순서쌍의 개수를 비교해보자.

자연수의 순서쌍은 다음과 같이 좌표평면상에 표현할 수 있다.




가로줄과 세로줄이 교차하는 지점에 자연수의 순서쌍이 위치한다.

세로줄과 가로줄은 무한하게 만나게 되는데 이는 자연수 집합을 (aleph zero)만큼 합집합한 것이다.

따라서 자연수의 순서쌍은 다음과 같이 무한하다.



그런데 위에서 보듯이 우리는 자연수의 순서쌍 하나하나에 자연수를 부여할 수 있다.

따라서 자연수의 순서쌍 집합은 가산집합(countable set)이며 기수는 (aleph zero)이다.


  자연수와 일대일 대응하는 집합들을 가산집합(countable set)이라 한다.

  또 자연수의 기수는 (aleph zero)이다.




여기서 자연수의 순서쌍(x, y)를 유리수 로 바꾸어 생각해보자.

유리수가 자연수의 순서쌍 집합의 부분집합이라는 것을 느낄 수 있는가?

유리수 2는 순서쌍으로는 (1, 2), (2, 4), (3, 6), 으로 무한하게 표현할 수 있다.




이때, 유리수의 기수는 자연수의 기수와 자연수 순서쌍의 기수 사이의 범위에 있다는 것은 자명하다.

이때 자연수의 기수는 (aleph zero)이고 자연수 순서쌍의 기수 또한 (aleph zero)이다.

따라서 유리수의 기수도 역시 (aleph zero)이다.



고로 자연수의 기수와 유리수의 기수는 같다.




참고 자료

1. 자연수 vs 유리수 - 네이버캐스트


Posted by 하남각목

댓글을 달아 주세요

지난 시간에 배운 칸토어의 집합론을 자연수와 정수의 크기 비교에 응용해보자.

자연수와 정수 사이에서 일대일 대응 패턴만 찾으면 된다.



쉽게 말해 홀수 자연수 n에 대해서는 에 대응시키고

짝수 자연수 n에 대해서는 에 대응시키는 규칙이다.



자연수와 정수의 일대일 대응 규칙을 찾았으므로 두 집합의 기수는 같다.

다시 돌이켜 생각해보면 짝수, 홀수, 정수 모두 자연수 집합과 기수가 같다.


예전 수학자들도 이를 발견하고 자연수 집합의 기수를 표준으로 정했는데, 이를 알레프영(aleph zero)이라고 한다.

자연수 집합과 일대일 대응하는 모든 집합의 기수는 알레프영(aleph zero)이다.  


  aleph zero는 무한집합 기수의 세상에서 자연수 0과 같은 존재이다.

  aleph zero는 aleph null 또는 aleph naught라고도 한다. 기호로는 이다.



또 기수가 (aleph zero)인 집합을 가산집합(countable set)이라고 한다.

즉, 셀 수 있다는 말인데 이는 유한하다는 의미가 아니라 1, 2, 3, 이렇게 자연수로 치환할 수 있다는 의미이다.



예를 들어 짝수로 번호가 세겨진 공을 센다고 하자. 

이때 2, 4, 6, 8,  이렇게 세는 사람은 없을 것이다. 

즉 모두 자연수로 치환하여 1, 2, 3, 4, 셀 것이다.(count)

따라서 자연수와 기수가 같은 모든 집합은 가산집합(countable set)이다.


  가산집합의 기수는 (aleph zero) 이다.




참고 자료 

1. 알레프수(aleph number) - 위키피디아

2. 자연수 vs 정수 - 네이버캐스트



Posted by 하남각목

댓글을 달아 주세요

  1. 은둔자 2013.04.26 01:31  댓글주소  수정/삭제  댓글쓰기

    폭풍 포스팅하고 계시네요. 잘 보고 갑니다.

    블로그 이름이 바뀌었네요. 앞으로도 화이팅입니다.