单射(injection或injective )又叫入射, 是指映止集合中的每个元素都至多有一个原像的映射。 其定义为:若对于X中的任意两个不同元素x 1 、x 2, x 1 ≠x 2 ,它们的像f(x 1 )≠f(x 2 ),则称f为X到Y的单射。更精确地说,函数f被称为是单射时,对每一值域内的y,存在至多一个定义域内的x使得f(x) = y。
19世纪初,随着重建数学基础运动的发生, 波尔扎诺 (Bolzano)对建立无穷集合理论提出了重要见解。后来, 格奥尔格·康托尔 (cantor)又研究了集合的映射问题, 并在1874年提出了集合的定义。1954年, 法国 数学团体尼古拉·布尔巴基(Nicolas Bourbaki)的《数学原本卷一:集合论》中首次提到了 单射 、 满射 、 双射 的概念,形成了现在使用的数学名词。
单射具有一些基本性质,如若f和g皆为单射的,则f o g亦为单射的。 通过是否满足充要条件可以对单射性进行验证。 在集合范畴中,函数是内射的当且仅当它是一个单射。 此外,该概念在其他领域应用广泛,如 计算机科学 中,一种沿光路逆向迭代的算法,通过建立从元素图像显示面到重建光场的单射映射,达到提高像素的匹配精度的目的。
定义
映射
设 、 是两个非空集合,如果存在一个法则 ,使得对 中每个元素 ,按法则 ,在 中有唯一确定的元素 与之对应,那么称 为从 到 的映射,记作
,
其中 称为元素 (在映射 下)的像,并记作 ,即
,
而元素 称为元素 (在 映射 下)的一个原像。
在映射 中,始集 ( )称为映射 的定义域,记为 或 ;终集 ( )称为映射的陪域,记为 或 ; 称为映射的 值域 ,记为 或 。
单射
如果一个映射的映止集合中的每个元素都至多有一个原像,那么就把这个映射称为单射。 即若对于 中的任意两个不同元素 ,它们的像 ,则称 为 到 的单射。
相关概念
满射
满射也称到上映射,指陪域与 值域 相等 的映射,当 时的映射 。
双射
双射 也称满单射、一一对应、到上的一一映射等,指同时是单射和满射的映射。
三者区别
单射 :对于映射 的值域 中每个像元素 ,都唯一存在自己的原像 。
满射 :集合 中的每个元素 都存在原像 。
双射 :集合 中的每个元素 都唯一存在自己的原像 。
简史
发展背景
关于映射,早在1638年, 伽利略·伽利莱 (Galileo Galilei)就发现, 自然数 和自然数的平方之间有一一对应的关系。 19世纪初,微积分中的许多迫切问题得到解决后,反过来,一场重建 数学基础 的运动出现,促进了集合论的诞生。 后来, 波尔扎诺 (Bolzano)对建立无穷集合理论提出了重要见解。其在《无穷的悖论》中,坚持实无穷集合的存在性,强调两个集合的等价概念(即两集合元素间存在对应),并注意到无穷集合的真子集可以同整个集合等价。但是该著作直到他死后三年,也就是1851年才问世。
1870年, 格奥尔格·康托尔 (cantor)应朋友海涅(Heine)邀请开始研究函数的三角级数表示的唯一性问题。他在1871年至1872年的论文中逐步把三角级数展开的唯一性条件推广到允许例外值成为无穷集的情况,把函数间断点问题的研究过渡到对点集本身的研究,明确提出了点集、点集的导集、导集的导集等由 实数 构成的更复杂的集合。 后来,康托尔又研究了集合的映射问题, 并在1873年12月给 戴德金 (Julius Wilhelm Richard Dedekind)中的信中说,他已成功证明了实数集是不可数的。次年,他在1874年提出了集合的定义。但是,后来人们认识到集合是一个原始的概念,不能用其他概念来定义,而只能加以描述或说明。
词源
单射作为一个名词出现的历史并不是很久,1954年, 法国 数学团体尼古拉·布尔巴基( 法语 :Nicholas Bourbaki)的《数学原本卷一:集合论》中首次提到了 单射 、 满射 、 双射 的概念。在此之前,学术界同概念使用的词是一对一关系、到上、一对一到上,布尔巴基使术语标准化,形成了现在使用的数学名词。
性质
(1)等价命题:映射 是单射的充要条件是: 任意两个不同的元素 ,都使 。
证明 :先证充分性。假设 映射 满足命题 ,求证它是单射。用 反证法 ,设 不是单射,则存在 , 的原像不止一个,可以设 是 的不同的原像,即 。这与 矛盾。因此是单射。
再证必要性。设 映射 是单射,求证它满足命题 。仍然用 反证法 ,设 不成立,则存在 中两个不同的元素 ,使 。令 ,则 是 的两个不同原像,这与单射定义矛盾。所以 成立。
(2)性质(1)的逆否命题:映射 是单射的充要条件是:若 , ,则 。
(3)只有单射才存在逆 映射 。 设 ,若 为单射,则对于 的任意 子集 ,有 。
(4)设 的一个映射, 的一个映射,则合成映射 满足:当 都是单射时, 也是单射。
(5)设 是任意两个集合,若存在从 到 的单射,则称 的基数小于或等于 的基数,记作 (若 是有限集, 表示集合 中所含元素的个数,若 是无限集,用 只表示其基数或势)。
(6)对于 ,定义映射 为:对任意 , 。 称为包含映射或内射。包含映射是单射。
(7) ,当且仅当 为单射时 相等 。
(8) ,当且仅当 为单射时相等。
(9) ,当且仅当 为单射时 相等 。
(10) ,当且仅当 为单射时相等。
举例
正例
例1 : 映射 , 是单射。
证明 :设 且 ,求证 。
因为 ,所以 或 ,又因为真数较大,则 对数 也较大,所以有 或 。总之,无论何时,都有 ,证毕。
根据上面的性质,要证一个映射是单射,只要任取映始集合中的元素 ,或者假设 ,求证 和 的像不等,或者假设 的像 相等 ,求证 。要说明一个映射不是单射,只要列举出映始集中两个不同的元素具有相同的像即可。
例2 :设有函数 , 。显然, 是单射的,因为当 时, 。
反例
例3 : 映射 , 不是单射。
证明 :可取 中的 和 ,它们满足 。这说明 中存在不等的 实数 ,在 下的像 相等 。因此, 不是单射。
例4 :设有函数 , 。 不是单射的,因为 。
推广
范畴论中的单射
态射 在范畴论中扮演着主要的角色。因为范畴论将许多不同数学领域但具有相似特征的具体数学对象和映射抽象为统一的概念是通过态射来实现的。例如一个集合 是一个单点集,从范畴论的角度可以等价地表示为任意一个集合到集合 恰好存在一个映射。
单射 : 是一范畴的单射,如果对该范畴中任何对象 和任意射 蕴涵 。 在集合范畴中,函数是内射的当且仅当它是一个单射。此 定理 说明了单射(内射)函数恰好是集合范畴内的单态射。
证明 :设 是内射的,令 是 的可变元素。如果 ,那么存在一个 使得 ,于是 ,从而 。故 是单射的。
反之,设 是单射的,取常量 且 ,那么 。因为常量对应 的元素,所以有 蕴涵 ,也就是 是内射函数。
子对象 :在许多具体的范畴中经常需要讨论某个对象的"子对象",因此,可以将这一概念抽象为范畴概念,但是在范畴论中与其说是讨论对象之间的"包含关系",不如说来讨论"包含 态射 "的性质。由于不同的具体范畴中对"包含态射"的要求不同,所以不能给出一个统一的条件来刻画所有的"包含态射"。 在范畴 中,对象 的一个子对象是 下的单射的一个等价类。单射是内射,所以子对象是内射的等价类。
应用
密码学
在密码学中,仿射密码是单表 替代密码 的一个特例,是一种线性变换。即仿射密码就是移位密码和乘法密码的结合(更确切地说是二者的线性结合,将移位密码和乘法密码进行 线性组合 就可以得到更多的选择方式获得 密钥 )。仿射密码中会用到乘法,乘数也受到与乘法密码相同的局限。但是,如果所选的仿射函数是一个单射函数,让 与 互质 (与乘法密码类似),即要求仿射密码 ,就能对密文进行解密。
计算机科学
在计算机科学中,对于元素图像生成算法,传统的方法是建立从光场到显示面的映射,这会存在很多冗余映射。针对这一问题,人们提出沿光路逆向迭代的算法,建立从元素图像显示面到重建光场的单射,使元素图像中的每个像素只对应唯一的光场像素,这可以提高像素的匹配精度,消除深度阶跃处的空洞。该方法提出的元素图像的计算生成 速率 是现有算法的8倍以上,图像中的像素总数越大,该算法的速率优势越明显。
日常生活
在日常生活中人们也可以借助单射原理,将复杂的事情变得简单,同时也能了解更多的信息。例如,两个棒球队首次对阵时,人们总会寻找球衣号码为1的人,因为在业余棒球队选手中,球衣号码为1的队员一般都是主力,只要了解主力选手,就能推测出那个棒球队的实力。由于知道球衣号码和选手是一一对应的,通过寻找1号选手可以推测该棒球队的实力。