집합론 - about sets and classes

01-01-about sets and classes

before we start…

우리가 알고 있는 모임의 수학적 표현으로의 set 을 이용해 해당 set \(S\) 를 생각 해 보자.

\[S = \text{자기 자신을 원소로 가지지 않는 모든 집합의 집합}\]

이를 좀더 포말하게 작성한다면,

\[S = \{ x:x \text{ is a set, }x \not\in x \}\] 이 된다. 일단 직관적으로 \(S\) 는 set 이라 한다면. “\(S\) 는 자기 자신을 원소로 가지는가?” 라는 질문이 생긴다

[!증명]

우선 \(S \in S\) 라 가정한다, 그러면 저 조건에 의하여, \(S \not\in S\) 를 만족해야 한다, 이는 모순이다.

또한 \(S \not\in S\) 라 가정한다, 그러면 조건의 역인 \(S \in S\) 를 만족해야 한다, 이 또한 모순이다.

즉 이러한 set 은 어떤 상황에도 모순을 만든다는 문제가 생긴다. (이를 러셀의 역설이라 한다.)

그렇다면 여기서 좀더 기초적인 질문이 가능하다.

“Set 이란 엄밀하게 무엇인가?”

이러한 문제를 해결하기 위해. 저멜로,러셀,칸토어 같은 여러 거인들이 다양한 방법으로 집합을 정의함으로써 이 역설을 해결하러 하였다.

그러나 저멜로의 집합에 관한 아이디어는 “베리의 역설” 을 해결하지 못한다는 한계에 부딛히고 말았다.

이후 폰 노이만, 베르나이스, 괴델이 NBG 공리계를 정립해 탄탄한 집합론을 만들었다. 이제 기존의 집합에 대한 관념을 버리고 sound 한 집합론에 대해 알아가 보자.

명제의 성질

우선 집합에 대해 논의하기 전에 기초적인 명제에 대해 알아야 한다

[!정의] 문장

문장이란 분명하게 참/거짓을 판단할수 있는 statement 이다.

“고대는 .대보다 좋다.” , “프랑스 왕은 대머리이다.” , “까마귀는 검다.” 같은 것들을 우리는 명제라고 한다.

계속해서 statement 들을 적어나가기는 비효율적이므로 \(P,Q,R,S\) 등을 사용해서 명제를 표기한다.

[!정의] 부정 (negation)

명제 \(P\) 의 부정은 \(¬P\) 으로 표기하며, \(¬P\) 는 \(P\) 와 반대되는 진리값을 가진다.

now we introduce the truth table,

\(P\) \(¬P\)
t f
f t

이 된다.

[!정의] 논리곱 (Conjunction).

두 명제 \(P,Q\) 에 대하여 \(P \wedge Q\) 는 \(P,Q\) 의 컨정션 이라하고, 이는 \(P,Q\) 전부가 참일떄만 참이다.

이때 우리는 간단하게 \(P\) and \(Q\) 라고 읽는다

\(P\) \(Q\) \(P \wedge Q\)
t t t
t f f
f t f
f f f

를 트루스 테이블로 알수 있게 된다.

[!정의] 논리합 (Disjunction).

두 명제 \(P,Q\) 에 대하여 \(P \vee Q\) 는 \(P,Q\) 의 디스정션 이라하고, 이는 \(P,Q\) 중 하나가 참이거나 둘다 참일때 참이다.

이때 우리는 간단하게 \(P\) or \(Q\) 라고 읽는다

\(P\) \(Q\) \(P \vee Q\)
t t t
t f t
f t t
f f f

[!정의] 함의 (Implication).

두 명제 \(P,Q\) 에 대하여 \(P \implies Q\) 는 \(P\) implies \(Q\) 이라하고, 이는 \(P\) 가 거짓, \(Q\) 가 참일때 뺴고는 전부 참이다.

\(P\) \(Q\) \(P \implies Q\)
t t t
t f f
f t t
f f t

note : \(P \implies Q\) is also read as “\(P\) only if \(Q\)”, “\(P\) is a sufficient condition of \(Q\)”, and “\(Q\) is a necessary condition of \(P\) ”.

명제 \(P \implies Q\) 의 역,이,대우는 각각

\[\begin{aligned} &Q \implies P \\ ¬&P\implies¬Q \\ ¬&Q\implies ¬P \end{aligned}\]

으로 정의된다

[!정리]

\(P,Q\) 가 명제라 하자, 그렇다면 다음이 전부 참이다. \[\begin{align} P \implies P \vee Q \\ Q\implies P \wedge Q \\ P \wedge Q \implies P \\ P \wedge Q \implies Q \end{align}\]

증명은 트루스 테이블을 이용해 보자 (사실 대부분이 트루스 테이블로 처리가 가능하다는 것이지…)

[!정리]

\(P,Q,R\) 을 명제라 하자, \(Q \implies R\) 이 참이라 가정하자, 그러면 다음이 전부 참이다. \[\begin{align} P \vee Q \implies P \wedge R \\ P \wedge Q \implies P \wedge R \end{align}\]

[!warning]

위에서는 “\(Q\implies R\) 이 참이라 가정하자…” 라고 거창하게 적었지만 이제부터는 간단하게 \(Q\implies R\) , 라고만 적는다

[!정리] Transitive law

명제 \(P,Q,R\) 에 대해서, \[[(P \implies Q)\wedge (Q\implies R)] \implies (P \implies R)\]

증명은 조금 스마트하게 해보자 저 왼쪽에 있는 두 implication 이 하나만 거짓인 경우에는 무조건 참이므로, 저 두 implication 이 참인 케이스만 따져서 트루스 테이블을 보면 된다는 것이다.

그리고 이제부터는 \((P \implies Q) \wedge (Q\implies P)\) 를 \(P \iff Q\) 으로 적는다. (사실은 \(=\) 을 뜻함은 ball knower 라면 다들 알것이다.)

[!정리] Many laws

  1. (idempotent law) \[P \vee P \iff P\]
  2. (idempotent law) \[P \vee P \iff P\]
  3. (commutative law)\[P \vee Q \iff Q \vee P\]
  4. (commutative law) \[P \wedge Q \iff Q \wedge P\]
  5. (associative law) \[P \vee (Q \vee R) \iff (P \vee Q) \vee R\]
  6. (associative law) \[P \wedge (Q \wedge R) \iff (P \wedge Q) \wedge R\]
  7. (distributive law) \[P \wedge (Q \wedge R) \iff (P\wedge Q) \wedge(P\wedge R)\]
  8. (distributive law) \[P \vee (Q \wedge R) \iff (P \vee Q) \wedge (P \vee R)\]

스마트하게 트루스 테이블을 이용해서 증명하면 된다~

또한 \[ \begin{aligned} &P \iff ¬(¬P)\\ &¬(P \wedge Q) \iff ¬P \vee¬Q\\ &¬(P \vee Q) \iff ¬P \wedge ¬Q \end{aligned} \] 도 증명하는 연습을 해보자.

클레스와 집합

이제부터 진짜 set 에 대해 다룬다

[!정리] Undefined notion (Class, \(\in\))

  1. “Class” 는 정의되지 않은 개념이다.
  2. “Membership relation” aka \(\in\) 은 정의되지 않은 개념이다.

충격적인 사실이지만, 모임과 원소 관계는 정의되지 않은 개념이다. 하지만 그래도 상관 없다! 다른 공리들을 이용해서 모든것을 따져볼수 있게 된다!

하지만 직관적으로는 class 는 적당한 모임으로 봐도 무방하다.

Set & proper class

[!정의] Set

어떤 클래스 \(x\) 에 대하여, \(x \in A\) 를 만족하는 클래스 \(A\) 가 존재한다면, \(x\) 는 집합 또는 원소 이다. i.e.

\[ x \text{ is a set (element) } \iff \exists A_{\text{class}} \text{ such that } x \in A_{\text{class}}\]

충격적이지만, 집합이 원소이고 원소가 집합이다!!!!!!!!

[!정의] Not in

\(x \not\in A\iff¬(x \in A)\)

[!정의] Proper class

\(X \text{ is a proper class} \iff \forall A_{\text{class} } ~X \not\in A_{class}\)

정리 하자면, class 에 하위 개념으로 “집합” 과 “proper class” 가 있다고 보면 된다 (당연히 상호 부정적이다.)

이제부터는 \(a,b,c,x,y,z\) 같은 소문자는 집합, \(A,B,C,X,Y,Z\) 같은 대문자는 class 를 나타내기로 약속한다.

위에서 언급한 러셀의 역설도 이 개념을 이용해 해결이 가능하다 \(S\) 가 set 이라면 말이 안되지만, \(S\) 가 proper class 면 \(S \not\in S\) 으로 정리된다. (모든 class 에 대해 원소가 될수 없는것이 proper class 의 정의니까!)

기존의 \(S\) 를 처리하려던 관점에서 보면, 거대한 모임을 proper class 으로 처리한다는 생각을 엿볼수 있다.

Axiom of extent

이젠 클래스 들 (즉, 어떤 모임들) 이 같다는 것을 정의해야 한다.

[!정의] 클래스의 같음

클래스 \(A,B\) 에 대해, \[ (A =B) \iff \forall X ,~(A \in X \iff B \in X)\]

이 정의를 조금 비틀면, \((A = B) \iff \forall X, ~ (A \not\in X \iff B \not\in X)\) 를 얻는다! 이때, \(A,B\) 둘다 프로퍼 클래스 라고 가정하자, 그렇다면 \(A=B\) 라는 결론을 얻는다! 즉, 저 정의만으로는 프로퍼 클래스 간의 구분이 불가능 하다는 문제점이 생긴다 그렇기 때문에 우리는 (좀더 직관적인!) 또다른 방법으로 클래스를 구분한다.

[!공리] Axiom of extent

\[(A=B) \iff (x \in A \iff x \in B)\]

증명에서는 대부분 axiom of extent 를 응용하게 된다.

Subclass and subset

[!정의] Subclass

\[A \subset B \iff (x \in A \implies x \in B)\] 이며, 이떄 \(A\) 는 \(B\) 의 subclass 이라고 한다

또한 \(A\subsetneq B\) 는 \(A \subset B \wedge A \neq B\) 를 뜻하며 \(A\) 는 \(B\) 의 strict subclass 이라고 한다.

이때 \(A \subset B\) and \(A\) is a set 이라면 \(A\) 는 \(B\) 의 subset 이라고 한다.

[!연습]

prove that \((A \subset B \wedge B \subset A )\iff (A=B)\)

[!증명]

by definiton and axiom of extent, \((A \subset B \wedge B \subset A ) \iff [(x \in A \implies x \in B) \wedge (x \in B \implies x \in A) ]\iff (x \in A \iff x \in B) \iff A=B\)

앗 그렇다면 set 의 subclass 는 set 일까? 고민해 보자.

증명하기 너무 어려워 보인다! 그렇기 때문에 그냥 공리를 추가한다.

[!공리] Axiom of subset

set 의 subclass 또한 set 이다.

Axiom of class construction

그럼 우리는 이런 고민을 하게 된다. “지금까지 \(S = \{ x : x \not\in x \}\) 같은 것들을 다루고 있었는데, \(S\) 가 class 라는 보장은 어디에 있지?”

이러한 고민을 해결하기 위해 수학자들은 새로운 공리를 추가했다.

[!공리] Axiom of class construction

\(P(x)\) 가 \(x\) 에 대해 포말한 스테이트먼트라 하자, i.e. \(P(x)\) 는 오직 \(\in,\vee,\wedge,\neg,\implies,\exists,\forall\),괄호들, 변수 (\(x,y,{z}\dots\)) 으로만 작성이 가능하다, 면 이 \(P(x)\) 를 만족하는 모든 \(x\) 를 원소로 가지는 class \(C\) 가 존재 한다, 간단하게 말해서, class \(\{ x : x \text{ is an element and satisfies } P(x) \}\) 가 존재한다.

중요한건 저 axiom 에서 설명하는 class 만 class 라는것이 아니다!** 저 axiom 에서 설명하는 class 는 확실하게 class 임이라는 것이다,

추가로 \(s.t.\) (such that) 도 \(P(x)\) 에서 많이 쓰이는데 \(s.t.\) 기호는 \(\ni\) 이고 이는 \(\in\) 을 뒤집은 거니까 써도 상관이 없다 zzz

Class operations

[!정의] Intersection

\[A \cap B = \{ x : x \in A \wedge x \in B \}\]

[!정의] Union

\[A \cup B = \{ x: x \in A \vee x \in B \}\]

[!정의] Complement

\[A^c = \{ x ; x \not\in A \}\]

[!정의] 뺄샘

\[A -B = A \cap {B}^{c} = \{ x : x \in A \wedge x \not\in B \}\]

이 오퍼레이션의 결과물은 axiom of class constrution 에 의해 class 임이 보장된다.

\(\emptyset\) 과 \(\mathcal{U}\)

[!정의] Universal class

\[\mathcal{U} = \{ x: x=x \} \]

[!정의] Empty class

\[\emptyset = \{ x:x\neq x \}\]

이 둘 전부 axiom of class construction 에 의해 class 임이 보장된다.

여기서 아무 생각 없이 \(\mathcal{U}, \emptyset\) 이 set 이라고 착각하지 말고 class 인지 set 인지 고민해 보자.

[!정리]

\[ \begin{align} \emptyset \subset A \tag{1}\\ A \subset \mathcal{U} \tag{2}\end{align}\] 가 모든 \(A\) 에 대해 참이다.

[!증명]

  1. by definiton, \(\emptyset \subset A \iff (x \in \emptyset \implies x \in A) \iff (x \not\in A \implies x \not\in \emptyset)\) and since \(\forall x \not\in A,\neg(x\neq x)\) is true, \(x \not\in A \implies x \not\in \emptyset\) is true

  2. by definition, \(A \subset \mathcal{U} \iff (x \in A \implies x \in \mathcal{U})\) which is true since \(\forall x \in A,x=x \therefore x \in \mathcal{U}\)

[!공리] Axiom of empty set

\(\emptyset\) 은 set 이다!

이제 \(\mathcal{U}\) 가 proper class 임을 보이자.

[!증명] \(\mathcal{U} \text{ is a proper class}\)

assume that \(\mathcal{U}\) is a set, since \(S \subset \mathcal{U}\), by axiom of subset, \(S\) becomes a set, which is contradiction, therefore \(\mathcal{U}\) is a proper class.

“Tons”

[!정의] 싱글톤, 더블톤

  1. A class containing only a single element is called a “singleton”.
  2. A class containing two elements is called an “unordered pair” or a “douleton”.

싱글톤 더블톤 둘다 axiom class construction 에 의해 class 임이 보장된다.

싱글톤과 더블톤은 과연 set 일까? proper class 일까? 이렇게 작은 class 는 분명 set 이라는 직관이 작용한다.

[!공리] Axiom of doubleton

\(\{a,b\}\) 에서 \(a,b\) 가 set 이면 \(\{a,b\}\) 도 set 이다.

[!정리]

singleton \(\{a\}\) where \(a\) is a set(element) is a set

[!증명]

by axiom of doubleton, \(\{a,b\}\) 은 set 이다. \(\{a\} \subset \{a,b\}\) 이므로, axiom of subset 에 의해서 \(\{a\}\) 도 set 이다.

이떄 더블톤이 unordered pair 이므로 ordered pair 는 어떻게 정의할까?

[!정의] Ordered pair

순서쌍 \((a,b)\) 는 \[(a,b) = \{ \{ a \},\{a,b\} \}\] 으로 정의한다.

axiom of doubleton 을 이용하면 \((a.b)\) 도 set 임을 쉽게 증명 가능하다.

그래프

[!정의] 카티잔 프로덕트

\[A \times B = \{ (x,y) : x \in A \text{ and } y \in B \}\]

[!정의] 그래프

\(\mathcal{U} \times \mathcal{U}\) 의 subclass 를 그래프라고 한다.

앗! 평면도 그래프! 곡선도 그래프! 점 하나도 그래프!

[!정의] Inverse of graph

let \(G\) be a graph, \[G ^{-1} = \{ (y,x) : (x,y) \in G \}\]

[!정의] 합성

\(G,H\) 가 그래프라고 하자, \[G \circ H = \{ (x,y): \exists z \ni(x,z) \in H \wedge(z,y) \in G \}\]

\(\ni\) 는 “such that” 을 뜻하는 기호다.

[!정의] Domain and range

\(G\) 를 그래프라 하자, \[\begin{align}dom (G) = \{ x : \exists y \ni (x,y) \in G \} \\ ran (G) = \{ y : \exists x \ni (x,y) \in G \} \end{align}\]

이때 둘을 각각 \(G\) 의 도메인, 레인지 라고 한다.

그래서 이제 이걸 이용해 무엇을 하죠?

그건 이제 다음 글에서 문제를 풀면서 생각해 본다.

댓글

댓글도 $\displaystyle \LaTeX{} $ 를 지원합니다!
\$(latex code)\$ 로 수식을 입력하세요!

post-of-the-week

해석학- 집합의 성질들

이미지
01-01-집합의 성질들 Before We Start… 우리는 지금까지 미적분학 을 배우면서 practical 한 수학에 있었다. 특히 벡터 미적분학은 물리를 위한 수학이라고 불러도 무방할 정도로 물리와의 깊은 연관을 보여주었다. 하지만 우리는 물리학자가 아닌 수학자, 결국 순수수학의 세상으로 빠질 대비가 필요해진다. 이런 “수학으로의 빠짐” 의 초석이라 할수있는 해석학 을 시작해 보자. 우선 아주 중요한 사실 하나를 집고 넘어가도록 하자, 그건 바로 이 세상의 모든건 추상 을 통해 만들어진 것이다. 즉 우리는 이제부터 자연수, 유리수 ,정수를 전부 우리가 엄밀한 정의 를 통해서 만들어낸 대상 으로 보아야 한다는 것이다. 실수의 정의 (“건축”) [!정의] \[\begin{align*} &\mathbb{N} = \{ 1,2,3, \cdots\} \\ &\mathbb{Z} = \{ \dots -3,-2,-1 , 0 ,1,2,3,\cdots \} \\ & \mathbb{Q} = \left\{ \frac{n}{m} ~|~ n,m \in \mathbb{Z} , m \neq0\right \} \end{align*} \] 을 통해서 우리는 자연수,정수,유리수를 정의했다. 이정도면 충분하게 많은 종류의 수들을 “정의” 했다고도 할수 있지만, 아직 우리는 많이 부족하다. \(x^2 =2\) 를 만족하는 해 \(x\) 가 존재하는가? 라는 질문에 대해 우리는 (귀류법을 통해서) “그런 유리수는 없다” 라는 답변을 얻는다. 하지만 여기서 “위 식을 만족하는 새로운 수” 를 “정의” 할수 있게 된다 . (이것이 실수!) 1 우선 실수의 formal 한 정의를 알아보도록 하자. 해석학의 스탠다드 교제인 루딘의 책에 따르면 실수 \(\mathbb{R}\) 는 “ \(Q\) 를 부분집합으로 가지는 최소상계 성질(least-upper-bound property)을 가지는 순서체(ordered field)” 이라...
Read more »

미분방정식- 1차와 2차 방정식

01-01 - 1차와 2차 미분방정식 Preface \(u,v,w,g,y,p,q ,\psi\) 는 \(t\) 에 대한 함수라는 약속을 하고 시작해 보자. 마찬가지로 \(\frac{du}{dt} = \dot{u}, \frac{d^2u}{dt^2} = \ddot{u} \cdots\) 라고 적어야 하겠지만 여기서는 \(u',u'' \cdots\) 라고 적자. 모든 방정식은 \(y\) 를 \(t\) 에 대해 닫힌 형식으로 기술하는것이 목적이 된다. [!note] 해를 제시할 때 그 해가 성립하는 구간을 잡아야 한다 , \(\frac{1}{t}\) 같은 것이 해라면, “ \(0\) ” 은 우리가 제시하는 구간에 없어야 한다. ( \(t \in (0,1]\) 처럼) [!tip] 최고차항의 계수를 1로 만든 표준형 \(y'' + p(t)y' + q(t)y = g(t)\) 에서, 해가 존재하는 구간 \(I\) 는 \(p(t), q(t), g(t)\) 세 함수가 동시에 연속이면서, 초기값 \(t_0\) 를 포함하는 가장 넓은 구간 이다. 그렇기에 해의 존재 구간은 방정식의 계수들을 표준형으로 나눴을 때, 분모가 0이 되는 점(Singular point)이나 로그의 진수 조건 등을 뚫고 지나갈 수 없다. 반드시 초기값 \(t_0\) 가 속한 연속 구간으로 쪼개서 대답해야 한다. Before We Start… 미분 방정식은 사실 너무 실용적인 과목이라 배워야 할 이유를 설명할 필요가 없다!! 1차 선형 상미분방정식 \(y' + py=g\) 이 꼴을 1차 선형 ODE 라고 한다 note that \(D_{t}(e^{ A }y)=e^A(y'+A')\) \(\therefore e^{ \int p(t) }(y'+p(t)y)=e^{ \int p(t) }(g(t))\) 을 이용한다, 그러므로 \(e^{ \int p(t)}(y)=\int_{dt} g(t...
Read more »

블로그 테마 패치 노트

이 테마를 쓰고 싶으시다면 여기서 받아가세요 Most Recent Release V3.141 \(+ \epsilon\) added custom comment section implemented smart caching to the search feature no more having to wait for the indexing to finish everytime you enter a new page alot of small bug fixes 참조 기능 증명, 정리 등등을 recall 할 때 편리한 기능 눌러봐 눌러봐2 이것도 눌러봐주세요 공지기능 이제부터 원하는 글을 최대 3개까지 “공지” 태그를 달아 홈 화면 상단에 핀 할 수 있음. 위키링크 기능 추가 linux mint 사용기 - 내가 쓰는 키보드 설정 처럼 호박색 하이라이트 는 위키링크를 의미함. 이때 저 링크를 클릭시 해당 글이 검색창에 검색됨 이런거도 되지롱 옵시디안 콜아웃들 이제부터 옵시디안 콜아웃 을 전부 지원함 [!note] 콜아웃이다 [!info] 콜아웃이다 [!todo] #투두1 콜아웃이다 눌러보셈! [!abstract] 콜아웃이다 [!summary] 콜아웃이다 [!tldr] 콜아웃이다 [!tip] 콜아웃이다 [!hint] 용을 입력하세요. [!important] 콜아웃이다 [!success] 콜아웃이다 [!check] 콜아웃이다 [!done] 콜아웃이다 [!question] 콜아웃이다 1 [!help] 콜아웃이다 [!faq] 콜아웃이다 [!warning] 콜아웃이다 [!caution] 콜아웃이다 [!attention] 콜아웃이다 [!failure] 콜아웃이다 [!fail] 콜아웃이다 [!missing] 콜아웃이다 [!danger] 콜아웃이다 [!error] 콜아웃이다 ...
Read more »