Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://en.wikipedia.org/wiki/Injective_function below:

Injective function - Wikipedia

From Wikipedia, the free encyclopedia

Function that preserves distinctness

In mathematics, an injective function (also known as injection, or one-to-one function^[1] ) is a function f that maps distinct elements of its domain to distinct elements of its codomain; that is, x₁ ≠ x₂ implies f(x₁) ≠ f(x₂) (equivalently by contraposition, f(x₁) = f(x₂) implies x₁ = x₂). In other words, every element of the function's codomain is the image of at most one element of its domain.^[2] The term one-to-one function must not be confused with one-to-one correspondence that refers to bijective functions, which are functions such that each element in the codomain is an image of exactly one element in the domain.

A homomorphism between algebraic structures is a function that is compatible with the operations of the structures. For all common algebraic structures, and, in particular for vector spaces, an injective homomorphism is also called a monomorphism. However, in the more general context of category theory, the definition of a monomorphism differs from that of an injective homomorphism.^[3] This is thus a theorem that they are equivalent for algebraic structures; see Homomorphism § Monomorphism for more details.

A function f {\displaystyle f} that is not injective is sometimes called many-to-one.^[2]

Let f {\displaystyle f} be a function whose domain is a set X . {\displaystyle X.} The function f {\displaystyle f} is said to be injective provided that for all a {\displaystyle a} and b {\displaystyle b} in X , {\displaystyle X,} if f ( a ) = f ( b ) , {\displaystyle f(a)=f(b),} then a = b {\displaystyle a=b} ; that is, f ( a ) = f ( b ) {\displaystyle f(a)=f(b)} implies a = b . {\displaystyle a=b.} Equivalently, if a ≠ b , {\displaystyle a\neq b,} then f ( a ) ≠ f ( b ) {\displaystyle f(a)\neq f(b)} in the contrapositive statement.

Symbolically, ∀ a , b ∈ X , f ( a ) = f ( b ) ⇒ a = b , {\displaystyle \forall a,b\in X,\;\;f(a)=f(b)\Rightarrow a=b,} which is logically equivalent to the contrapositive,^[4] ∀ a , b ∈ X , a ≠ b ⇒ f ( a ) ≠ f ( b ) . {\displaystyle \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b).} An injective function (or, more generally, a monomorphism) is often denoted by using the specialized arrows ↣ or ↪ (for example, f : A ↣ B {\displaystyle f:A\rightarrowtail B} or f : A ↪ B {\displaystyle f:A\hookrightarrow B} ), although some authors specifically reserve ↪ for an inclusion map.^[5]

For visual examples, readers are directed to the gallery section.

• For any set X {\displaystyle X} and any subset S ⊆ X , {\displaystyle S\subseteq X,} the inclusion map S → X {\displaystyle S\to X} (which sends any element s ∈ S {\displaystyle s\in S} to itself) is injective. In particular, the identity function X → X {\displaystyle X\to X} is always injective (and in fact bijective).
• If the domain of a function is the empty set, then the function is the empty function, which is injective.
• If the domain of a function has one element (that is, it is a singleton set), then the function is always injective.
• The function f : R → R {\displaystyle f:\mathbb {R} \to \mathbb {R} } defined by f ( x ) = 2 x + 1 {\displaystyle f(x)=2x+1} is injective.
• The function g : R → R {\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by g ( x ) = x 2 {\displaystyle g(x)=x^{2}} is not injective, because (for example) g ( 1 ) = 1 = g ( − 1 ) . {\displaystyle g(1)=1=g(-1).} However, if g {\displaystyle g} is redefined so that its domain is the non-negative real numbers [0,+∞), then g {\displaystyle g} is injective.
• The exponential function exp : R → R {\displaystyle \exp :\mathbb {R} \to \mathbb {R} } defined by exp ⁡ ( x ) = e x {\displaystyle \exp(x)=e^{x}} is injective (but not surjective, as no real value maps to a negative number).
• The natural logarithm function ln : ( 0 , ∞ ) → R {\displaystyle \ln :(0,\infty )\to \mathbb {R} } defined by x ↦ ln ⁡ x {\displaystyle x\mapsto \ln x} is injective.
• The function g : R → R {\displaystyle g:\mathbb {R} \to \mathbb {R} } defined by g ( x ) = x n − x {\displaystyle g(x)=x^{n}-x} is not injective, since, for example, g ( 0 ) = g ( 1 ) = 0. {\displaystyle g(0)=g(1)=0.}

More generally, when X {\displaystyle X} and Y {\displaystyle Y} are both the real line R , {\displaystyle \mathbb {R} ,} then an injective function f : R → R {\displaystyle f:\mathbb {R} \to \mathbb {R} } is one whose graph is never intersected by any horizontal line more than once. This principle is referred to as the horizontal line test.^[2]

Functions with left inverses are always injections. That is, given f : X → Y , {\displaystyle f:X\to Y,} if there is a function g : Y → X {\displaystyle g:Y\to X} such that for every x ∈ X {\displaystyle x\in X} , g ( f ( x ) ) = x {\displaystyle g(f(x))=x} , then f {\displaystyle f} is injective. The proof is that

f ( a ) = f ( b ) → g ( f ( a ) ) = g ( f ( b ) ) → a = b . {\displaystyle f(a)=f(b)\rightarrow g(f(a))=g(f(b))\rightarrow a=b.}

In this case, g {\displaystyle g} is called a retraction of f . {\displaystyle f.} Conversely, f {\displaystyle f} is called a section of g . {\displaystyle g.}

Conversely, every injection f {\displaystyle f} with a non-empty domain has a left inverse g {\displaystyle g} . It can be defined by choosing an element a {\displaystyle a} in the domain of f {\displaystyle f} and setting g ( y ) {\displaystyle g(y)} to the unique element of the pre-image f − 1 [ y ] {\displaystyle f^{-1}[y]} (if it is non-empty) or to a {\displaystyle a} (otherwise).^[6]

The left inverse g {\displaystyle g} is not necessarily an inverse of f , {\displaystyle f,} because the composition in the other order, f ∘ g , {\displaystyle f\circ g,} may differ from the identity on Y . {\displaystyle Y.} In other words, an injective function can be "reversed" by a left inverse, but is not necessarily invertible, which requires that the function is bijective.

In fact, to turn an injective function f : X → Y {\displaystyle f:X\to Y} into a bijective (hence invertible) function, it suffices to replace its codomain Y {\displaystyle Y} by its actual image J = f ( X ) . {\displaystyle J=f(X).} That is, let g : X → J {\displaystyle g:X\to J} such that g ( x ) = f ( x ) {\displaystyle g(x)=f(x)} for all x ∈ X {\displaystyle x\in X} ; then g {\displaystyle g} is bijective. Indeed, f {\displaystyle f} can be factored as In J , Y ∘ g , {\displaystyle \operatorname {In} _{J,Y}\circ g,} where In J , Y {\displaystyle \operatorname {In} _{J,Y}} is the inclusion function from J {\displaystyle J} into Y . {\displaystyle Y.}

More generally, injective partial functions are called partial bijections.

• If f {\displaystyle f} and g {\displaystyle g} are both injective then f ∘ g {\displaystyle f\circ g} is injective.
• If g ∘ f {\displaystyle g\circ f} is injective, then f {\displaystyle f} is injective (but g {\displaystyle g} need not be).
• f : X → Y {\displaystyle f:X\to Y} is injective if and only if, given any functions g , {\displaystyle g,} h : W → X {\displaystyle h:W\to X} whenever f ∘ g = f ∘ h , {\displaystyle f\circ g=f\circ h,} then g = h . {\displaystyle g=h.} In other words, injective functions are precisely the monomorphisms in the category Set of sets.
• If f : X → Y {\displaystyle f:X\to Y} is injective and A {\displaystyle A} is a subset of X , {\displaystyle X,} then f − 1 ( f ( A ) ) = A . {\displaystyle f^{-1}(f(A))=A.} Thus, A {\displaystyle A} can be recovered from its image f ( A ) . {\displaystyle f(A).}
• If f : X → Y {\displaystyle f:X\to Y} is injective and A {\displaystyle A} and B {\displaystyle B} are both subsets of X , {\displaystyle X,} then f ( A ∩ B ) = f ( A ) ∩ f ( B ) . {\displaystyle f(A\cap B)=f(A)\cap f(B).}
• Every function h : W → Y {\displaystyle h:W\to Y} can be decomposed as h = f ∘ g {\displaystyle h=f\circ g} for a suitable injection f {\displaystyle f} and surjection g . {\displaystyle g.} This decomposition is unique up to isomorphism, and f {\displaystyle f} may be thought of as the inclusion function of the range h ( W ) {\displaystyle h(W)} of h {\displaystyle h} as a subset of the codomain Y {\displaystyle Y} of h . {\displaystyle h.}
• If f : X → Y {\displaystyle f:X\to Y} is an injective function, then Y {\displaystyle Y} has at least as many elements as X , {\displaystyle X,} in the sense of cardinal numbers. In particular, if, in addition, there is an injection from Y {\displaystyle Y} to X , {\displaystyle X,} then X {\displaystyle X} and Y {\displaystyle Y} have the same cardinal number. (This is known as the Cantor–Bernstein–Schroeder theorem.)
• If both X {\displaystyle X} and Y {\displaystyle Y} are finite with the same number of elements, then f : X → Y {\displaystyle f:X\to Y} is injective if and only if f {\displaystyle f} is surjective (in which case f {\displaystyle f} is bijective).
• An injective function which is a homomorphism between two algebraic structures is an embedding.
• Unlike surjectivity, which is a relation between the graph of a function and its codomain, injectivity is a property of the graph of the function alone; that is, whether a function f {\displaystyle f} is injective can be decided by only considering the graph (and not the codomain) of f . {\displaystyle f.}

A proof that a function f {\displaystyle f} is injective depends on how the function is presented and what properties the function holds. For functions that are given by some formula there is a basic idea. We use the definition of injectivity, namely that if f ( x ) = f ( y ) , {\displaystyle f(x)=f(y),} then x = y . {\displaystyle x=y.} ^[7]

Here is an example: f ( x ) = 2 x + 3 {\displaystyle f(x)=2x+3}

Proof: Let f : X → Y . {\displaystyle f:X\to Y.} Suppose f ( x ) = f ( y ) . {\displaystyle f(x)=f(y).} So 2 x + 3 = 2 y + 3 {\displaystyle 2x+3=2y+3} implies 2 x = 2 y , {\displaystyle 2x=2y,} which implies x = y . {\displaystyle x=y.} Therefore, it follows from the definition that f {\displaystyle f} is injective.

There are multiple other methods of proving that a function is injective. For example, in calculus if f {\displaystyle f} is a differentiable function defined on some interval, then it is sufficient to show that the derivative is always positive or always negative on that interval. In linear algebra, if f {\displaystyle f} is a linear transformation it is sufficient to show that the kernel of f {\displaystyle f} contains only the zero vector. If f {\displaystyle f} is a function with finite domain it is sufficient to look through the list of images of each domain element and check that no image occurs twice on the list.

A graphical approach for a real-valued function f {\displaystyle f} of a real variable x {\displaystyle x} is the horizontal line test. If every horizontal line intersects the curve of f ( x ) {\displaystyle f(x)} in at most one point, then f {\displaystyle f} is injective or one-to-one.

• An injective non-surjective function (injection, not a bijection)

• An injective surjective function (bijection)

• A non-injective surjective function (surjection, not a bijection)

• A non-injective non-surjective function (also not a bijection)

• Not an injective function. Here

  X 1 {\displaystyle X_{1}}

  and

  X 2 {\displaystyle X_{2}}

  are subsets of

  X , Y 1 {\displaystyle X,Y_{1}}

  and

  Y 2 {\displaystyle Y_{2}}

  are subsets of

  Y {\displaystyle Y}

  : for two regions where the function is not injective because more than one domain

  element

  can map to a single range element. That is, it is possible for

  more than one x {\displaystyle x}

  in

  X {\displaystyle X}

  to map to the

  same y {\displaystyle y}

  in

  Y . {\displaystyle Y.}

• Making functions injective. The previous function

  f : X → Y {\displaystyle f:X\to Y}

  can be reduced to one or more injective functions (say)

  f : X 1 → Y 1 {\displaystyle f:X_{1}\to Y_{1}}

  and

  f : X 2 → Y 2 , {\displaystyle f:X_{2}\to Y_{2},}

  shown by solid curves (long-dash parts of initial curve are not mapped to anymore). Notice how the rule

  f {\displaystyle f}

  has not changed – only the domain and range.

  X 1 {\displaystyle X_{1}}

  and

  X 2 {\displaystyle X_{2}}

  are subsets of

  X , Y 1 {\displaystyle X,Y_{1}}

  and

  Y 2 {\displaystyle Y_{2}}

  are subsets of

  Y {\displaystyle Y}

  : for two regions where the initial function can be made injective so that one domain element can map to a single range element. That is, only one

  x {\displaystyle x}

  in

  X {\displaystyle X}

  maps to one

  y {\displaystyle y}

  in

  Y . {\displaystyle Y.}

• Injective functions. Diagramatic interpretation in the

  Cartesian plane

  , defined by the

  mapping f : X → Y , {\displaystyle f:X\to Y,}

  where

  y = f ( x ) , {\displaystyle y=f(x),} X = {\displaystyle X=} domain of function

  ,

  Y = {\displaystyle Y=} range of function

  , and

  im ⁡ ( f ) {\displaystyle \operatorname {im} (f)}

  denotes image of

  f . {\displaystyle f.}

  Every one

  x {\displaystyle x}

  in

  X {\displaystyle X}

  maps to exactly one unique

  y {\displaystyle y}

  in

  Y . {\displaystyle Y.}

  The circled parts of the axes represent domain and range sets— in accordance with the standard diagrams above

• Bijection, injection and surjection – Properties of mathematical functions
• Injective metric space – Type of metric space
• Monotonic function – Order-preserving mathematical function
• Univalent function – Mathematical concept

1. ^ Sometimes one-one function, in Indian mathematical education. "Chapter 1:Relations and functions" (PDF). Archived (PDF) from the original on Dec 26, 2023 – via NCERT.
2. ^ ^{a b c} "Injective, Surjective and Bijective". Math is Fun. Retrieved 2019-12-07.
3. ^ "Section 7.3 (00V5): Injective and surjective maps of presheaves". The Stacks project. Retrieved 2019-12-07.
4. ^ Farlow, S. J. "Section 4.2 Injections, Surjections, and Bijections" (PDF). Mathematics & Statistics - University of Maine. Archived from the original (PDF) on Dec 7, 2019. Retrieved 2019-12-06.
5. ^ "What are usual notations for surjective, injective and bijective functions?". Mathematics Stack Exchange. Retrieved 2024-11-24.
6. ^ Unlike the corresponding statement that every surjective function has a right inverse, this does not require the axiom of choice, as the existence of a {\displaystyle a} is implied by the non-emptiness of the domain. However, this statement may fail in less conventional mathematics such as constructive mathematics. In constructive mathematics, the inclusion { 0 , 1 } → R {\displaystyle \{0,1\}\to \mathbb {R} } of the two-element set in the reals cannot have a left inverse, as it would violate indecomposability, by giving a retraction of the real line to the set {0,1}.
7. ^ Williams, Peter (Aug 21, 1996). "Proving Functions One-to-One". Department of Mathematics at CSU San Bernardino Reference Notes Page. Archived from the original on 4 June 2017.

• Bartle, Robert G. (1976), The Elements of Real Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-05464-1, p. 17 ff.
• Halmos, Paul R. (1974), Naive Set Theory, New York: Springer, ISBN 978-0-387-90092-6, p. 38 ff.

Look up

in Wiktionary, the free dictionary.

• Earliest Uses of Some of the Words of Mathematics: entry on Injection, Surjection and Bijection has the history of Injection and related terms.
• Khan Academy – Surjective (onto) and Injective (one-to-one) functions: Introduction to surjective and injective functions

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4