[ 이산 수학 ] 7. Cardinality , 행렬

Cardinality = Size of set

 

Set A와 B가 일대일 대응( bijection )이면,

| A | = | B | 라고 한다.

 

 

Set A와 B가 일대일 함수 ( injection )이면,

| A | ≤ | B |. 라고 한다

 

 

Countable

Set의 원소의 개수가 유한개 이거나 양의 정수 같이 한 sequence에 나열할 수 있으면(손으로 꼽을 수 있으면)

Countable이라고 한다. 

 

이러한 양의 정수들의 Cardinalty 는 무한대이긴 하지만 셀 수 있는 무한대 = countably infinite라고 하며

기호로는 ℵ 이렇게 표시한다.

집합 S가 countably infinite 이면  |S| = ℵ0 이렇게 표현한다~

 

Uncountable(가산집합) != 무한집합

무한이 아니더라도 셀 수 없을 수도 있기 때문

 

 

정확하게 하면 그 무한개 있는 집합을 모두 [ 규칙에 맞추어 ] 인덱싱할 수 있으면 된다!!! 

 

• Hilbert’s Grand Hotel

한 호텔에 셀 수 있을 정도지만 무지하게 많은 수(무한대)의 방을 구비해두었다.

각 방은 게스트가 있지만, 손님을 더 받을 수 있다. 어떻게 했을까?


--> 1 , 2 3 4 5 6 7 8 ... n(infinite)
인 호텔방에 새로 손님이 오면

위 사람들을 한 칸씩 옆으로 보내고 새로 온 사람을 1번 칸으로 보낸다.

 

 

---

Set이 Countable인지 확인하는 법

 

1) countable인 것에 일대일 대응이면 가능

 

f(x) = 2x 

 

우선 x에 1,2,3,4... ( 양의 정수 ) 를 넣을 예정이다.

넣는 값이 Countable이고, 그에 대해서 Bijection이므로, 일대일 대응이면서 onto 조건을 만족한다.

 

일대일 대응

1) f(a) = f(b)이면, a=b 이다. 라는 성질을 이용하여 n=m인 것을 확인하고

 

Onto 1) 그냥 다 쏘기만 하면 된다는 성질을 이용해보면,  t=2k 라고 하였을 때k가 양의 정수일 때 f(k)=t인 것을 확인할 수 있다.

 

 

---

2) Sequence 로 나열할 수 있으면 Countable혹은 Bijection이면 가능하긴 함

 

이렇게 표시를 하든

 

이렇게 표시하기

 

 

---

• 양의 유리수는 Countable한가??

유리수(rational num) 은 p/q (q!=0) 로 표현할 수 있어야 한다.

  - 3/4 는 유리수

  - 루트 2는 유리수가 아니다.

 

 

그럼 양의 유리수는 Countable할까?

 

답 ) ㅇㅇ 우리가 sequence에 맞게 나열할 수 있으니까

 

p+q = 1  / p+q = 2 ... 이런식으로 쭉 해도 되고

가로 줄은 분모를 1,2,3,4,5로 증가 / 세로 줄은 분자를 1,2,3,4,5로 증가하는 꼴로 해도 규칙에 맞출 수 있다.

 

  

 

 

 

그러나 실수는 uncountable하다. (비가산집합)
0과 1 사이의 실수 집합이 uncountable하기 때문이다.

0.123456............
0.246582............
0.846236............
0...................
0...................


위와 같이 0 이상 1 이하의 모든 실수들을 쭉 나열할 수 있다고 해보자.
어떤 실수를 임의로 만들면 그 리스트에 포함될 것이다.

그런데 우리는 리스트에 포함되지 않는 수를 만들 수 있다.
1) 리스트 첫째수인 0.123456.....과 다른 수를 만들기 위해
   소수점 첫째자리 수를  1과 다른 수로 쓴다. 임의로 0으로 써보자.
     0.0
    
2) 이번에는 리스트 둘째수인 0.246582...와 같지 않게

   소수점 둘째자리 수를 4과 다른 수로 쓴다. 임의로 3으로 써보자.

     0.03

3) 이런 식으로 리스트 셋째수와는 소수점 셋째자리 수를 같지 않게 하고,

4) 리스트 넷째수와는 소수점 넷째자리 수를 같지 않게 하고,

n) 리스트 n번째수와는 소수점 n번째자리 수가 같지 않게 하면,

리스트에 나온 모든 수와는 다른 새로운 실수를 만들 수 있는 것이다.

그냥 소수점 각 자리수마다 없는 거로 쏙쏙 피해가면 새로운 숫자 만들 수 있다 이 말인 듯

 

---

행렬

사각 배열이라고 보면 된다.

M개의 (row) 가로=행,

N개의 (column) 로= 열을 나타낸다. 

M*N 행렬이라고 한다.

 

 

 

 

• 행렬의 덧셈

조건 ) 두 개의 행렬의 크기가 같아야 한다.

A [ a ij ] , B [ b ij ] 가 m*n 행렬이라고 하자.

 

A+B의 결과는 m*n 행렬이고, 각 인덱스에 a ij + b ij (i,j) 원소가 들어간 형태이다.

따라서, A+B = [a ij + b ij]

 

 

• 행렬의 곱

 

[ 앞 Operand 의 가로  *  뒷 Operand 의 세로 ] 로 연산하므로, 

 

행렬 곱의 조건) A*B를 할 때, A의 Row 개수와 B의 Column 개수가 같아야한다.

 

 

 

 

 

문제

 

 

 

 

행렬의 곱은 교환법칙이 성립하지 않는다! AB != BA

결합법칙은 된다고 함

 

 

 

• 항등 행렬

: n*n 크기의 행렬에서,  (a,a) 만 1인 행렬

아마 이 기호가 i,j 번쨰 칸 값을 구하는 것 같은데

i=j 이면 1, 아니면 0이다.

 

AIn = ImA = A 

(단 , A가 m*n인 행렬일 때. )

 

정사각형 행렬인 행렬 A는 I n라고 한다.

 

 

---

 

• 전치 행렬

: 대각선 기준으로 위치를 바꿈. 인덱스를 나타내려면 그 전[ i , j ] 는 [ j , i ] 라고 생각하면 된다.

 

a[ i , j ] = a`[ j , i ] 이다.

 

 

• 부울 행렬

and 일 땐, 둘 다 1인 것에. 우리가 아는 논리 연산으로 하면 됨

 

어려울 거 없음

이 기호는

이걸 하라는 거임

 

이렇게 미친 짓도 함

 

 

그럼 해야함

 

 

 

(참고)

한동대학교 최희열교수님 - 이산수학

 

http://vackieria.blogspot.com/2009/09/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99countable-%EA%B0%80%EC%82%B0%EC%A7%91%ED%95%A9-uncountable-%EB%B9%84%EA%B0%80%EC%82%B0%EC%A7%91%ED%95%A9.html

 

 

https://m.blog.naver.com/study_together_/221089512333

 

 

(행렬)

https://velog.io/@joygoround/%EC%9D%B4%EC%82%B0%EC%88%98%ED%95%99-%ED%96%89%EB%A0%AC

 

https://sensol2.tistory.com/25