단사·전사·전단사(Injection, surjection, bijection)

이 개념 위에 세워진 것

이 개념을 언급하는 페이지

• 함수

  … 가면 단사, 출력 쪽 집합의 원소가 하나도 빠짐없이 어떤 입력의 짝이 되면 전사라 하고, 둘 다이면전단사입니다. 출력에서 입력으로 거꾸로 가는 함수(역함수)는 전단사일 때만 있습니다. 예를 들어 실수 전체에서 …

• 연쇄법칙

  … 의 미분이 g'(x)e^{g(x)} 인 것(지수함수)도 연쇄법칙입니다. 로그의 미분도 eˣ의역함수라는 점에서 구합니다. e^{\ln x} = x 의 양변을 미분하면 e^{\ln x}\cdot(\ln …

• 자연로그

  자연로그에는 얼굴이 둘 있습니다. 하나는 eˣ의역함수입니다. e^{y} = x 인 y가 \ln x 이고, 그래프는 eˣ를 직선 y = x 에 비춘 모양입니다. …

• 연립일차방정식과 역행렬

  … b가 그 직선 위에 없으면 해가 없고, 있으면 해가 무한히 많습니다. 행렬식이 0이 아니면 변환은전단사, 곧 평면의 점들을 빠짐없이 하나씩 짝지어 보냅니다. 그러니 거꾸로 되돌리는 변환이 있고, 그 행렬이 …

• 집합의 크기

  유한집합의 크기는 세면 됩니다. 그런데 "센다"는 건 사실 1, 2, 3, …과짝짓기를 하는 일입니다. 무한집합에는 끝까지 셀 수 없으니 짝짓기만 남습니다. 짝이 딱 맞으면 크기가 같다 고 …

• 비둘기집 원리

  … 칸은 두 마리 이상이 들어간 칸입니다. 함수의 말로 하면, 큰 유한집합에서 작은 유한집합으로 가는 함수는단사가 될 수 없습니다. 이 한 줄로 여러 사실이 나옵니다. 2월 29일까지 생일은 366가지이니, 367명이 …

• 모듈러 연산

  … (노란 테두리)를 따라가 보세요. 지금 어떤 줄은 0부터 n-1 까지를 한 번씩 모두 밟는데(곱하기 a 가전단사), 그런 줄에만 1( 흰 칸)이 나옵니다. 그 칸이 a 의 역수, ax \equiv 1 을 만드는 x …

• 오일러 피 함수와 페르마 소정리

  … 고리로 돌리는 순열입니다. 핵심은 이것입니다. a 가 단원이면 곱하기 a 는 단원들을 단원들로 보내는전단사입니다. 그리고 단원들은 모두 같은 길이 의 고리로 쪼개집니다. 단원 k 에서 출발한 고리가 제자리로 오는 …

• 원시근

  … 원리⟧). a 가 n 과 서로소이면(최대공약수가 1) 곱하기 a 는 되돌릴 수 있는전단사라서, 돌아오는 곳은 언제나 출발점 1입니다. 처음 1로 돌아오기까지의 걸음 수가 a 의 위수 입니다. n …

• 중국인의 나머지 정리

  … 개의 칸에 겹치지 않고 들어가니 칸마다 정확히 하나씩입니다(비둘기집 원리를 거꾸로 쓴 셈이고, 대응은전단사입니다). 답을 직접 만들 수도 있습니다. n 의 배수 중 m 으로 나누면 1이 남는 수와, m 의 배수 …

• 칸토어 함수

  … 이렇게 0과 1 사이의 모든 이진 전개에 닿습니다. 그래서 F 는 칸토어 집합에서 [0, 1] 전체로 가는전사이고, 길이 0인 집합이 길이 1인 구간 전체로 펼쳐집니다. 칸토어 집합이 [0, 1] 보다 작지 않다는 …

• 푸앵카레 원판

  … 이상해 보입니다. 하지만 거리를 잊고 점의 짝짓기만 보면, 경계 원을 뺀 원판(열린 원판)과 평면 사이에는전단사가 있습니다. 예를 들어 원점에서 거리 r인 점을 같은 방향으로 거리 r/(1-r) 인 곳에 보내면, r이 …

• 그래프

  … 같은 그래프로 보고, 동형이라고 부릅니다. 정확히는 한 그래프의 꼭짓점을 다른 그래프의 꼭짓점으로 보내는일대일대응가운데 이어진 두 점을 늘 이어진 두 점으로, 떨어진 두 점을 늘 떨어진 두 점으로 보내는 것이 있을 …

• 오일러 경로

  … 그림의 걷기도 이렇게 찾은 길입니다. 변마다 붙는 번호 1, 2, …, m은 변들과 순서 사이의일대일대응입니다. 비슷해 보이는 '모든 꼭짓점 을 한 번씩 지나는 길'은 해밀턴 경로라고 부릅니다. 1857년 …

• 문맥 자유 문법

  … 값인데, 이 수는 이항계수로 적히고 짝 맞는 괄호열의 개수와도 같습니다. 괄호열과 이진 트리 사이에전단사가 있기 때문입니다. 이진 트리는 '잎이거나, 두 이진 트리의 쌍'이라는 정의, 곧 타입의 등식 T …

• 순열

  … n 입니다. 지금 n! = . 늘어놓기 하나는 n개의 자리에서 n개의 물건으로 가는일대일대응하나이므로, n!은 원소가 n개인 집합에서 자기 자신으로 가는 전단사 함수의 개수이기도 합니다. …

• 카탈랑 수

  … 위의 삼각형이 되고, 그 괄호의 안쪽과 뒤쪽이 각각 삼각형 왼쪽과 오른쪽의 작은 다각형이 됩니다. 이런일대일대응이 있으니 두 세기의 답이 같습니다. 점화식. 비어 있지 않은 짝 맞는 괄호열은 모두 (A)B 꼴로 단 한 …

• 분할수

  … 대해 뒤집으면 가로줄과 세로줄이 바뀌어 또 하나의 분할, 켤레 분할 나옵니다. 뒤집기는 분할들 사이의일대일대응이고 줄의 개수와 가장 긴 줄의 길이를 맞바꾸므로, '부분이 k개 이하인 분할'과 '가장 큰 부분이 k …

• 교란순열

  … 돌려준다고 합시다. 아무도 자기 모자를 받지 못할 확률은 얼마일까요? 돌려주기 하나는 사람에서 모자로 가는일대일대응, 곧 순열입니다. 순열에서 제자리에 그대로 있는 것을 고정점이라 하는데, 고정점이 하나도 없는 …

• 별과 막대

  … 입니다. 별은 사탕, 흰 막대는 아이 사이의 경계입니다. 아래 수는 아이마다 받은 개수입니다. 이 대응은일대일대응입니다. 줄에는 자리가 n+k-1 개 있고, 그중 막대가 설 k-1 자리를 고르면 배치가 하나 정해지며, …

• 트리

  … 그 이웃의 이름을 적기를 n−2번 되풀이하면 길이 n−2인 수열이 나오는데, 이 대응이 트리와 수열 사이의일대일대응입니다. 그림 위의 트리를 이렇게 적은 것이 위의 '프뤼퍼 부호'이고, '새 무작위 트리'는 무작위 수열을 …

• 홀의 정리

  … 됩니다. 서로 겹치지 않는 변들의 모음이 매칭 이고, 모든 사람이 일을 얻는 매칭은 사람에서 일로 가는단사 함수(서로 다른 사람을 서로 다른 일로 보내는 함수)이면서 각자 원하는 일로만 보내는 것입니다. 누구든 사람 …

• 안정 매칭

  … 학생은 학교들에, 학교는 학생들에 좋아하는 순서를 매깁니다. 학생과 학교를 짝짓는 것은 두 무리 사이의일대일대응인데, 어떤 짝짓기는 오래가지 못합니다. 학생 s와 학교 c가 둘 다 지금 짝보다 서로를 더 좋아하면, …

• 위상수학

  … 이렇게 서로 바꿀 수 있는 두 도형을 위상동형 이라 합니다. 정확히는 두 도형 사이에 점을 하나씩 짝짓는전단사f가 있고, f와 그 역함수가 모두 연속이라는 뜻입니다. 찢으면 f가 끊기고, 붙이면 역함수가 …

• 라틴 방진

  … 색이 겹치지 않게 칠한 것과 같습니다(r행 c열의 기호가 변 rc의 색). 모든 짝이 한 번씩이라는 조건은전단사로, 칸과 짝의 개수를 맞추는 셈은 비둘기집 원리로 이어집니다.

• 대수적 자료형

  … 아니지만, 쌍의 순서를 바꾸는 함수가 서로 되돌리는 짝으로 있어서 값들이 빠짐없이 하나씩 짝지어집니다(전단사). 이런 관계를 동형( \cong )이라 합니다. 동형을 같음으로 보면 수의 법칙이 그대로 성립합니다. …

• 범주론

  … A 가 있으면 f를 동형 사상 (isomorphism)이라 하고 A와 B가 동형이라고 합니다. Set에서는전단사 함수, 행렬의 범주에서는 역행렬이 있는 정사각 행렬(행렬식이 0이 아닌 것), 나누어떨어짐의 범주에서는 a …

이 페이지가 가리키는 개념