请输入您要查询的字词:

 

单词 PropertiesOfBijections
释义

properties of bijections


Let A,B,C,D be sets. We write AB when there is a bijection from A to B. Below are some properties of bijections.

  1. 1.

    AA. The identity functionMathworldPlanetmath is the bijection from A to A.

  2. 2.

    If AB, then BA. If f:AB is a bijection, then its inverse functionMathworldPlanetmath f-1:BA is also a bijection.

  3. 3.

    If AB, BC, then AC. If f:AB and g:BC are bijections, so is the compositionMathworldPlanetmathPlanetmath gf:AC.

  4. 4.

    If AB, CD, and AC=BD=, then ABCD.

    Proof.

    If f:AB and g:CD are bijections, so is h:ACBD, defined by

    h(x)={f(x) if xA,g(x) if xC.

    Since AC=, h is a well-defined function. h is onto since both f and g are. Since f,g are one-to-one, and BD=, h is also one-to-one.∎

  5. 5.

    If AB, CD, then A×CB×D. If f:AB and g:CD are bijections, so is h:A×CB×D, given by h(x,y)=(f(x),g(y)).

  6. 6.

    A×BB×A. The function f:A×BB×A given by f(x,y)=(y,x) is a bijection.

  7. 7.

    If AB and CD, then ACBD.

    Proof.

    Suppose ϕ:AB and σ:CD are bijections. Define F:ACBD as follows: for any function f:AC, let F(f)=σfϕ-1:BD. F is a well-defined function. It is one-to-one because σ and ϕ are bijections (hence are cancellable). For any g:BD, it is easy to see that F(σ-1gϕ)=g, so that F is onto. Therefore F is a bijection from AC to BD.∎

  8. 8.

    Continuing from property 8, using the bijection F, we have Mono(A,B)Mono(C,D), Epi(A,B)Epi(C,D), and Iso(A,B)Iso(C,D), where Mono(A,B), Epi(A,B), and Iso(A,B) are the sets of injections, surjectionsMathworldPlanetmath, and bijections from A to B.

  9. 9.

    P(A)2A, where P(A) is the powerset of A, and 2A is the set of all functions from A to 2={0,1}.

    Proof.

    For every BA, define φB:A2 by

    φB(x)={1 if xB,0 otherwise.

    Then φ:P(A)2A, defined by φ(B)=φB is a well-defined function. It is one-to-one: if φB=φC for B,CA, then xB iff xC, so B=C. It is onto: suppose f:A2, then by setting B={xAf(x)=1}, we see that φB=f. As a result, φ is a bijection.∎

Remark. As a result of property 9, we sometimes denote 2A the powerset of A.

随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 19:06:23