[암호학] 집합론

원소의 개수 (Cardinality)는 |A|로 

유한집합의 경우 원소의 개수를 세면 되어서 쉽다.

하지만 무한집합의 경우는 , 원소의 개수를 셀 수 없기 떄문에

무한집합 

A,B에서 |A|=|B||A|=|B|가 성립하려면 A,B사이에 일대일 대응이 존재해야 한다.

위와 같이 정의한다.

• |N| = |Z| (N : 자연수, Z: 정수)
  • -3 -2 -1 0 1 2 3 4
  • 7 5 3 1 2 4 6 8 
  • 과 같이 일대일 대응이 있으니까 개수가 같다고 판단
• |N| = |Q| (Q: 유리수)
  • 1 2 3 4 5 6 7 8 9
  • 1/1 1/2 2/1 1/3 3/1 1/4 2/3 3/2 4/1 1/5 (합이 2, 합이 3, 합이 4)
• |N| = |R| (N: 자연수, R: 실수) => 자연수와 실수의 cardinality는 다름
  • 이를 Diagonalization (대각화)로 증명할 수 있음. 
  • R1 = {x | 0<x<1}
  • 일대일 대응이 있다고 하자.
    • 1 ↔ 0. d(11) d(12) d(13) d(14) ….
    • 2 ↔ 0.d(21) d(22) d(23) d(24) …..
    • 3 ↔ 0. d(31) d(32) d(33) d(34) …..
    • X = 0.D1 D2 D3 D4 …. (이때, Di=(dii+1)mod10 (mod는 나머지연산) 라 하자)
      • d(ii) 가 4면 Di 는 5
      • d(ii) 가 5면 Di 는 4
    • 그러면, X는 지금까지 자연수와 매칭안된 새로운 실수가 된다.
  • 실수집합은 자연수집합보다 크기가 크다
  • |N|=|Z|=|Q|<|R|  이 된다

---

집합의 종류

• 공집합
• 유한 집합
• 무한하지만 셀 수 있는 (자연수 집합)
• 무한하지만 셀 수 없는 (실수 집합)

power set

power set 은 어떤 집합의 부분집합들을 모두 원소로 하는 집합.

2 ^ x = {A | A (x에 속함 기호 X), powerset의 원소 개수 2 ^|x|

• 모든 집합 X에서 |X|≠|2^X|이다.
  • 증명: X=공집합인 경우, |X| = 0, |2^X| = 1 이므로 참
  • |X| = |2^X| 라는 것은 두 집합 사이에 일대일 대응이 존재한다는 것, 이러한 대응을 f
  •  
  • X : 대각화로 일대일 대응이 계속 생겨나, 무한집합
  • |R| = |2^N|
    • R1 = {x | 0 < x<1}
    • | R1 | = |2 ^N|
      • R1을 이진수로 쓰면
      • 0.10110100 <-> {1,3,4,6,9...} 몇 번째 자리에 있으면 집합에 쓰기
      • 따라서 |2^N| 은 무한집합(uncountable set) 
• 결과적으로 집합론을 요약하면
  • |A|<|N|=|Z|=|Q|<|R|=|2^N|<|2^R|<.... (A : Finite set)

이거 아직 이해안됨

---

Cantor Set and some thoughts (그냥 이해하면 좋은거)

수직선에서 남은 거를 3개로 끊어서 하나씩 버리기 -> 없어진 부분의 길이 = 1/3 + 2/9 + 4/27 + …. = 1 -> 남은 애들 = cantor set

=> 3진수로 섰을 때, 자리가 1인 애들이 없어진 것임, 0,2 로 실수를 만들면 안 없어짐 → 남은 길이는 없는데 개수는 uncountable