Bijection Definition and 99 Threads

In mathematics, a bijection, bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set. There are no unpaired elements. In mathematical terms, a bijective function f: X → Y is a one-to-one (injective) and onto (surjective) mapping of a set X to a set Y. The term one-to-one correspondence must not be confused with one-to-one function (an injective function; see figures).

A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements. For infinite sets, the picture is more complicated, leading to the concept of cardinal number—a way to distinguish the various sizes of infinite sets.
A bijective function from a set to itself is also called a permutation, and the set of all permutations of a set forms the symmetric group.
Bijective functions are essential to many areas of mathematics including the definitions of isomorphism, homeomorphism, diffeomorphism, permutation group, and projective map.

View More On Wikipedia.org
Recent contents Top users
  1. P

    I On a bijective Laplace transform

    Exponential polynomials are linear combinations of terms like ##t^ne^{at}\cos{bt}## and ##t^ne^{at}\sin{bt}##, where ##n## is a nonnegative integer, ##a## is real and ##b>0##. Like the proper rational functions, these are presumably subspaces of ##\mathbb R^{\mathbb R}##. The proof goes like...
  2. entropy1

    I Direction of logical implication in bijectively related sets

    I have a hypothesis of which I wonder if it's sound. Perhaps you guys can advise me: Suppose ##x_n\Rightarrow a_n## (logical implication) for some set X and set A. I think we have to assume a bijection. Then, if ##a_m = False##, ##x_m## should be ##False##, right? So, in case of a bijection...
  3. dirtypurp

    I Is √9x a Bijection from N to R?

    Let f : N −→ R and f(x) = √ 9x The domain is all natural numbers: {0, 1, 2, 3, ...} The codomain is all real numbers. The range i believe is [0, +infinity) I believe that although the above is a function since every input of x provides a output that fits in our codomain. I also believe that...
  4. I

    Prove bijection from (0,1] to (0,1)

    So, I need to prove that ## (0,1] \thicksim (0,1) ##. Which means that I need to come up with some bijection from ##(0,1]## to ##(0,1)##. Now here is the outline of my function. I am going to use identity function for all irrationals. So, any irrational number in ##(0,1]## will be mapped to the...
  5. T

    Is there a simple injection from B to A using tangent function?

    So I don't really have any goods ideas on how to try and solve this. I only know that using tangent function is supposedly a good idea.
  6. S

    Prove that this mapping is a bijection

    How would one tackle this using the definition? (i.e. for some function ff that f(x)=f(y)⟹x=yf(x)=f(y)⟹x=y implies an injection and y=f(x)y=f(x) for all yy in the codomain of ff for a surjection, provided such x∈Dx∈D exist.) One can solve the system of equations for x1x1 and x2x2 and that...
  7. M

    MHB Show that there exists a bijection

    Hey! :o Let $X$ be an infinite set and let $x\in X$. Show that there exists a bijection $f:X\to X\setminus \{x\}$. Use, if needed, the axiom of choice. To show that $f$ is bijective we have to show that it is surjective and injective. The axiom of choice is equivalent to saying that, the...
  8. nomadreid

    I Is the Unit Square Bijective or Only Injective to the Real Line?

    Is the following (or, the following after any minor errors are corrected) a bijection from the unit square S=[0,1]X[0,1] to the line L=[0,1], or only an injection? If only an injection, are the excluded points in L countable? [1] Let L be identified with the set of real numbers r, 0 ≤ r ≤ 1...
  9. S

    Is my Proof Valid for Bijection of Finite Sets?

    <Moderator's note: Moved from a technical forum.> Hi PF, I am learning how to prove things (I have minimal background in math). Would the following proof be considered valid and rigorous? If not any pointers or tips would be much appreciated! Problem: Prove that the notion of number of...
  10. K

    Cartesian Product and Bijection

    Homework Statement Given two sets of Cartesian product S=A1×A2...×An P=(A1×A2...×An-1)×An show that there exists bijection between the two sets. Homework Equations ∀a1,a2:a1∈A1, a2∈A2: A1×A2=(a1,a2) The Attempt at a Solution let f be a function that maps f: P → A1×A2...×An-1 where...
  11. PsychonautQQ

    Fundamental Group Coset to preimage bijection

    Homework Statement Let p: E-->B be a covering map, let p(e_0)=b_0 and let E be path connected. Show that there is a bijection between the collection of right cosets of p*F(E,e_0) in F(B,b_0) (where p* is the homomorphism of fundamental groups induced by p and F(E,e_0),F(B,b_0) are the...
  12. M

    I Sum principle proof: discrete mathematics

    Theorem: Let ##A_1, A_2, ..., A_k## be finite, disjunct sets. Then ##|A_1 \cup A_2 \cup \dots \cup A_k| = |A_1| + |A_2| + \dots + |A_k|## I will give the proof my book provides, I don't understand several parts of it. Proof: We have bijections ##f_i: [n_i] \rightarrow A_i## for ##i \in [k]##...
  13. M

    F bijective <=> f has an inverse

    Homework Statement Proof that: f has an inverse ##\iff## f is a bijection Homework Equations /definitions[/B] A) ##f: X \rightarrow Y## If there is a function ##g: Y \rightarrow X## for which ##f \circ g = f(g(x)) = i_Y## and ##g \circ f = g(f(x)) = i_X##, then ##g## is the inverse...
  14. P

    [Discrete] Prove that |nZ| = |Z| for any postive integer n

    I have been studying discrete mathematics for fun and I am kind of stuck on this bijection problem. 1. Homework Statement I wanted to apologize in advance if i put this homework question in the wrong part of the forums. Discrete Math and much logic math is a computer science type math of...
  15. RJLiberator

    Proving a function is a bijection and isomorphic

    Homework Statement If G is a group and a ∈ G, let π: G--> G be the function defined as π(g) = ag, for all g ∈G. a) Show that π is a bijection b) Show that if π is an isomorphism, then a is the identity element of G. Homework Equations I think to show that pi is a bijection we have to show that...
  16. RJLiberator

    Abstract Algebra: Bijection, Isomorphism, Symmetric Sets

    Homework Statement Suppose X is a set with n elements. Prove that Bij(X) ≅ S_n. Homework Equations S_n = Symmetric set ≅ = isomorphism Definition: Let G and G2 be groups. G and G2 are called Isomorphic if there exists a bijection ϑ:G->G2 such that for all x,y∈G, ϑ(xy) = ϑ(x)ϑ(y) where the...
  17. davidbenari

    How does ifft(fft(x)) form the correct bijection with domain?

    I think my question is more appropriate here than in the computation section. My question is: (In the context of inverse fast-fourier transforms and fast-fourier transforms) Knowing ifft(fft(x)=x might be trivial as it is almost a definition; associating it with a domain ##t## is perfectly...
  18. nomadreid

    Constructive bijection between [0,1] and R?

    It is easy to construct a bijection between the open interval (0,1) and ℝ, and (if one isn't an intuitionist) it is easy to prove that there exists a bijection between [0,1] and ℝ, but is it possible to construct such a bijection between [0,1] and ℝ? Obviously it won't be continuous, but...
  19. Colleen G

    Bijection between (0,1) and [0,1) in R?

    Homework Statement I need to find a bijection between (0,1) and [0,1) in R. It can go in either direction since it is a bijection. Homework Equations I can't think of any equations at all! The Attempt at a Solution Something like f(x) = 1/[(1/x)+1] for x in A...
  20. F

    Prove that 2xmodn is a bijection for all odd n

    1. State whether or not f(x) = 2x mod n is a bijection for all odd n and prove it Homework EquationsThe Attempt at a Solution So I'm pretty sure it is a bijection over testing it for some odd n, and the fact that gcd(2,n) = 1, thus there must exist an inverse for 2x mod n. However, I realize...
  21. P

    Bijection between parameters in integral formula

    Hello, To measure the atomic force with an AFM. One can use the frequency shift of a cantilever. This change of frequency is linked to the atomic force by what we called the Franz J. Giessibl formula in the community. z is the AFM tip-sample distance. frequency(z) is the change of...
  22. trash

    Is it possible to define this bijection?

    I'd like to know if it is possible to define a bijection between the sets [0,1]^{\mathbb{Z}} and [0,1]^{\mathbb{N}}; \mathbb{N}^{\mathbb{N}} and \mathbb{Z}^{\mathbb{Z}}. I tried to define a bijection between [0,1]^\mathbb{N} and [0,1]^\mathbb{Z} as follows: Take the bijection...
  23. P

    Proof of bijection of a function

    Homework Statement Consider a bijection f = (A,B,F) Show that f^(-1) (inverse of f) is a bijection from B to A and that for any element x of A we have f^(-1)(f(x))=x The Attempt at a Solution For this proof can I use contradiction and the say f^(-1) is not a bijection from B to A or...
  24. B

    Gödel's Incompleteness TheoremsWhat is the limit of mathematical knowledge?

    Homework Statement Let K be any set and let F* be the set of all functions with domain K. Prove that card K < card F*.The Attempt at a Solution I am first able to show that card K <= card F*, by creating an invertible function from K into F*. let f: K -> F* be defined so that if k is an...
  25. Z

    Bijection proof (intro analysis)

    I'm wondering whether my solution to this problem is correct, since the answer in the answer sheet says that this is provable, and I think I found a counterexample... Any help is appreciated :) Homework Statement Prove or disprove: ##f:D->K##, where ##D,K != empty##, is a bijection iff there...
  26. D

    Bijection is uniformly continuous

    Let f:N-> Q be a bijection. I want to show that this is uniformly continuous on N. (N is the set of natural numbers, Q the rationals). My first thought was to use induction. Since every point in N is an isolated point, then f is continuous on N. Let N1=[1,a_1], where a_1 is a natural number...
  27. K

    MHB Injection, Surjection, Bijection

    Can anyone explain to me how to do these types of questions? I have the answers but I don't understand it. The function f: N -> N, f(n) = n+1 is (a) Surjection but not an injection (B) Injection but not a surjection (c) A Bijection (d) Neither surjection not injection The answer is B...
  28. A

    Is There a Bijection from A to X if B is a Subset of X?

    This is something I have been wondering about. Let f:A->B be a bijection. If B is a subset of X. Can there still exist a bijection from A to X?
  29. M

    Bijection between AuB and A with A infinite set and B enumerable set.

    1. Homework Statement . Let A and B be disjoint sets, A infinite and B enumerable. Prove that there exists a bijection between AuB and A. 3. The Attempt at a Solution . I have an idea of how to prove this statement, but I got stuck in the middle, so here is what I've done: There are just...
  30. E

    Cardinality proof by indicating a bijection

    Homework Statement Prove that |AB\cupC|=|ABx AC| by demonstrating a bijection between the two sets. Homework Equations Two sets have equivalent cardinality if there is a bijection between them/ The Attempt at a Solution Essentially I can prove that there is a function from...
  31. H

    Conservation of completeness by uniformly continuous bijection

    Homework Statement I want to prove this proposition: Let f: M \rightarrow N be a uniformly continuous bijection between metric spaces. If M is complete, then N is complete.The Attempt at a Solution I have a 'partial' solution, whose legitimacy hinges upon a claim that I am unable to prove...
  32. B

    Thoughts on this Inverse Bijection Proof

    Is this sufficient?
  33. B

    Finding Bijection Proof: X to p(X)

    Homework Statement Let X be a set. Suppose that f is a bijection from p(X) to p(X) such that f(A)\subseteq f(B) iff A\subseteq B for all subsets A,B of X. Show that there is a bijection g from X to X such that for all A\subseteq X one has f(A)=g(A). Homework Equations p(X) is the power...
  34. C

    Dual Space Bijection: Proving Dependence on Basis

    Homework Statement let V be finite -dimentional and T:V->V*(V* is the dual space of V with same dimension as V) ,let ei be the bases of V,e^i be the bases of V*,consider the linear bijection :K:V->V* defined K(ei)=e^i,show that this bijection depends on the original choice of basis. 2. The...
  35. B

    Bijection between sets of functions

    For two sets X and Y let X^Y be the set of functions from Y to X. Prove that there is a bijection between (X x Y)^Z and X^Z x Y^Z. Attempt: I could not get any further from that "there must be a function S with S(f)=g and S(f')=g for any g, f' in X^Z x Y^Z, and where f is in (X x Y)^Z."
  36. G

    Showing f is a Bijection on a Group

    1. The problem statement, all variables and given/known data Let (G,*) be a group, and denote the inverse of an element x by x'. Show that f: G to G defi ned by f(x) = x' is a bijection, by explicitly writing down an inverse. Given x, y in G, what is f(x *y)? Homework Equations...
  37. S

    Do I need a function to show a bijection between intervals?

    Homework Statement I need to prove that [0,1) and (0,1] have the same cardinality. My question is, do I have to define a function from [0,1) → (0,1] in order to show a correspondence or is there another method? Thanks.
  38. T

    Writing down an explicit bijection

    Homework Statement Let X= \{a,b,c\} and Y= \{d,e\}. Write down and explicit bijection N_{|X×Y|} → X×Y The Attempt at a Solution Well I came up with the easiest method, just giving one value to each member of N_{|X×Y|} so I was just wondering whether there is another way of doing it not by...
  39. D

    Prove that g composed of f is a bijection.

    Homework Statement If f:A->B is a bijection and g:B->C is a bijection, show that g\circf is a bijection from A->C.Homework Equations A function is a bijection from A to B when it is both a surjection and an injection from A to B.The Attempt at a Solution Suppose f is a bijection from A to B and...
  40. E

    Help with a bijection proof involving sets

    Homework Statement I was given a pdf document containing questions that require me to prove set rules. However, the third question (the one that starts at the bottom of the first page and runs into the second page) is giving me problems. I might be able to prove it if he wants a proof by...
  41. A

    Showing a bijection between a set of functions and a set of relations

    Homework Statement With X and Y being sets, I need to show that there is a bijection between the set of functions (X->P(Y)) and the set of relations P(X x Y) where P(..) is the power set symbol. Homework Equations P(Y) = {Z | Z subset of Y} The Attempt at a Solution I know a bijection...
  42. B

    Function must be a bijection for its inverse to exist?

    My analysis text defines inverse functions only for bijections. But y = e^{x} is not bijective, so according to my book it's inverse ( ln x ) wouldn't be defined? Am I missing something or is my textbook just plain wrong? I use the text by Bartle and Sherbert. Thanks! BiP
  43. M

    [Cardinality] Prove there is no bijection between two sets

    Homework Statement prove there is no continuous bijection from the unit circle (the boundary; x^2+y^2=1) to R Homework Equations The Attempt at a Solution is this possible to show by cardinality? since if two sets have different cardinality, then there is no bijection between...
  44. Z

    Show that the function f is bijection

    a function f, that maps from the Cartesian Product of the positive integers to the positive integers. where f(x,y) = 2^(x - 1) * (2y - 1). I have to show that this function is both one-to-one and onto. I started trying to prove that it is onto, showing that there exists an n such that...
  45. I

    Math Proof: Uncountable binary sequence and a bijection from R to R-{0}

    Homework Statement Question 1: Prove that the cardinality of R (the set of all real numbers)is the same as the cardinality of R-{0} by constructing a bijective function from R to R-{0} Question 2: Let A be the infinite sequence of binary numbers as follows: A={(a1,a2,a3...)|ai= 0or 1 for...
  46. T

    Bijection between products of countable sets

    Homework Statement Let S1 = {a} be a set consisting of just one element and let S2 = {b, c} be a set consisting of two elements. Show that S1 × Z is bijective to S2 × Z. Homework Equations The Attempt at a Solution So I usually prove bijectivity by showing that two sets are...
  47. V

    Finding the conditions for a particular mapping to be a bijection

    Homework Statement here's the problem: Let A and B be n x n matrix with coefficient in K (any field), let Mn(K) be the set of all n x n matrix with coefficient in K . T is a linear map defined like this T : Mn(K)---> Mn(K) T(Y) = AYB what are the necessary conditions for T to be a...
  48. T

    Proving Bijective Power Sets of A & B | A, B, C

    Let A,B, and C be non-empty sets. A and B are bijective. Prove that the power set of A is bijective to the power set of B. I understand how to prove bijection but can't figure out how to apply this to power sets and can't find any info on this subject.
  49. T

    Bijection proof for set products

    Let A1, A2, T be non-empty sets such that A1 is bijective to A2. Show that A1 × T is bijective to A2 × T So far I've been able to show that for any b where b is an element of A2, there must be some a within A1 such that f(a) = b. I've been able to do the same for proving injectivity...
  50. T

    Bijection of Cartesian products

    How can I prove this: Let A, B, and C be non empty sets. If A is bijective to B, then A x C is bijective to B x C. also if A and B are bijective Power set of A is bijective to Power set of B and finally Fun(A,C) is bijective to Fun(B,C)
Back
Top