정보의 공유는 자유로워야 한다

Complete Graph(완전 그래프)는 서로 다른 두개의 vertex가 반드시 하나의 edge로 연결된 그래프를 뜻한다.

예를 들어 vertex의 수가 8개인 complete graph는 다음과 같다.

n개의 vertex를 가지는 complete graph는 으로 나타낸다.

은 개의 edge를 가지는데,

이는 n개의 꼭지점 중 2개를 선택하는 조합문제에 해당한다.

vertex가 k개인 complete graph는 자연스럽게 k-1을 차수로 하는 regular graph가 된다.

  regular graph(정규 그래프)는 각 vertex가 동일한 수의 이웃을 가지는 그래프이다.

  즉, 각 vertex의 차수가 모두 같다는 것이다.

또 모든 complete graph는 그 자체로 clique이다.

  clique(클릭)이란 모든 두 꼭지점이 변으로 연결되어 있는 집합을 말한다.

참고자료

1. Complete Graph - 위키피디아

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

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

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

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

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

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

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

참고자료

1. Judith L.Gersting의 이산수학

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

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

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

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

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

참고자료

1. Judith L.Gersting의 이산수학

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E0과 1번째 숫자가 다르고

E1과 2번째 숫자가 다르고

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

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

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

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

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

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

참고자료

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

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

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

그렇다면 정수보다 훨씬 더 큰 유리수도 가산집합(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 유리수 - 네이버캐스트

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

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

쉽게 말해 홀수 자연수 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 정수 - 네이버캐스트

짝수의 개수와 자연수의 개수 중 어느 쪽이 많을까?

짝수가 자연수의 부분집합이니까 짝수의 개수가 자연수의 개수보다 많지는 않을 것이다.

그렇다면 자연수의 개수가 짝수의 개수보다 큰가?

어찌보면 당연히 자연수 집합의 크기가 짝수 집합의 크기보다 큰 것 같아보인다.

자연수는 짝수 뿐만 아니라 홀수로도 이루어지고,

짝수의 기수 + 홀수의 기수 = 자연수의 기수이기 때문이다.

  기수(cardinal number)는 수의 일종으로 집합의 크기를 나타내기 위해 사용된다. 여기서 크기는 간단히 원소의 개수를 뜻한다. 집합론의 용어로는 농도라고도 한다.

하지만 요점은 짝수 집합과 자연수 집합, 둘다 무한 집합이라는 데 있다. 

'무한'은 어떤 것의 크기를 나타내는 용어가 아니라 무수히 많다는 성질을 나타내는 용어이다.

그렇기 때문에 무한에는 수학적인 연산이 적용되지 않는다.

  기수로서의 무한은 극한에서 나오는 무한과는 전혀 상관없다.

 그럼 크기 비교는 불가능한 걸까?

  여기서 서로 다른 크기를 가진 무한 집합이 존재한다고 주장한 

  집합론의 창시자, 칸토어를 소개한다.

  칸토어는 두 유한집합 사이에 일대일 대응이 가능하면,

  두 유한집합의 기수가 같다는 것을 밝혔다.

  이를 확장하여 무한집합에서도 일대일 대응의 패턴이 발견되면,

  두 무한집합의 기수는 같다고 할 수 있다고 주장하였다.

  칸토어의 집합론(Set Theory) : 일대일 대응이 가능하면 집합의 기수가 같다.

이를 짝수와 자연수의 크기 비교에 응용해보자.

자연수 집합과 짝수 집합은 다음과 같이 일대일 대응이 가능하다.

따라서 짝수의 크기와 자연수의 크기는 같다.

위와 비슷하게 홀수의 크기와 자연수의 크기가 같다는 것도 쉽게 증명할 수 있다.

  주의 : 일대일 대응 패턴을 찾지 못하더라도 집합 A의 기수가 집합 B의 기수보다 작다고 할 수 없다. 

           일대일 대응 패턴이 없다는 것을 증명해야 집합 A의 기수가 집합 B의 기수보다 작다고 할 수 있다.

참고 자료

1. 기수(cardinality) - 위키피디아

2. 칸토어(Georg Cantor) - 위키피디아

3. 짝수 vs 자연수 - 네이버캐스트