対応 (数学)
数学における対応（たいおう、Correspondence）とは、ある集合の各元に別な集合の部分集合を割り当てるものである。
定義
集合 A から B への（部分）対応とは、直積集合 A × B の部分集合 G が与えられたとき、三つ組 f = (A, B; G) のことをいう。このとき、
- <math>f\colon A\to B,\quad A \stackrel{f}{{}\to{}}B</math>
などと表す。A, B, G はそれぞれ対応 f の始域 (initial set, source)、終域 (terminal set, target)、グラフ (graph) と呼ばれる。グラフの各成分への射影
- <math> D(f) = \mathrm{dom}(f) := {\rm pr}_l(G) =
\{a\in A \mid \exists b\in B\mbox{ such that } (a,b)\in G\}
</math> は f の定義域 (domain) といい、
- <math> V(f) = \mathrm{ran}(f) := {\rm pr}_r(G) =
\{b\in B \mid \exists a\in A\mbox{ such that } (a,b)\in G\}
</math> を f の像 (image) または値域 (range) と呼ぶ。D(f) = A であるとき、f は（左）全域的対応あるいは単に対応であるといい、V(f) = B であるとき f は全射あるいは右全域的対応という。左全域的かつ右全域的であるときに限って対応と呼ぶこともある。
対応 f: A → B が与えられたとき、dom(f) の元 a に対して、B の部分集合（空集合であってもよい）
- <math>f(a) := \{b\in B\mid (a,b)\in G\}</math>
は、対応 f による a の像 (image) または値 (value) と呼ばれる。このとき、
- <math>G(f) = \{(a,b) \mid a\in A,\,b\in f(a)\}</math>
は f のグラフ G に一致する。
対応と関係
対応 f: A → B が与えられているとき、A の元 a と B の元 b に対して a Rf b ⇔ (a, b) ∈ G(f) と置いて得られる Rf は二項関係である。逆に二項関係 R ⊂ A × B が与えられたとき、a ∈ A に対して、f(a) = {b | a R b} を割り当てる対応 fR: A → B が定まる。
直積の部分集合をグラフとして定まるという意味では、対応は二項関係と同じ概念を表すものと考えることができるが、対応というときはある集合から別な集合へ元を写すというニュアンスが強い。例えば、対応 f: A → A に対して、a ∈ f(a) となるような A の元 a を対応 f の不動点という。
対応によって、一つの元に（部分集合に属する）複数の元が割り当てられているとみなすと、多価函数に近いものと考えることもできるが、対応による像の濃度は元ごとに異なっていてもよいという点で多価函数とは異なる。
対応の相等
二つの対応 f: A → B と g: C → D が等しいとは、順序三つ組としての相当をいう。これは、始域、終域を共有し、始域の各元の像が常に等しいこと、すなわち、集合として A = C, B = D であって、なおかつどんな a ∈ A (= C) に対しても、f(a) = g(a) を満たすとき、対応 f と g は等しいといい、f = g と記す。
なお、終域を重視しない立場もあり、その場合はグラフの相等 G(f) = G(g) を以って対応の相当 f = g と定める。f = g となるための必要十分条件は dom(f) = dom(g) かつ a ∈ dom(f) ならば f(a) = g(a) を満たすことであり、また、(dom(f), ran(f), G(f)) と (dom(g), ran(g), G(g)) が順序三つ組として相等であることである。
逆対応
対応 f: A → B が与えられているとき、
- <math>G(g) = \{(b,a) \in B \times A \mid (a,b) \in G(f)\}</math>
をグラフとする対応 g: B → A を f の逆対応と呼び、f−1 で表す。
写像
対応 f = (A, B, Gf) は、
- 定義域の各元 a ∈ A に対して (a, b) ∈ Gf となるような b ∈ B が一つしかない（すなわち、A のどの元 a についても f(a) がただ一つの元からなる）
という条件（一意対応）をみたすとき、 写像という。対応 f が写像であるとき、f(a) = {b} となることを f(a) = b と略記して、この元 b = f(a) を a の像と呼ぶ。
