선택공리

선택함수

집합 의 부분집합들의 집합족을 이라 할 때,

인

선택공리

공집합이 아닌 임의의 집합에 대한 선택함수가 존재한다.

참고) 선택공리는 ‘공집합을 원소로 갖지 않는 서로소인 집합족 의 원소들에서 하나씩 원소를 선택하여 갖는 집합이 존재한다’ 라고도 해석이 가능하다.

동치인 명제

극대원리

임의의 부분순서집합은 극대인 쇄를 갖는다.

조른의 원리

모든 쇄가 위로 유계인 부분순서집합의 극대원소를 갖는다.

정렬원리

모든 집합은 정렬가능하다.

즉, 모든 집합은 적당한 순서관계를 부여하여 정렬집합으로 만들 수 있다.

그 외의 명제들

• 라그랑주 원리
• 타르스키 원리
• 티호노프 원리
• 타이히뮐러-투키 원리
• 임의의 두 기수의 비교가능원리
• 모든 벡터공간의 기저존재원리

함의되는 명제

• 괴델의 완전성 원리
• 베르의 범주원리
• 한-바나흐 원리
• 바나흐-타르스키 역설
• 닐센-슈라이어 원리
• 모든 체의 대수적 폐포존재 원리

부분순서집합

정의

부분순서관계

반사적, 반대칭적, 추이적인 관계

• ex 1) 두 집합 에 대하여
• ex 2) 두 실수 에 대하여
• ex 3) 두 자연수 에 대하여 이 의 배수인 관계

부분순서집합

집합 상에 부분순서관계 가 주어진 경우 를 부분순서집합이라 하고 이를 로 나타내기도 한다.

• 집합 에 관계가 부여 됐을 뿐이지, 집합 의 모든 원소들이 순서 관계를 가져야 하는 것은 아니다.
• ex) 일 때, 
  • 다음의 관계는 성립하지만
    •  
    •  
    •  
    •  
    •  
  • 다음의 관계는 성립하지 않는다.
    • 
    • 
  • 즉 모든 원소들이 부분순서 관계를 갖지는 않는다는 것.

극대원소와 극소원소

가 부분순서집합이라 할 때,

• 를 만족하는 의 원소 를 극대원소,
• 를 만족하는 의 원소 를 극소원소라 한다.
• ex) 멱집합 에서
• 극대, 극소 원소는 유일하지 않다. 극대, 극소는 최대, 최소와는 다르다.
• ex) 집합 의 관계가 다음과 같다면
  •  
  •  
  •  
  •  
  • c, e는 극대원소가 되고
  • a, b는 극소원소가 된다.

최대원소와 최소원소

가 부분순서집합이라 할 때,

• 를 만족하는 의 원소 를 최대원소,
• 를 만족하는 의 원소 를 최소원소라 한다.
• 극대, 극소와 달리 최대, 최소는 유일하다.

상한과 하한

• 극대-극소, 최대-최소를 무한집합에 적용하기 어렵기 때문에 만들어진 개념이 상계-하계, 상한-하한
• 해당 집합을 포함하는 집합을 더 큰 정의하고 그 더 큰 집합을 이용해서 상계-하계와 상한-하한을 정의함. 

상계와 하계

가 부분순서집합 의 부분집합이라 할 때,

• 인 를 에서 의 상계,
• 인 를 에서 의 하계라 한다.
• 상계-하계는 항상 존재하지 않음.

상한과 하한

부분순서집합 의 부분집합 에 대하여

• 의 상계들의 집합이 최소 원소를 가질 때 이 원소를 에서 의 상한이라 하고, 로 나타낸다.
• 의 하계들의 집합이 최대 원소를 가질 때 이 원소를 에서 의 하한이라 하고, 로 나타낸다.
• ex) 에서

절편과 절단

절편

부분순서집합 의 원소 에 대하여

• 
  • 집합 아래에 표시된 숫자보다 작은 숫자들을 모은 집합이라고 생각하면 된다.
• ex 1) 의 절편
• ex 2) 의 절편

절단

1. 
2. 
3. 

를 만족하는 부분순서집합 의 공집합이 아닌 부분집합들의 쌍

• ex) 의 두 부분집합 에 대하여
• 일종의 분할과 비슷하다.

순서동형

순서보존함수

부분순서집합 에 대하여

• 함수 가 조건 을 만족하면
• 를 순서보존함수라 한다.
• 순서만 보장되면 되기 때문에, 집합 A와 집합 B의 크기가 달라도 무방하다.

순서동형

부분순서집합 에 대하여

• 함수 가 전단사이고 이면 를 순서동형사상이라 한다.
• 이때 는 순서동형이라 하고 로 나타낸다.
• ex) 항등함수

전순서집합

전순서집합

비교가능

부분순서집합 의 두 원소 가 이면 는 비교가능하다고 한다.

• ex) 집합 의 관계가 다음과 같을 때
  •  
  •  
  •  
  • 다른 원소들 간에는 비교가 가능하지만 a와 b는 비교가 불가능하다.

전순서집합

부분순서집합 의 임의의 두 원소가 비교가능하면 를 전순서집합이라고 한다.

• 집합 내의 모든 원소가 비교 가능한 상태이면 전순서집합이 된다.

쇄

부분순서집합 의 전순서 부분집합 를 에서의 쇄라고 한다.

• ex) 집합 의 관계가 다음과 같을 때
  •  
  •  
  •  
•  는 전순서 집합이 아니지만, 만일 의 부분집합을  로 잡으면 는 전순서집합이 되고, 이 때 를 의 쇄라고 한다.

정렬집합

부분순서집합 의 공집합이 아닌 모든 부분집합 가 최소원소를 가지면, 그리고 그 때에만 집합  를 정렬집합이라 한다.

• ex)
  • 는 전순서집합이긴 하지만, 최소 원소를 갖고 있지 않기 때문에 정렬집합은 아니다.
  • 는 전순서집합이기도 하고 정렬집합이기도 하다.
• 따라서 정렬집합이면 전순서집합이다. 그 역은 성립하지 않는다.

서수

서수의 개념

서수

집합의 길이를 나타내는 수

1. 모든 정렬집합 에 대하여 서수가 존재하며, 모든 순서수 에 대하여, 인 정렬집합 가 존재한다.
   • 책에 따라 라고 표기하기도 함.
2. 
3. 
4. 

• 기수와 서수의 가장 큰 차이는 구조가 들어가느냐 하는 것.

유한서수와 초한서수

유한서수란 유한정렬집합의 기수이고, 초한서수란 무한정렬집합의 서수이다.

• <대표적인 초한서수>
  • 

서수의 순서

정렬집합 에 대하여 일 때,

• 가 의 절편과 순서동형이면 는 보다 작거나 같다고 하며 로 나타낸다.
• 이때 특히 이면 로 나타낸다.

서수의 연산

서수 합

서로소인 두 집합 의 서수를 각각 라고 할 때

• ex) 라면 
  • 를 로 변환한 후에
  • 그 둘을 합하여   을 만든다.

서수 곱

서로소인 두 집합 의 서수를 각각 라고 할 때

• 순서쌍의 순서는 앞의 것을 먼저, 뒤의 것을 그 다음에 보는 것이 자연스럽다 –사전식 순서
• 뒤의 것을 앞으로 놓고 곱하는 것이 사전식 순서 결과를 만들 수 있기 때문에 서수곱은 뒤의 것을 먼저두는 식으로 한다. 이것은 일종의 수학적 약속.

연산 법칙

임의의 서수 에 대하여 다음이 성립한다.

• 결합법칙
  • 
  • 
• 분배법칙
  • 
  • 단 
    • 좌측 분배 법칙은 성립하지만, 우측 분배 법칙은 성립하지 않는다.
    • 
    • 
• 일반적으로 서수는 합과 곱에 대하여 교환법칙이 성립하지 않는다.
  • 
  • 

1.  

집한론의 역설

칸토어의 역설

칸토어의 정리

임의의 집합 에 대하여 이다.

• (크거나 같은 것이 아니라 아예 큰 것)
• (멱집합의 기수는 가 되는데, 원래 집합이 공집합이었을 때 조차도 이 되어서 멱집합은 항상 원래 집합 보다 크게 된다.)

칸토어의 역설

모든 집합들의 집합을 , 그 기수를 라 하자.

그러면 칸토어의 정리에 따라 의 멱집합의 기수 는 이지만, 이는 이어야 하는 가정에 모순이 된다.

• (멱집합의 기수가 원래 집합보다 같거나 큰 것이 아니라 항상 크기 때문에 역설이 발생)

러셀의 역설

모든 집합들의 집합을 라 하자.

그러면 는 하나의 집합이 된다. (여기서 S는 자기 자신을 원소로 갖지 않는 집합들의 집합)

만약 라 하자. 그러면 의 정의에 의해 이다.

만약 라고 하자. 그러면 의 정의에 의해 이다.

따라서 는 존재하지 않는다.

• (칸토어의 역설이나 러셀의 역설이나 모두 모든 집합들의 집합은 존재하지 않는다는 증명)

공리적 집합론

ZFC

체르멜로(Zermelo)-프렝켈(Fraenkel)의 ZF 공리계에 선택공리(Axiom of choice)가 추가된 공리계.

체르멜로가 확장공리/ 짝공리/ 공집합공리/ 무한공리/ 합집합공리/멱집합공리/분류공리꼴 7개를 만들었고, 이후에 체르멜로 공리계의 허술함을 보완하기 위해 폰노인만의 정칙성공리와 프렝켈의 치환공리꼴이 추가 되어 ZF 공리계가 완성 됨. 최종적으로 선택공리가 추가되어 ZFC가 완성 됨.

현대 수학의 표준적인 수학기초론으로 다음 10가지 공리 및 공리꼴을 가지고 집합론을 구성한다.

• 확장공리
  • 두 집합의 모든 원소가 일치하면 두 집합은 동일하다
• 짝공리
  • 두 집합을 원소로 하는 집합이 존재한다.
• 공집합공리
  • 아무런 원소도 갖지 않는 집합(공집합)도 존재한다. 
• 무한공리
  • 무한 집합이 존재한다.
• 합집합공리
  • 집합족의 합집합도 집합이다.
• 멱집합공리
  • 집합의 멱집합도 집합이다.
• 분류공리꼴
  • 명제함수가 참이 되게 하는 집합의 원소들을 갖고 집합을 만들어도 집합이다.
• 정칙성공리
  • X라는 집합이 공집합이 아니면 X와 서로소인 원소를 갖는 집합도 집합이다.
• 치환공리꼴
  • 미지수 x, y가 포함된 논리식이 있을 때, 논리식이 참이 되게 하는 y들의 집합도 집합이다.
• 선택공리 (Axiom of choice)

그 외의 집합론

NBG

ZFC의 보존적 확장 형태로, 고유 모임을 포함하는 집합론.

폰 노이만-베르나이스-괴델의 이름을 따서 만들어짐.

고유 모임(proper class)이란 집합이 아닌 모임을 의미.

MK

NBG에서 재귀적 정의를 허용한 집합론.

모스-켈리의 이름을 따서 만들어짐.

연속체 가설

정의

칸토어의 연속체 가설

두 초한기수 에 대하여, 를 만족하는 기수 는 존재하지 않는다. 

일반화 연속체 가설

임의의 초한기수 에 대하여, 를 만족하는 기수 는 존재하지 않는다. 

ZFC 와의 관계

연속체 가설은 ZFC와 독립적이다. 즉, ZFC 에서는 연속체 가설을 증명할 수도, 반증할 수도 없다.

다른 공리와의 관계

구성 가능성 공리

ZFC에 구성 가능성 공리를 추가하면 일반화 연속체 가설이 참이다.

고유 강제법 공리

고유 강제법 공리를 가정하면 칸토어의 연속체 가설은 거짓이다.

집합의 분류

유한, 무한집합

동등

두 집합 에 대하여 전단사함수 가 존재하면 는 동등이다. ( 또는 )

유한, 무한집합

집합 의 적당한 진부분집합 가 와 동등하면 는 무한집합이다.

무한집합이 아닌 집합을 유한집합이라 한다.

ex) 은 무한집합이다.

여러가지 정리

• 공집합 은 유한집합이다.
• 무한집합을 포함하는 집합은 무한이다.
• 유한집합의 모든 부분집합은 유한이다.
• 전단사함수 에 대하여
  • 가 무한집합이면 도 무한집합이고
  • 가 유한집합이면 도 유한집합이다.
• 무한집합 의 부분집합 가 유한이면 는 무한집합이다.

가부번, 비가부번 집합

가부번집합

집합 가 일 때 를 가부번집합이라 한다.

• 가부번집합은 번호를 붙일 수 있는 집합을 의미함.
  • 자연수 집합은 번호를 붙일 수 있으므로 가부번 집합이다. –1 다음은 2 그 다음 3이므로
  • 실수 집합은 번호를 붙일 수 없으므로 비가부번 집합이 된다. –1 다음 수를 어떤 것으로 정의할 수가 없음.

가산집합

유한집합이나 가부번집합을 가산집합이라 한다.

여러가지 정리

• 가산집합의 부분집합은 가산집합이다.
• 가부번집합들의 합집합은 가부번이다.
• 은 가부번집합이다.
• 은 가부번집합이다.
  • 가부번 집합을 합하거나 곱해도 가부번 집합이다. –지수로 올리면 얘기가 달라짐.
• 의 부분집합 은 비가부번이다.
• 모든 무리수의 집합은 비가부번집합이다.
  • 비가부번 집합인 실수 집합은 유리수와 무리수 집합의 합집합인데, 유리수 집합은 가부번 집합이므로 무리수 집합이 비가부번 집합이어야 한다.
• 은 비가부번집합이다. (복소수 집합)

기수

기수의 개념

기수

집합의 크기를 나타내는 수. 또는

• 각 집합 에 대해 는 유일하다.
• 에 해당하는 집합 는 항상 있다.
• 
• 이면
• 
• (배열의 길이라고 생각하면 편하다)

유한기수, 초한기수

유한기수는 유한집합의 기수이고, 초한기수는 무한집합의 기수

• 대표적인 초한기수
  • 가부번집합의 기수 (알레프 제로라고 읽음)
  • 연속체의 기수 (시그마라고 읽음)

#A < #B

는 의 한 부분집합과 동등이고, 는 의 어떠한 부분집합과도 동등이지 않다.

• 
• 가 의 부분집합과 동등이고, 도 의 부분집합과 동등이면 와 는 동등이다. () – 칸토어-번슈타인 정리
• 이고  이면  이다.

기수의 연산

기수 합

서로소인 두 집합 의 기수를 각각 라고할 때,

기수 곱

집합 의 기수를 각각 라고할 때,

연산 법칙

임의의 기수 에 대하여 다음이 성립한다.

• 교환법칙
  • 
  • 
• 결합법칙
  • 
  • 
• 분배법칙
  • 
• (기수 자체는 숫자인데, 기수의 연산은 그 숫자의 값이 위의 결과를 만족한다고 보는게 아니라, 그 기수가 대응되는 집합과의 관계가 위 조건을 만족한다는 의미)

여러가지 정리

• 
• 
• 
• 
• 
• 

기수의 지수

집합 에 대하여 일 때

• 
  • A에서 B로 가는 함수를 끌어 모은 집합. 지수에서 밑으로 가는 모습
  • ex) 일 때, 의 총 개수
    • 
• 
• 일 때,

여러가지 정리

• 집합 에 대하여  일 때 
  • ex) 일때
    • 
    • 
• 기수 에 대하여
  • 
  • 
  • 
• 
  • 끼리의 합이나 곱은 여전히 지만, 지수로 올리면 가 된다.
  • 에 를 지수로 올려도 가 된다.
• 
  • 는 실수집합의 멱집합

함수

함수의 정의

• 함수: 다음을 만족하는 X에서 Y로의 관계
  • 
    • 는 라고도 쓴다.
    • s.t.는 such that의 약자. 그러한 것을 만족 시키는
  • 
  • ex) X = { 1, 2, 3 }, Y = { a, b, c } 일 때
    • f1 = { (1, a), (1, b), (2, b), (3, c) }
      • f1은 함수가 아니다 (1, a), (1, b) 때문
    • f2 = { (1, a), (2, b) }
      • f2는 함수가 아니다. X의 3에 대응되는 순서쌍이 없기 때문.
    • f3 = { (1, a), (2, a), (3, b) }
      • f3는 함수다. Y의 c가 없지만 이것은 함수의 정의에 부합한다.
• 함수 에서 일 때 다음과 같이 부른다. 
  • y를 f에 의한 x의 상 (Image)
  • x를 f에 의한 y의 원상 (Pre-Image)
  • X를 f의 정의역 Dom(f) (Domain)
  • Y를 f의 공역 (Co-Domain)
  • 를 f의 치역 Rng(f) (Range)
  • ex) 위 예제의 f3의 경우
    • Dom(f3) = { 1, 2, 3 }
    • Rng(f3) = { a, b }
    • 1의 상 = a
    • a의 원상 = { 1, 2 }
• 함수식이 같아도 정의역이 다르면 다른 함수다.
  • ex)
• 함수  에 대하여 일 때 
  • 는 X를 A로 축소한 함수
    • 
  • 이면 f는 g의 A에서의 확대함수
  • ex) A = { 1, 2 }, B = { 1, 2, 3 }, Y = { a, b, c } 일 때
    • 
    • 
    • f를 축소하면 g가 되고, g를 확대하면 f가 된다.

함수의 성질

• 함수  에 대하여
  • 전사 (Onto)
    • 
    • 공역에 있는 모든 원소가 화살을 받은 상태
  • 단사 (Into)
    • 
    • 공역에 있는 모든 원소가 화살을 하나씩만 받은 상태
  • 전단사: 전사이고 단사인 함수. 일대일 대응

여러가지 함수

• 고등학교 교육과정 내
  • 항등함수
    • 
    • x를 넣으면 x가 그대로 나오는 함수. 정의역이 공역이면서 치역이 된다.
  • 상등함수
    • 
    • 어떤 값을 넣어도 어떤 상수가 나옴.
  • 역함수
    • 전단사인 에 대하여  
    • 역함수가 가능하려면 전단사 함수여야 함. 
  • 합성함수
    • 두 함수 와
  • 합성함수의 성질
    • 
    • 
    • 
    • 
    • 가 모두 단사면 는 단사
    • 가 모두 전사면 는 전사
• 고등학교 교육과정 외 (집합 가 일 때)
  • 포함함수
    • 가
    • 항등함수의 축소된 함수
  • 특성함수 (지시 함수)
    • 가
    • 어떤 특정 집합을 두고, 이 특정 집합에 내가 원하는 값이 포함 되었는지 안 되었는지를 지시하는 함수
  • 선택함수
    • 집합 의 부분집합들의 집합족을 이라 할 때 모든 에 대하여 로 정의되는 함수
    • ex) X = { 1, 2, 3, 4, 5 }, A1 = { 1, 2, 3 }, A2 = { 2, 3, 4 }, A3 = { 4, 5 } 일 때
      • 함수 f가 A1, A2, A3을 정의역으로 가지고 그 치역이 각각 2, 4, 5일 경우 이 함수 f는 선택 함수가 된다. A1에 2가 포함되어 있고, A2에 4가 포함되어 있고, A3에 5가 포함되어 있기 때문.
      • 반면 함수 g가 A1, A2, A3을 정의역으로 가지고 그 치역이 각각 1, 2, 3일 경우 이 함수 g는 선택 함수가 아니다. A1에 1가 포함되어 있고, A2에 2가 포함되어 있지만, A3에 3가 포함되어 있지 않기 때문.

• •  

여러가지 정리

• 함수 에 대하여 역함수 가 존재하면 는 전단사이다.
• 합성함수 가 단사이면 는 단사이고, 가 전사이면 는 전사이다.
• 정수집합 과 자연수집합 사이에는 일대일 대응이 존재한다.
  • (증명) 를 다음과 같이 정의한다.
    • 
    • f는 단사임을 증명
      • case1)  
      • case2)  
    • f는 전사임을 증명
      • 양의 짝수집합을 , 양의 홀수집합을 라고 정의
      • case1)  
      • case2)
    • 따라서 f는 전단사 함수이고 고로 일대일 대응이 된다.

집합의 함수

개념과 정의

• 함수 에서 이고 일 때 다음이 성립한다.
  
  • f에 대한 A의 상
    • 
  • f에 대한 B의 역상
    • 
  • ex) 가 라 할때
    • 집합 A를 { -1, 0, 1, 2 } 라고 하면 집합에 대한 함수는 가 된다. (각각의 원소를 함수에 대입)
    • 집합 B를 { 0, 1, 4 } 라고 할 때 B의 역상은  가 된다.
    • 여기서 집합 B는 A의 상인데, B의 역상을 구하면 원래 집합 A보다 큰 집합이 된다.
    • 집합 A의 상은 일반적으로 집합 A의 크기보다 줄어들게 된다. (단사가 되면 동일), 반면 집합 A의 역상에 대한 상은 일반적으로 집합 A의 크기보다 커지게 된다. (전사가 되면 동일)

여러가지 정리

• 함수 에서 이고 일 때 다음이 성립한다.
  • 
  • 
  • 는 단사
  • 는 전사
• 함수 에 대하여 를 의 부분집합족이라 하면 다음이 성립한다.
  • 
  • 
  • 가 단사이면 

관계

용어 정리

• 관계
  • 곱집합 의 부분집합
  • 
  • P(x, y)는 명제함수
  • ex) A = {2, 3}, B = {4, 6} 이라 할 때,
    • 이 되고
    • 명제함수 P(x, y)를 ‘x는 y의 약수이다’ 라고 정의하면
    • 이 된다.
    • 이때 의 한 원소인 (2, 4)는 또는 와 같이 표기가 가능하다.
• 관계 의 해집합
  • 는 참
• 정의역 (Domain)
  • 적당한 에 대하여, 인 모든  의 집합 
  • 의 왼쪽에 오는 원소들(x). 위의 예시의 경우  
• 상 (Image)
  • 적당한 에 대하여, 인 모든 의 집합
  • 의 오른쪽에 오는 원소들(y). 위의 예시의 경우  

관계의 성질

집합 X에서의 관계 에 대하여

• 반사성:
  • ex) X = {1, 2, 3} 에서의 관계
    • 는 반사적이지 않다. (3, 3)이 없기 때문
    • 는 반사적이다. 자기 자신에 대해 반사적인 원소가 모두 있으면 추가적인 원소가 있는 것은 반사성에 영향이 없다.
    • 이때 반사성을 이루는 원소 (1, 1), (2, 2), (3, 3)을 특별히 라고 표기하며 대각관계 또는 항등관계라고 부른다.
    • 집합이 반사적이라는 말은 대각관계(또는 항등관계)를 포함하고 있다는 말이 된다.
• 대칭성:
  • ex) X = {1, 2, 3} 에서의 관계
    • 는 대칭적이다. (1, 2)가 있을 때 (2, 1)이 있으면 대칭적이라고 인정한다.
• 반대칭성:
  • ex) X = {1, 2, 3} 에서의 관계
    • 는 반대칭적이지 않다. 대칭되는 쌍이 존재하기 때문. 만일 위 집합에서 (1, 2)나 (2, 1)이 빠지면 반대칭적이 된다.
    • 반면 반대칭성의 정의에 의해 (1, 1)은 반대칭적이다. 이 성립하기 때문.
• 추이성:
  • ex) X = {1, 2, 3} 에서의 관계
    • 은 추이적이지 못하다. (1, 2), (2, 3)은 있지만 (1, 3)은 없기 때문. 위 집합에 (1, 3)을 추가하면 추이적이 된다. (3, 1)이 추가 되어야 하는 것이 아니므로 주의.
• ex) X = {1, 2, 3} 에서의 관계
  • 가 있을 때
  • 위 집합은 반사적이지 못하다. (3, 3)이 없기 때문.
  • 위 집합은 대칭적이다. (1, 3)에 대칭되는 (3, 1)이 존재하고 (2, 3)에 대칭되는 (3, 2)가 존재하기 때문.
  • 위 집합은 반대칭적이지 못하다. 대칭적이기 때문.
  • 위 집합은 추이적이지 못하다. (1, 3)과 (2, 3)이 존재하지만 (1, 2)가 없기 때문.

여러가지 관계

• 역관계
  • 이면 오직 그 때에만 즉,
  • ex) 의 역관계는 가 된다.
• 합성관계
  • 집합 X에서의 관계 G와 H에 대하여 합성관계
    • 합성 관계의 순서는 오른쪽에서 왼쪽으로 진행되기 때문에 위 합성관계에서 G를 먼저 쓰고 그 후에 H를 쓰면 된다.
  • ex)
• 역관계와 합성관계에 관한 정리
  • 집합 X에서의 관계 F, G, H에 대하여 다음이 모두 성립한다.
    • 
    • 
    • 
•  동치관계
  • 반사적, 대칭적, 추이적인 관계
  • ex) “=” 는 반사적이고 대칭적이고 추이적이므로 동치 관계가 된다.
    • 반사적:
    • 대칭적:
    • 추이적:
  • 집합 에 대하여 가장 작은 동치관계는 의 대각관계가 되고, 가장 큰 동치관계는 가 된다.
  • 동치관계는 E라고 표기하기도 한다.
• 순서관계
  • 반사적, 반대칭적, 추이적인 관계
  • ex) 은 순서 관계이다.

동치관계와 분할

용어 정리

• 분할: 집합 X에 대하여 다음 세 조건을 만족하는 집합족
  • 공집합을 원소로 하지 않는다.
  • X를 덮는다.
  • 서로소 집합족이다.
  • ex) X = {1, 2, 3, 4, 5} 에서의 분할 P를 다음과 같이 구성 P = { {1, 2}, {3, 4}, {5} }
• 동치류: 집합 X 상의 하나의 동치 관계를 E라 할 때
  • 
  • ex) X = {1, 2, 3, 4, 5} 일 때
    • E = { (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 3), (3, 1), (2, 4), (4, 2) } 라 하면
    • 
      • 1의 동치류라는 것은 왼쪽에 1이 나오는 순서쌍의 오른쪽 것을 의미한다.
    • 
    • 
    • 
    • 
• 상집합: 집합 X에서의 모든 동치류의 집합
  • 
  • ex) 앞선 예와 같이 동치류들이 구성되었을 때
    • 상집합 는 모든 동치류들을 합한 것이므로 다음과 같다.
    • 이 상집합은 집합의 분할과 동일하다. 이는 다시 말해 동치관계를 알면 그 동치관계를 이용해서 분할을 끌어낼 수 있다는 뜻이 된다.
    • 물론 그 역도 성립하므로 분할을 알면 동치 관계를 이끌어낼 수 있다.
• (분할 P에 의한 관계)
  • 
  • ex) X = {1, 2, 3, 4, 5}, P = { {1, 2}, {3, 4}, {5} } 일 때, P의 부분집합을 각각  이라하면
    • 
    • 
    • 
    • 이 를 모두 모으면 이 된다. 

여러가지 정리

• 공집합이 아닌 집합 X 위의 동치관계 E에 대하여 다음이 모두 성립한다.
  • 
  • 
  • 
  • 는  의 분할이다.
• 공집합이 아닌 집합 X의 분할 P에 대하여 다음이 모두 성립한다.
  • 는 상의 동치관계다.
  • 

• (용어 정리 생략)

집합족

집합족(Family)이란?

• 집합족
  • 집합을 원소로 갖는 집합 (ex 멱집합)
  • 집합족은 F로 표기
• 첨수족
  • 첨수(번호)가 부여된 대상들로 이루어진 집합. 집합족의 표현을 간단하게 하기 위해 만든 개념.
  • 첨수족은 I로 표기
• ex) 집합 에 대하여
  • 멱집합은 가 되고, 이를 집합족 F라 정의
  • 집합족 F에 속하는 각각의 집합에 Index를 붙여서 표현하면
  • 가 되고 여기의 I를 첨수족이라 부른다.

집합족의 연산

• 
• 
• ex) 집합족 에 대하여
  • 
  • 
  • 위 집합족을 첨수집합으로 표기하면 가 되고, 합집합과 교집합은 다음과 같이 표기 가능하다.
    • 
    • 
• quiz) 만일 첨수족 I에 대하여 이라면
  • 
  • 
  • 첨수집합 I의 합집합은 공집합이 되지만, 교집합은 전체집합이 된다.

드모르간 법칙

• 
• 

분배법칙

• 
• 

곱집합

곱집합이란?

• 순서쌍은 순서가 중요한 반면, 집합은 순서가 중요하지 않다. 순서쌍을 집합에 적용하기 위해 다음과 같이 정의한다.
•  순서쌍
  • 
  • ex) (1, 2) 라는 순서쌍을 집합으로 표현하면 다음과 같다.
    • 
    • 집합 자체에는 순서가 없기 때문에 위의 결과는 다음과도 동일하다.
    • 
    • 역으로 { {2, 3}, {3} } 이라는 집합은 (3, 2)와 대응되는데, 기본 원칙은 겹치는 것이 먼저 나오고, 그렇지 않은 것이 나중에 나오는 식으로 표기한다.
• 곱집합
  • 
    • ex) A = { 1, 2 }, B = { 3, 4 } 일 때, 순서쌍의 곱은 다음과 같다.
      • 
      • 

곱집합의 연산

• 
• 
• 
• 

집합족의 공집합

• 임의의 집합족 F가 첨수집합 I에 의해 첨수화된 첨수족 의 곱집합 는 다음과 같다.
  • 

명제와 증명

명제와 연결사

• 명제: 참, 거짓이 분명히 판단되는 문장
  • 단순 명제: p, q, r
  • 합성 명제: 몇 개의 단순 명제들이 연결사에 의해 결합된 명제
• 연결사: 두 명제 p와 q에 대해
  • 부정
    • 
    • not p
  • 논리곱
    • 
    • p and q
  • 논리합
    • 
    • p or q
  • 조건
    • 
    • if p then q
  • 쌍조건
    • 
    • p if and only if q
    • 줄여서 iff 라고도 함

진리표

• 진리표란 명제의 진리값을 표로 나타낸 것

T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

• 진리집합
  • 해당 명제가 참이 되도록 하는 모든 원소들의 집합
  • 집합이므로 대문자로 표기
• 명제 P가 거짓이라는 것은 진리집합에 해당 하는 원소들이 없다는 의미이고, P는 공집합이라는 의미가 된다.
• 는 p가 q의 부분집합인지를 묻는 것과 같다. 만일 p가 거짓이면 p가 공집합이 되는 것이므로, p가 거짓일 때는 q와 관계 없이 참이 된다.
• 진리표에 의해 다음 명제들은 참이다.
  • 
  • (드모르간의 법칙)
  • (대우 법칙)
  • (결합 법칙)
  • (분배 법칙)
  • 위 명제들의 and를 or로, or를 and로 동시에 바꾸면 결과는 같다.

연역적 추론

• 연역적 추론이란 이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 것

명제 함수

명제함수와 한정기호

• 명제함수: 변수 x가 결정되어야만 참, 거짓이 판단되는 문장
  • 
• 한정기호: 전칭기호와 존재기호
  • : for every
  • : for some

명제의 부정

• 두 명제 p와 q에 대해, x의 모집단은 건드리지 않도록 하며 다음의 4가지 원리를 모두 적용한다.
  • 
  • 
  • 
  • 

함의와 동치

항진명제와 모순명제

• 항진명제: 모든 논리적 가능성의 진리값들이 참인 명제. t
• 모순명제: 모든 논리적 가능성의 진리값들이 거짓인 명제. c
• 항진명제와 모순명제의 성질
  • 임의의 명제 p에 대하여
    • 
    • 
    • 
    • 
    • 
    • 
• 항진명제, 모순명제의 정의에 따라 아래 명제는 참이다.
  • 
  • 
    • p이면 q이고, q이면 r이면, p이면 r이다.

함의와 동치

• 함의: 항진인 조건문 를 논리적 함의라 하고, 로 나타내며, p는 q의 충분조건, q는 p의 필요조건이라 한다.
• 동치: 항진인 쌍조건문 를 동치라 하고, 로 나타내며 p와 q는 서로의 필요충분조건이라 한다.

개념

• : V.S over 일때, : sub V.S of (V.S = Vector Space)
  
  • 
    • 
    • 가 위에서 그대로 잘 정의되어,  : V.S over
• Sub V.S 예시
  • (over ) : sub V.S of  (over )
  • V : sub V.S of V
  • : sub V.S of V
  •  
• : sub V.S of
  • 
    • 
    • 
    • 
• Sub V.S 특징
  • : sub V.S of , : sub V.S of : sub V.S of
  • : sub V.S of : sub V.S of
  • : sub V.S of
    • 
      • : sub V.S of
  • : sub V.S of
    • 
      • : sub V.S of
      • : sub V.S of
      • : sub V.S of
  • : sub V.S of
    • 
      • 
      • 
• : V.S over 일때, 곱집합 
• 벡터 공간의 External Direct Sum
  • 에 다음 연산을 정의한다.
    • 
    • 
  • 그러면 는 V.S over 가 된다.
  • 이 벡터공간을 이라 한다.
• 벡터 공간의 Internal Direct Sum
  • : V.S over , : sub V.S of 일 때
    • 
      • 
        • 
        • 
• 
  • External, Internal Direct Sum이 Isomorphic 하기 때문에 특별히 구분 하지 않고 라 쓴다.
• 벡터 공간의 Direct Sum의 예
  • 
    • 
  • 
  • 
  • 
• Direct Sum of Many V.S 에 대해서도 정의 가능. 유한한 경우와 무한한 경우 정의가 다른데 생략.

개념

• : 스칼라 에 대한 벡터 공간 ()
  • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 
    • 
  • 용어
    • 의 원소는 스칼라
    • 의 원소는 벡터
    • 는 벡터합
    • 는 스칼라곱
    • 는 에 대한 벡터공간
• 벡터공간의 예
  • : 에 대한 벡터공간
    • 스칼라의 카테시안도 벡터공간이 된다. 위 8가지 조건을 만족함.
  • : 에 대한 벡터공간
    • 행렬도 벡터공간이 된다. 위 8가지 조건을 만족함.
  • : 에 대한 벡터공간
    • 함수들도 벡터공간이 된다. 위 8가지 조건을 만족함.
  • : 에 대한 벡터공간
    • 수열공간도 벡터공간이 된다. 위 8가지 조건을 만족함.
  • 미지수 에 대하여, , 는 다항식의 덧셈, 는 다항식에 스칼라곱이라 같이 정의하면
    • : 에 대한 벡터공간
  • 를 “합동이면 같은 것으로 보는 유향 선분의 집합”, 는 “평행사변형식 덧셈”, 
  • 는 “길이만 스칼라배 늘리기”로 정의하면
    • : 에 대한 벡터공간
• 벡터공간이라면 다음이 성립한다.
  • 
  • 는 유일하다.
  • 마다, 가 유일하다.
  • 
  • 
  • 
  • 
  • 
  • 
• 벡터공간으로써 구조가 같다.
  • : Vector-space Isomorphic (over )
  • 
    • : 전단사,
      •  
      •  
  • 이때  를 VS isomorphism 이라 부른다.
    • 
  • 
  •