|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
列 / sequence' 자연수의 집합 [math(\mathbb{Z}^+)]' 또는 '주어진 어떤 양의 정수 [math(n)] 보다 작거나 같은 양의 정수의 집합'을 정의역으로 갖는 함수. 쉽게 말하자면, 수를 늘어놓고 그것에 순번을 붙이는 것이다. 늘어놓는 규칙은 있어도 되고 없어도 된다.[1] 단, 난수열은 중등교육과정에서 큰 의미가 없기 때문에 주로 규칙적으로 나열된 수열들을 다룬다. 만약 수열의 정의역이 첫 [math(n)]개의 자연수이면 유한수열이라 하며, ([math(\left<1, 6, 3, 9\right>)], [math(\left<3, 4, 7\right>)] 등), 수열의 정의역이 자연수인 경우 무한수열이라 한다. ([math(\left<1, 2, 3, 4,\ldots\right>)], [math(\left<1, 3, 5, 7,\ldots\right>)] 등).
초등학교 수학에서는 뛰어 세기, 규칙과 대응 등으로 수열을 익히기 위한 첫걸음을 뗀다.
2. 상세
2.1. 정의
열 [math(a)]이란 정의역이
순서수(ordinal number) [math(\alpha\in \bold{ON})]인 함수를 말한다.
[math(a:\alpha\to S)]
일반적으로 함수를 나타내는 기호는 주로 [math(f,g,h)]를 많이 쓰지만, 열의 경우 [math(a,b,c)] 등을 주로 사용한다.[math(a:\alpha\to S)]
정의역이 유한 순서수([math(n)] 이하의 자연수의 집합)이면 유한렬, 가산 무한 순서수(자연수 집합)이면 무한렬이라고 하며, 일반적으로 순서수 [math(\alpha)]가 정의역이면 [math(\alpha-)]열([math(\alpha-)]sequence)라고 한다. 자연수집합 뿐만 아니라, 순서수라면 자신의 원소를 정렬하여 나타낼 수 있기 때문에, 정의역이 비가산 무한 서수일 때도 열이라고 할 수 있다. 이 문서는 물론 정의역이 가산집합일 때(유한렬과 무한렬) 위주로 작성되었다.[2]
문맥에 따라서 공역이 수 체계 문서에 나오는 익숙한 수이면 수열(공역이 정수이면 정수열, 유리수면 유리수열, 실수면 실수열, 복소수면 복소수열, ...), 위상 공간이면 점렬, 함수 공간이면 함수열, 집합족이면 집합렬 등 편한 대로 부를 수 있다. 어차피 형식적으로는 전부 열이다.
실함수에서 다변수 함수가 있듯 열에서도 이중렬, 삼중렬 등을 정의할 수 있다.
[math(n)]개의 순서수 [math(\alpha_{1},\cdots,\alpha_{n})]에 대하여, [math(n)]중 열은 정의역이 [math(\alpha_{1}\times\cdots\times\alpha_{n})]인 함수를 말한다.
[math(a:\alpha_{1}\times\cdots\times\alpha_{n}\to S)]
[math(a:\alpha_{1}\times\cdots\times\alpha_{n}\to S)]
[math(n=2)]이고, [math(\alpha_{1})], [math(\alpha_{2})]가 모두 유한 순서수이면, 함수 [math(A:\alpha_{1}\times\alpha_{2}\to S)]를
행렬이라고 한다. 무슨 말이냐면, [math((i,j)\in\alpha_{1}\times\alpha_{2})]에 대응하는 항을 [math(i)]행 [math(j)]열의 성분으로 적으면 된다.
2.1.1. 일반항
열의 항은 정의역의 특정한 원소에 대응하는 함수값을 의미한다. 열의 일반항은 열의 함수식을 뜻한다. 즉, 정의역의 원소와 그에 대한 함수값의 관계를 식으로 표현한 것이다. 일반적으로 열의 일반항의 독립변수는 [math(x)]대신 [math(n)], [math(m)], [math(k)], [math(i)], [math(j)], [math(l)] 등을 주로 사용한다. 예를 들어서, 무한수열 [math(a:\mathbb{N}\to\mathbb{R})]의 일반항이 [math(a_{n}=2n-1)]로 주어지면 [math(a)]의 3번째 항은 [math(a_{3}=5)]가 된다.2.1.2. 열의 표기
열 [math(a)]는 첨수를 부여해 표기할 수 있다. 문맥상, 항이 [math(a_{1},a_{2},a_{3}\ldots)]으로 주어졌을 때, 이를 나열하여 열 [math(a_{1},a_{2},a_{3},\ldots)]이라고 쓰기도 한다. 혹은 괄호 [math((,))] 또는 [math(\langle, \rangle)]등을 사용하여 [math((a_{1},a_{2},a_{3},\ldots))] 또는 [math(\langle a_1, a_2, \ldots\rangle)]로 나타내기도 한다.수열의 일반항 [math(a_{n})]이 주어지면 [math((a_{n}))], [math(\langle a_{n}\rangle)], [math(\{a_{n}\})] 등으로 나타내기도 하고, 여기에 아랫첨자와 윗첨자를 추가하여 정의역까지 나타내는 표기법도 있다. 예를 들어서 [math((2^{n}-1)_{n=0}^{\infty})]는 일반항이 [math(a_{n}=2^{n}-1)]이고 [math(n=0)]부터 시작하는 무한수열이다.
2.1.3. 부분렬
열 [math(a:\alpha\to S)]에 대하여, [math(\beta\subseteq\alpha)]인 [math(\beta)]에 대하여, 수열 [math(k:\beta\to\alpha)]가 강한 단조증가함수[3]라고 하자. 이때 합성함수 [math(a\circ k:\beta\to S)]를 [math(a)]의 부분렬이라 한다. 부분렬이 나오는 유명한 명제로는 내림 사슬 조건, 볼차노-바이어슈트라스 정리[4] 등이 있다.3. 관련 문서
[1]
규칙 없이 무한히 반복될 경우 해당 수열은
난수열(
亂
數
列, random sequence)이라고 한다.
초월수의 숫자 배열이 대표적이다.
[2]
선택공리를 받아들이면 이론상으로는 모든 집합을 정렬할 수 있으므로 함수와 수열은 사실상 같은 것이 된다. 하지만 해석학에서 하는 수열은 대다수가 정의역이 가산이고, 이산 위상이 주어질 때만 다룬다.
[3]
강한 단조 함수란 함수의 정의역의 대소가 그대로 함수값의 대소로 이어지는 함수를 말한다. 즉, 강한 단조증가 함수라면 [math(x<y)]이면 [math(f(x)<f(y))]가 되며, 강한 단조감소 함수라면 [math(x<y)]이면 [math(f(x)>f(y))]가 된다.
[4]
임의의 유계 실수열에 대해 어떤 수 [math(L)]로 수렴하는 부분 실수열이 존재한다.