-1
$\begingroup$

As the title says, I struggle to understand why ( Injections,∘ ) is not a group while ( Injections_finite,∘ ) is.

As I understand, there are 4 properties needed for set to be a group.

  • Associativity
  • Closed operation
  • Inverses
  • Identity

Closed operation

For both statements, this is valid. Since these are functions, they are defined on the entire domain.

Identity

The identity function which takes every element to itself is the identity : f(x) -> x

Associativity

It is verifiable as a result of closure.

Inverses

This is what I have issues understanding.

  • For ( Injections,∘ ), the explanation given is: Since the domain can have infinite size, it is not necessary that these functions are invertible.

My question:

  • What does the infinite size of the domain have to do with the absence of inverse for functions that are part of that domain?

  • For ( Injections_infinite,∘ ), the explanation given is: The existence of inverses is the result of the proposition which states that if the domain and co-domain are finite and have the same size, every injective function from one to the other is also a bijection. Since these are bijections, their invertability follows.

My question:

  • Does "injective function from one to the other is also a bijection" mean that functions that are mapped from a finite domain to a finite co-domain are both injective and surjective?
  • Why does their bijection imply invertability?

Thanks for the help in advance!!

$\endgroup$
  • 1
    $\begingroup$ I assume you are talking about functions from a set $S$ to itself? If so, then...yes. If $S$ is finite then injective implies surjective (by the pigeon hole principle). This is clearly false if $S$ is infinite. For a reference (in the finite case) see, e.g., this $\endgroup$ – lulu Dec 23 '16 at 14:40
2
$\begingroup$

Like lulu in the comments, I'm also assuming you're talking about functions that map a set $A$ to itself since otherwise injectivity does not necessarily imply surjectivity if $A$ is finite (take $f : \{1,2\} \to \{1,2,3\}$ defined by $f(x) = x$).

Anyway, your questions:

What does the infinite size of the domain have to do with the absence of inverse for functions that are part of that domain?

I think the best way to answer this is to exhibit an injective function $f : A \to A$ where $A$ is infinite and $f$ is not surjective. Then since $f$ is not surjective, it's not bijective, which means it doesn't have an inverse. Take $A = \Bbb N = \{0,1,2,3, \dots\}$ and take $f : A \to A$ to be $f(x) = x + 1$. Then $f$ is clearly injective, but it is not surjective because there is no $x \in A$ such that $f(x) = 0$.

Does "injective function from one to the other is also a bijection" mean that functions that are mapped from a finite domain to a finite co-domain are both injective and surjective?

No. It means if you have a function $f : A \to A$ that you already know to be injective, and if $A$ is finite, then you can conclude that $f$ is bijective (i.e., $f$ is also surjective). (See the link lulu provided in the comment on your post for details on that.) But it's possible to have a function $g : B \to B$ where $B$ is finite and $g$ is neither surjective nor injective, e.g., take $B = \{1,2,3\}$ and $g(1) = g(2) = g(3) = 1$.

Why does their bijection imply invertability?

Because if $f : A \to A$ is bijective, then (even if $A$ is infinite) for every $b \in A$ there is a unique $a \in A$ such that $f(a) = b.$ Therefore the inverse function $f^{-1}$ is simply the function that sends $b$ "back" to $a$. That is, if $a \in A$ such that $f(a) = b$, then $f^{-1}(b) = a$. And this function is well defined because $f$ is surjective (so we know that $f^{-1}(b)$ actually has a value) and $f$ is injective (so we know that $a$ is the only element in $A$ such that $f^{-1}(b) = a$)

$\endgroup$
  • $\begingroup$ So bijectivity is a requirement for the existance of an inverse? $\endgroup$ – Pete Dec 23 '16 at 15:03
  • $\begingroup$ @Pete, for the existence of an inverse function, yes. But even without bijectivity it's still possible to talk about "inverse elements" for specific values. For example, $f(x) = x^3 - 9x$ is not bijective because it's not injective, but we can still say, for example, $f^{-1}(80) = 5$. But we can't say, for example, $f^{-1}(0)$, because there are three values of $x$ such that $f(x) = 0$. But I think this "inverse element" concept may really be more of a precalculus/college algebra thing since I haven't seen it anywhere but there. $\endgroup$ – tilper Dec 23 '16 at 15:09
0
$\begingroup$

What does the infinite size of the domain have to do with the absence of inverse for functions that are part of that domain?

Because if $S$ is finite and $f:S\to S$ is injective, then it has an inverse. However, if $S$ is not finite, then it may not have an inverse. For example, $f:\mathbb N\to\mathbb N$ defined as $f(n)=2n$ is not invertible.

Does "injective function from one to the other is also a bijection" mean that functions that are mapped from a finite domain to a finite co-domain are both injective and surjective?

No, it only means that functions that are mapped from a finite domain to a finite co-domain of the same cardinality that are injective are also surjective.

Why does their bijection imply invertability?

Because bijection always implies invertibility.

$\endgroup$
  • $\begingroup$ Wouldn't the invert of f(n) = 2_n_ be f^-1(n) = 0.5_x_ $\endgroup$ – Pete Dec 23 '16 at 14:58
  • $\begingroup$ @Pete No, because that function is not a function from $\mathbb N$ to $\mathbb N$ (because $f(3)$ is not an integer) $\endgroup$ – 5xum Dec 23 '16 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.