관계와 함수

by LY4I
60 views

거듭제곱집합과 데카르트 곱

ZF6. 거듭제곱집합 공리; Power set axiom.

x가 집합이라고 하자. 그러면 x의 모든 부분집합만을 원소로 갖는 집합이 존재한다.

x가 집합일 때 x의 모든 부분집합만을 원소로 갖는 집합은 유일하다. 그러므로 다음과 같이 정의한다.

정의 1. x가 집합일 때, x의 모든 부분집합만을 원소로 갖는 집합을 x거듭제곱집합(power set) 또는 멱집합이라고 부르고, P(x)로 나타낸다.

거듭제곱집합 공리 덕분에 집합의 데카르트 곱을 정의할 수 있다.

정리 2. XY가 집합이라고 하자. 그러면 xX, yY를 만족시키는 모든 순서쌍 x,y를 원소로 갖는 집합이 존재한다.

증명

거듭제곱집합 공리에 의하여 P=P(P(XY))는 집합이다. 이제 xX, yY라고 하자. 그러면 {x}P(XY),{y}P(XY) 이므로 x,y={{x},{x,y}}P(P(XY))=P 이다. Z={zP|xy(xXyYz=x,y)} 라고 하면, 분류 공리꼴에 의하여 Z는 잘 정의된 집합이며 정확히 xX, yY를 만족시키는 모든 순서쌍 x,y를 원소로 가진다.

정리 2의 증명에서 XY가 정해질 때마다 집합 Z는 하나로 정해진다.

정의 3. XY가 집합이라고 하자. 이때 xX, yY를 만족시키는 모든 순서쌍 x,y만을 원소로 갖는 집합을 XY데카르트 곱(Cartesian product)이라고 부르고 X×Y로 나타낸다.

관계와 함수

정의 4. XY가 집합이라고 하자. 이때 X×Y의 부분집합 R를 ‘XY 사이의 관계(relation)’라고 부른다. 특히 XX 사이의 관계를 간단하게 ‘X 위에서의 관계’라고 부른다. RXY 사이의 관계일 때, x,yR를 간단하게 xRy와 같이 나타낸다.

정의 5. RXY 사이의 관계라고 하자. 만약 임의의 xX에 대하여 [x,yRyY가 유일하게 존재]하면, RX로부터 Y로의 함수(function)라고 부른다. 만약 fX로부터 Y로의 함수이면, x,yf를 간단히 y=f(x)와 같이 나타낸다. 함수를 사상(map)이라고 부르기도 한다.

FA로부터 B로의 함수라는 것을 L의 논리식으로 나타내면 다음과 같다. (FA×B)x(xAy((yB)(x,yF)z(x,zFz=y))) XY 사이의 모든 관계의 모임은 P(X×Y)이므로 집합이다. 함수는 관계의 일종이므로, 모든 함수의 모임 또한 집합이다.

정의 6. XY가 집합이라고 하자. 이때 X로부터 Y의 모든 함수만으로 이루어진 집합을 YX로 나타낸다.

f가 함수일 때 f정의역(domain)을 다음과 같이 정의한다. Dom(f)={xf|yf(x,yf)} 또한 f치역(range)을 다음과 같이 정의한다. Ran(f)={yf|xf(x,yf)} fX로부터 Y로의 함수일 때 f의 치역을 f[X]와 같이 나타내기도 한다.

XY가 집합일 때, fX로부터 Y로의 함수인 것을 f:XY와 같이 나타낸다. 편의상 별다른 언급이 없으면 f의 정의역이 X인 것으로 약속한다. 즉 Dom(f)=X인 것으로 약속한다.

함수는 순서쌍의 모임이다. 그러므로 두 함수 f:XYg:XZ가 같다는 것은 두 집합 fg가 같다는 것을 의미한다. 이때 두 함수의 공역 YZ가 서로 일치하는지 여부는 상관없다. f=g로부터 얻는 것은 f[X]=g[X]라는 사실과 f[X]YZ의 부분집합이라는 사실뿐이다.

함수의 정의에 따르면 으로부터 으로의 함수이다. 또한 으로부터 으로의 함수는 뿐이다. 그러므로 ={}이다.

동등관계와 순서관계

동등관계와 순서관계는 함수와 더불어 수학에서 가장 많이 사용되는 관계이다.

정의 7. EX 위에서 정의된 관계라고 하자. 이때 다음과 같이 정의한다.

  1. 임의의 xX에 대하여 x,xE가 성립하면, E반사적 관계(reflexive relation)라고 부른다.
  2. X의 임의의 원소 x, y에 대하여, x,yE일 때마다 y,xE가 성립하면, E대칭적 관계(symmetric relation)라고 부른다.
  3. X의 임의의 원소 x, y, z에 대하여, [x,yE이고 y,zE]일 때마다 x,zE가 성립하면, E추이적 관계(transitive relation)라고 부른다.

만약 E가 위 세 조건을 모두 만족시키면, EX 위에서 정의된 동등관계(equivalent relation)라고 부른다. 동등관계를 동치관계라고 부르기도 한다.

정의 8. RX 위에서 정의된 관계라고 하자. 이때 다음과 같이 정의한다.

  1. X의 임의의 원소 x, y에 대하여, [x,yR이고 y,xR]일 때마다 x=y가 성립하면, R반대칭적 관계(antisymmetric relation)라고 부른다.
  2. R가 반사적이고 반대칭적이며 추이적인 관계일 때 R약한 반순서관계(weak partial order)라고 부른다.
  3. R가 약한 반순서관계라고 하자. 만약 X의 임의의 두 원소가 비교 가능하면, 즉 X의 임의의 원소 x, y에 대하여 x,yR 또는 y,xR가 성립하면, R약한 전순서관계(weak total order)라고 부른다.
  4. 임의의 xX에 대하여 x,xR가 성립하면, R반반사적 관계(irreflexive relation)라고 부른다.
  5. R가 반반사적이고 추이적인 관계라고 하자. 만약 X의 임의의 원소 x, y에 대하여, x,yRy,xR가 성립하면, R강한 반순서관계(strict partial order)라고 부른다.
  6. R가 강한 반순서관계라고 하자. 만약 X의 서로 다른 임의의 두 원소 x, y에 대하여 x,yR 또는 y,xR가 성립하면, R강한 전순서관계(strict total order)라고 부른다.

정리 9. SX 위에서 정의된 강한 반순서관계라고하자. 그러면 R=S{x,x|xX}X 위에서 정의된 약한 반순서관계이다. 여기서 만약 S가 전순서관계이면 R도 전순서관계이다.

증명

주어진 관계가 정의 8의 조건을 만족시키는지 점검해 보면 된다.

동등관계를 나타낼 때와 마찬가지로 순서관계를 나타낼 때도 x,yR를 간단히 xRy와 같이 나타낸다.

동등관계를 나타낼 때 주로 기호 ‘’이나 ‘’를 사용한다. 강한 순서관계를 나타낼 때 주로 ‘<‘나 ‘’를 사용하며, 약한 순서관계를 나타낼 때 주로 ‘’나 ‘’를 사용한다.

부분집합을 나타내는 기호 는 관계가 아니다. 왜냐하면 모든 집합의 집합이 존재하지 않기 때문이다. 그러나 적당한 집합 X를 고정시키면 는 거듭제곱집합 P(X) 위에서 정의된 관계이다.