Functions and Relations - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:21:05Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:21 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[계산 이론 개론#Mathematical Objects\|계산 이론 개론]]		상위 문서: [[계산 이론 개론#Mathematical Objects\|계산 이론 개론]]

Pinkgo: /* More about Binary Relations */

2025-10-08T10:33:16Z

More about Binary Relations

← 이전 판		2025년 10월 8일 (수) 10:33 판
34번째 줄:		34번째 줄:
	* symmetric: <math>\forall a\,\, b. (a, b) \in R \rightarrow (b,a) \in R</math>		* symmetric: <math>\forall a\,\, b. (a, b) \in R \rightarrow (b,a) \in R</math>
	* antisymmetic: <math>\forall a\,\, b. (a, b) \land (b, a) \in R \rightarrow a = b</math>		* antisymmetic: <math>\forall a\,\, b. (a, b) \land (b, a) \in R \rightarrow a = b</math>
	* transitive: <math>\forall a b c. (a, b) \land (b, c) \in R \rightarrow (a, c) \in R</math>		* transitive: <math>\forall a\,\, b\,\, c. (a, b) \land (b, c) \in R \rightarrow (a, c) \in R</math>
	* an equivalance: 이항 관계 R이 reflexive, symmetric, and transitive		* an equivalance: 이항 관계 R이 reflexive, symmetric, and transitive
	* a partial order: 이항 관계 R이 reflexive, antisymmetric, and transitive		* a partial order: 이항 관계 R이 reflexive, antisymmetric, and transitive
	* a total<ref>or linear</ref> order: a partial order R이 <math>\forall a b. (a, b) \in R \lor (b, a) \in R</math>을 추가로 만족. 즉, 모든 원소가 비교 가능하다.		* a total<ref>or linear</ref> order: a partial order R이 <math>\forall a\,\, b. (a, b) \in R \lor (b, a) \in R</math>을 추가로 만족. 즉, 모든 원소가 비교 가능하다.

	==각주==		==각주==

Pinkgo: /* More about Binary Relations */

2025-10-08T10:25:03Z

More about Binary Relations

← 이전 판		2025년 10월 8일 (수) 10:25 판
32번째 줄:		32번째 줄:
	<math>R \subseteq A\times A</math>를 만족하는 이항관계 R에 대해 아래와 같은 정의가 성립한다.		<math>R \subseteq A\times A</math>를 만족하는 이항관계 R에 대해 아래와 같은 정의가 성립한다.
	* reflexive: <math>\forall a. a\in A \rightarrow (a,a) \in R</math>		* reflexive: <math>\forall a. a\in A \rightarrow (a,a) \in R</math>
	* symmetric: <math>\forall a b. (a, b) \in R \rightarrow (b,a) \in R</math>		* symmetric: <math>\forall a\,\, b. (a, b) \in R \rightarrow (b,a) \in R</math>
	* antisymmetic: <math>\forall a b. (a, b) \land (b, a) \in R \rightarrow a = b</math>		* antisymmetic: <math>\forall a\,\, b. (a, b) \land (b, a) \in R \rightarrow a = b</math>
	* transitive: <math>\forall a b c. (a, b) \land (b, c) \in R \rightarrow (a, c) \in R</math>		* transitive: <math>\forall a b c. (a, b) \land (b, c) \in R \rightarrow (a, c) \in R</math>
	* an equivalance: 이항 관계 R이 reflexive, symmetric, and transitive		* an equivalance: 이항 관계 R이 reflexive, symmetric, and transitive

2025년 9월 10일 (수) 04:27에 Pinkgo님의 편집

2025-09-10T04:27:56Z

@@ 10번째 줄: / 10번째 줄: @@
   <math>\forall a \in A \rightarrow \exists ! b \in B \land (a, b) \in F</math>
-==Relations==
+===Special Classes of Functions===
 함수는 아래와 같이 정의된다.
 * 일대일 함수<ref>단사, one-to-one, injective라고도 한다.</ref>: <math>\forall a\, a'\, b.(a,b)\in F \land (a',b)\in F \rightarrow a = a'</math>
@@ 22번째 줄: / 16번째 줄: @@
 * 일대일 대응<ref>one-to-one correspondence, bijective라고도 한다.</ref>:<math>\forall b. b \in B \rightarrow (\exists ! a.(a,b)\in F)</math>
-==Using Functions to Compare Sets==
+===Using Functions to Compare Sets===
 집합의 크기와 함수의 성질은 서로 밀접한 관련을 맺고 있다.
 * 동수성(Equinumerous): 집합 A, B가 같은 크기<ref><math>|A|=|B|</math></ref>라면, 이는 <math>A\rightarrow B</math> 사이에 bijection이 존재
@@ 28번째 줄: / 22번째 줄: @@
 * Cantor–Schröder–Bernstein 정리: |A|<math>\le</math>|B|이고 |A|<math>\ge</math>|B|이면 |A|=|B|
 * 비둘기집 원리(Pigeonhole Principle): |A|<math>\le</math>|B|일 때 B<math>\rightarrow</math>A 사이의 injection은 존재할 수 없다.
 ==각주==

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: 계산 이론 개론 ==개요== 해당 문서에서는 함수(functions), 관계(relations)와 집합 사이의 관계에 대해 설명한다. ==Functions== 함수는 입력을 정의역(domain)에서 받아서 출력을 (codomain)에서 내놓는 블랙박스처럼 동작한다. 이때 중요한 것은 각 입력마다 단 하나의 출력만 존재한다...

2025-09-09T16:46:07Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: 계산 이론 개론 ==개요== 해당 문서에서는 함수(functions), 관계(relations)와 집합 사이의 관계에 대해 설명한다. ==Functions== 함수는 입력을 정의역(domain)에서 받아서 출력을 (codomain)에서 내놓는 블랙박스처럼 동작한다. 이때 중요한 것은 각 입력마다 단 하나의 출력만 존재한다...

새 문서

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[계산 이론 개론#Mathematical Objects|계산 이론 개론]]

==개요==
해당 문서에서는 함수(functions), 관계(relations)와 집합 사이의 관계에 대해 설명한다.

==Functions==
함수는 입력을 정의역(domain)에서 받아서 출력을 (codomain)에서 내놓는 블랙박스처럼 동작한다. 이때 중요한 것은 각 입력마다 단 하나의 출력만 존재한다는 것이다. 함수 F는 집합 A, B에 대해 데카르트 곱 <math>A \times B</math>의 부분집합이다. 이때 모든 <math>a \in A</math>에 대해 단 하나의 <math>b \in B</math>만 대응해야 한다. 따라서 함수의 정의를 집합을 통해서 나타내면 아래와 같다:
<math>\forall a \in A \rightarrow \exists ! b \in B \land (a, b) \in F</math>

==Relations==
이항 관계(Binary relations)란 두 집합 A, B에 대해 이항 관계는 데카르트 곱 <math>A \times B</math>의 부분집합을 의미한다. 이는 예를 들면,
* <math>A = \{1,2,3\}, B = \{4,5\}</math>
* <math>A\times B = \{(1,4),(1,5)(2,4),(2,5),(3,4),(3,5)\}</math>
* <math>R = \{(1,5),(3,5),(2,4)\}</math>

==Special Classes of Functions==
함수는 아래와 같이 정의된다.
* 일대일 함수<ref>단사, one-to-one, injective라고도 한다.</ref>: <math>\forall a\, a'\, b.(a,b)\in F \land (a',b)\in F \rightarrow a = a'</math>
* 전사<ref>onto, surjective라고도 한다.</ref>: <math>\forall b. b \in B \rightarrow (\exists a. (a,b)\in F)</math>
* 일대일 대응<ref>one-to-one correspondence, bijective라고도 한다.</ref>:<math>\forall b. b \in B \rightarrow (\exists ! a.(a,b)\in F)</math>

==Using Functions to Compare Sets==
집합의 크기와 함수의 성질은 서로 밀접한 관련을 맺고 있다.
* 동수성(Equinumerous): 집합 A, B가 같은 크기<ref><math>|A|=|B|</math></ref>라면, 이는 <math>A\rightarrow B</math> 사이에 bijection이 존재
* 카디널리티 비교: |A|<math>\le</math>|B|는 A<math>\rightarrow</math>B 사이에 injection이 존재
* Cantor–Schröder–Bernstein 정리: |A|<math>\le</math>|B|이고 |A|<math>\ge</math>|B|이면 |A|=|B|
* 비둘기집 원리(Pigeonhole Principle): |A|<math>\le</math>|B|일 때 B<math>\rightarrow</math>A 사이의 injection은 존재할 수 없다.

==각주==