집합과 명제 편집하기 (부분)

===집합 잡설===
{{노잼}}

이 아래로 전부 개소리다. 멍멍 왈왈

누군가 집합론 문서를 만든다면 필히 이 내용들을 가져가길 바란다 아님 이 문서를 집합론이라고 생각하자

------------------

실수 몇개로 이루어진 집합 A는 실수집합 R에서 dense하다 when

모든 개구간이 A의 점을 포함할때, 즉 R에서 아무 두 점을 골랐을때 그 사이에 A의 점이 있으면.

ex)유리수 집합 Q는 R에서 dense하다

모든 실수는 무한소수로 표현될수 있기에, 그 사이의 한 유리수를 택할 수 있다(0.85=0.84999..)


* 유계집합

A가 실수 몇 개의 집합이라 하면

A는 1)유계다 2)위로 유계다 3)아래로 유계다 according as M이란 실수가 있는데

모든 x∈A에 대해 1)|x|≤M 2)x≤M 3)M≤x 일때.

M은 1)bound 2)upper bound 3)lower bound라 한다.

A가 유계다 ⇔ A가 어떤 유한구간의 부분집합이다

A가 유한집합이면 A는 bounded하고

A가 무한집합이면 A는 bounded하거나 bounded from above(below)거나 unbounded하다

ex)A={1,1/2,1/3,...1/n,...}는 [0,1](구간) 의 부분집합이기에 A는 무한집합이고, bounded하다

unbounded는 bounded만 아니면 unbounded하다 한다.

공집합은 bounded할까??

[[추가바람]]

두 유계거나 위로 또는 아래로 유계인 집합의 교집합과 합집합은 각각의 원래의 성질을 만족한다.

두 unbouded한 집합의 교집합은 bounded할수 있고 unbounded할수 있지만 합집합은 unbounded하다.


* least upper bound(or supremum)

A가 실수 몇 개의 집합이라 하면

어떤 실수 M은 least upper bound or supremum of A(denoted by Sup(A))라 한다,

M은 A의 upper bound이고 M보다 더 작은 수가 A의 upper bound가 되지 못할때.

(Sup은 실수에서 따진다)

Completion property of R

If a set A of real numbers is bounded from above, sup(A) exists.

이딴게 뭐라고..

ex)A={x∈Q, x＞0, x^2＜3}은 bounded인게 분명하지만 sup(A)는 없다.

루트3은 무리수이고, A는 유리수 집합이기에.

그니까 유리수는 Complete하지 않다는데, 이런건 응딩이같은 거다. 냄새난다고.


* 곱집합

두 집합 A,B에 대해 AxB={(a,b):a∈A,b∈b}로 정의한다. 순서쌍들의 집합이다.

AxA=A^2

AxB는 BxA와 다르다.

n(AxB)=n(A)xn(B) for any 유한집합 A, B

m개의 집합 A1, A2,...,Am의 곱집합도 생각할 수 있다(ai∈Ai)(a1,a2,..,am) 

중복순열 기호에 오른쪽 위에 m, 아래에 i=1을 쓰고 그 옆에 Ai로 denote된다

A^n=AxAx...A(A n개)

(AxB)n(AxC)=Ax(BnC)


*Relation(or Binary relation)

두 집합 A,B에 대해

Relation from A to B 은 AxB의 부분집합이다.

a∈A, b∈B에 대해 R이 relation from A to B일때

1)(a,b)∈R; a is R-related to b, denoted by aRb

2)(a,b)∈/R; a is not R-related to b, denoted by aR/b(∈/은 그 기호 안써져서, R/은 R 중간에 그은거)

Domain of R은 R 안의 순서쌍들의 첫째 수들의 집합, Range of R은 R안의 순서쌍들의 둘째수의 집합

R이 A to A의 Relation 이면 R is a relation on A라 함


* Universal relation, Empty relation, Equality relation

A를 어떤 집합이라 하면, AxA, 공집합,은 AxA의 부분집합이고 relations on A이다.

각각 Universal relation, Empty Relation이라 한다.

Any relation R on A, 공집합⊆R⊆AxA

Equality relation은 {(a,a):a∈A}이다



* Inverse Relation

R을 A to B의 any relation이라 하자

inverse of R (R-1 그 역함수기호) is relation from B to A which is R-1={(b,a):(a,b)∈R}

ex) R={(1,a),(2,c)} R-1={(a,1),(c,2)}

(R-1)-1=R

Domain of R은 Range of R-1이고, and vice versa

If R is a relaion on A, R-1 is also a relation on A


* Composition of Relations

A,B,C are sets. R is relation from A to B, S is relation from B to C.

RoS(o는 가운데에 작은 동글뱅이)={(a,c):there exists b∈B for which (a,b)∈R and (b,c)∈S}

a(RoS)c whenever there exists b∈B such that aRb and bSc

RoS is called the composition of R and S

Theorem)A,B,C,D are sets.

R is relation from A to B, S is " from B to C, T is from C to D,

(RoS)oT=Ro(SoT)

prove)RoS에 속하는 원소 (a,c) 그리고 T에 속하는 원소 (c,d)에 대해서,

(a,b)가 R의 원소, (b,c)가 S의 원소여야 하므로 SoT에 (c,d)가 속해서 좌변은 우변의 부분집합이다를 증명할 수 있다.

거꾸로도 성립한다.

if R is a relation on A, RoR can be defined, and sometimes denoted by R^2

so on R^3,...R^n. R^n can be defined for all 자연수 n


아래 4개의 relation들은 전부 on A인데 두 집합이 다르면 굳이 저걸 생각하는 의미가 없기 때문이다

* Reflexive relation: A relation R on a set A is reflexive if aRa for every a∈A

A에 안속하는 (a,a)가 R에 있으면 그건 Reflexive가 아니다 근데 어차피 R은 A^2의 부분집합이므로 (a,a)꼴의 원소만 있어야 한단 거다.

equality relation은 얘의 부분집합이라 할 수 있겠다.

* Symmetric relation : A relation R on a set A is symmetric if aRb then bRa 

aRb인데 bR/a이면 symmetric이 아니다

* Antisymmetric relation : A relation R on a set a is antisymmetric if aRb and bRa then a=b

aRb, bRa인데 a=/=b이면 antisymmetric이 아니다

중요한? 건 예를 들어 A={1,2,3,4}, R={(1,3),(2,1)}인 경우 이건 비대칭이다 애초에 aRb이고 bRa인게 없어서

그래서 공집합은 대칭, Transitive, 비대칭관계이지만 Reflexive는 아니다

나머지 3개는 전부 가정->결론의 조건문이지만 Reflexive는 원소가 있어야 하기에

* Transitive relation : A relation R on a set A is transitive if aRb and bRc then aRc

aRb이고 bRc인데 aR/c이면 transitive하지 않다 당연히 a=c여도 된다 예를 들어 A={1,2,3}에 대해 R={(1,2)}도 transitive하다 

가정이 F니까

나는 잘 와닿지 않으니 예를 들어 비교해보자.

R1~R5 is a relation on A, A={1,2,3,4}

R1={(1,1),(1,2),(2,3),(1,3),(4,4)}<br>
R2={(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)}<br>
R3={(1,3),(2,1)}<br>
R4=공집합(empty relation)<br>
R5=AxA(universal relation)<br>

우선 reflexive<br>
reflexive가 되려면 1,1 2,2 3,3 4,4 네개 다 있어야 한다 고로 R2와 R5만이 reflexive이다

다음 symmetric<br>
R1엔 2,1 과 3,2 와 3,1 이 있어야 symmetric이다. R2는 맞고 R3는 아니고 R4,R5는 맞다.

antisymmetric

R1은 1,1 과 4,4가 있으니 antisymmetric이다. 왠지 reflexive의 부분집합 일수도 있을것 같다. R2는 1,2와 2,1이 있기에 아니다.<br>
R3는 가정->결론 조건문에서 가정을 부정했으니 맞다 할 수 있겠다. R4도 그렇고, R5는 1,2와 2,1같은게 있으니 아니다.

마지막으로 transitive

R1은 (1,1)->(1,3)=(1,3) / (1,2)->(2,3)=(1,3)이니 transitive하다 R2도 그렇고 R3는 (2,1)->(1,3)=(2,3)인데 이게 없다 고로 아니다.<br>
R4는 맞고 R5도 맞다 모든걸 다 갖고 있을테니.

* P-closure

P가 아니라 무슨 필기체 P인데 나는 특수문자 찾기 귀찮으니 넘어가도록 하자

P를 예를들어 transitive나 reflexive같은 관계의 성질이라 하자. 집합 A에서 정의?된 임의의 관계에 대해

P성질을 가진 관계를 P-relation이라 하자. 그리고 R을 P성질이 없는 관계 on A라 하자.

그러면 P-closure of R, P(R)이라 쓰고, 은 R을 포함하는 집합 A에서의

R⊆P(R)⊆S 이런 관계이다. S는 P 성질을 갖고 R을 포함하는 임의의 A에서의 관계. R이 P성질을 가진다면 R=P(R)이다.

reflexive(R) 뭐 이런식으로 쓴다 이거다. 얘네도 집합이다.

reflexive와 symmetric closure을 얻는 방법은 이렇게도 생각할 수 있다

★집합 A에서의 임의의 관계 R에 대해
(△a는 집합 A에서 equality relation)(R-1은 inverse)<br>
-Ru△a는 R의 reflexive closure, reflexive(R)이다<br>
-Ru(R-1)은 R의 symmetric closure, symmetric(R)이다

나는 이해가 잘 안 되니 예를 들어 생각해 보자.

예를 들어 A={1,2,3,4}에서 정의된 관계 R={(1,1),(1,3),(2,4),(3,1),(3,3),(4,3)}에 대해

reflexive(R)은 (2,2)와 (4,4)를 우겨넣은 거고

symmetric(R)은 (4,2),(3,4)를 우겨넣은 거다


★Transitivie closure

R을 집합 A에서의 관계라 하고, R{{위첨자|2}}를 R 둘의 합성, R{{위첨자|n}}을 R n개의 합성(=R{{위첨자|n-1}}에서 R로의 합성)이라 하자.

이때 R{{위첨자|*}}을 R, R2, R3, ...R{{위첨자|∞}}들의 합집합이라 하면

R{{위첨자|*}}은 R의 transtivie closure이다.

집합 A가 n개의 원소로 이루어진 유한집합이면, R{{위첨자|*}}은 R, R2, R3, ...R{{위첨자|n}}들의 합집합이라 할 수 있겠다.

그리고 R이 그런 A의 한 관계이면 R, R2, R3, ...R{{위첨자|n}}들의 합집합이 R의 transitive closure이다.

솔직히 뭐라는지 모르겠다 대충 넘어가자.

뭐 간단한 예를 들면

R이 A={1,2,3}의 관계 R={(1,2),(2,3),(3,3)}이라 하자. 그럼 transtive(R)을 어떻게 찾나면

R{{위첨자|2}}={(1,3),(2,3),(3,3)}(합성된 원소만 갖고있음), R{{위첨자|3}}={(1,3),(2,3),(3,3)}이고

transitive(R)은 R1UR2UR3={(1,2),(1,3),(2,3),(3,3)}이다.

재미없는 문제

A={1,2,...,n}에 대해 n개의 순서쌍을 가진 관계 R의 transitive closure이 AxA가 되게 만드는 R을 찾아보자

답은 {(1,2),(2,3),...(n-1,n),(n,1)}이다. 잘 보면 저걸 한번 합성하면 (1,3),(2,4)...,(n,2) 이렇게 간격이 1씩이었던게 2씩 된다

한번 더 하면 (1,4),(2,5),....(n,3) 이렇게 3이 되고 4가 되고 ... 결국 AxA의 모든 원소를 모을 수 있게 된다 졷같다

아 샛스


*Partition(그 분할 맞다)

여기선 단순히 집합의 분할의 수를 세는 게 아니라 좆같은걸 이야기한다

임의의 공집합이 아닌 집합 S에 대해 S의 partition은 P={A{{아래첨자|i}}}에 대해

1)모든 a∈S가 A{{아래첨자|i}} 중 하나에 속하고

2)A{{아래첨자|i}}=/=A{{아래첨자|j}}이면 A{{아래첨자|i}}nA{{아래첨자|j}}=공집합 인 거다

그니까 그냥 분할이다

무슨 system representative는 부랄탕이다

*Equivalence relation

그냥 symmetric, refelxive, transitive하면 equivalence relation이다

뭐 a≡b(mod m) (m은자연슈 ab는정수)는 equivalence relation이라고 한다.

*Equivalence class

S의 equivalence relation R에 대해

[a]={x:(a,x)∈R} 를 equivalence class of a in S under R 이라고 한다

그냥 동치관계에서 어느 하나의 정의역에 대한 치역집합이다

*quotient set

위의 equivalence class에서 모든 equivalence class들의 집합을, S/R={[a]:a∈S}이라 쓰고, 이걸 quotient set of S by R 이라 쓴다

R이 S의 equivalence relation이라 하면 quotient set S/R은 S의 한 분할이라고 한다.

증명)

S/R이 S의 partition이려면

each a∈S, a∈[a] / If [a]=/=[b], then [a]n[b]=Ø 이 두 가지를 밝히면 된다

1)each a∈S, a∈[a]는 R이 reflexive하기에, (a,a)∈R이라 알 수 있다

2)If [a]=/=[b], then [a]n[b]=Ø의 대우는 If [a]n[b]=/=Ø then [a]=[b]인데

∃x∈S, (a,x)∈R and (b,x)∈R이어야 한다 disjoint아니니까

여기서 R이 symmetric하기에 (x,a)∈R, (x,b)∈R이고

R이 transitive하기에 (a,b)∈R, (b,a)∈R이다

즉 ∃x∈S, [a]={a,b,x}=[b]가 되어 대우가 증명되었다

어떤 분할에 대해 그것과 같은 quotient set이 존재한다는 것도(역) 있는데 다음시간에


*Partial Ordering Relation

그냥 equivalence에서 symmetric떼고 antisymmetric 넣은거다

ex)relation ⊆ of set inclusion

1) A⊆A for any set A<br>
2) if A⊆B and B⊆A, A=B<br>
3) if A⊆B and B⊆C, A⊆C

ex2)relation 'A divides B' for set of positive integer but not for set of integer

3 divides -3 and -3 divides 3 but 3=/=-3