Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Discrete mathematics, continuous mathematics, and probability resit / 1 / c

Table of contents
- i c
  - Solution i
- ii c
  - Solution ii

i

Solution

Suppose

g (y) = g (y^{'})

. Applying

f

and using the right inverse identity gives

y = (f \circ g) (y) = (f \circ g) (y^{'}) = y^{'} .

This is exactly injectivity, so every right inverse is injective.

ii

Solution

For each

y \in Y

, surjectivity makes the fiber of a function

f^{- 1} ({y})

nonempty. Choose one element

x_{y}

of each such fiber of a function and define

g (y) = x_{y}

. Then

f (g (y)) = y

for every

y

, proving $f \circ g = I_{Y}$ . For arbitrary sets, the simultaneous selection invokes the usual axiom of choice; this is the right-inverse characterization of the axiom of choice. For finite

Y

only finitely many choices are needed. If

Y

is empty, the unique empty function gives the same conclusion.

 Ancestors (11)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version