1

Chartrand, 3rd Ed, P224-225: Define a relation $R$ as a relation from A to B.

$R$ is well-defined means: $(a,b), (a,c) \in R \implies b = c$.

P220: A function $f: A \to B$ is one-to-one means:
For all $x, y \in A$, if $f(x) = f(y)$, then $x = y$.

I've observed that in the proofs of some functions, one can prove injectivity merely by reversing all the steps in the proof of the definition of well-defined.

$1.$ Is this always admissible and convenient? If not, when and why not?

$2.$ Is the converse true? Could one equally have started with proving the definition of well-defined and then reversed every step to prove injectivity?

Community
  • 1

2 Answers2

2

Let's represent function $f:A\to B$ as a set of ordered pairs $f=\{(a_1,b_1), (a_2,b_2)\ldots\}$.

If this is a one-to-one function, then:

  1. If $(a,b)\in f$ and $(c,b)\in f$, then $a=c$.

  2. For all $a\in A$, there is exactly one $b\in B$ such that $(a,b)\in f$.

You have correctly noticed that if we reverse all the ordered pairs, then condition (1) corresponds to well-defined. However we have this extra condition (2), which distinguishes the two definitions.

vadim123
  • 82,796
0

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\notag \\ #1 \quad & \quad \text{"#2"} \notag \\ \quad & } \newcommand{\endcalc}{\notag \end{align}} $Yes, for functions these two concepts are duals of each other. Here is a proof.

Using the definitions you provided, we can calculate as follows, for any function $\;f : A \to B\;$ (leaving implicit that $\;x,y \in A\;$ and $\;p,q \in B\;$):

$$\calc f\text{ is one-to-one} \calcop{\equiv}{definition of one-to-one} \langle \forall x,y : f(x) = f(y) : x = y \rangle \calcop{\equiv}{logic: one-point rule, twice -- to prepare for the next step} \langle \forall x,y,p,q : p=f(x) \;\land\; q=f(y) \;\land\; p = q : x = y \rangle \calcop{\equiv}{definition of function application, twice} \langle \forall x,y,p,q : (x,p) \in f \;\land\; (y,q) \in f \;\land\; p = q : x = y \rangle \calcop{\equiv}{logic: simplify using one-point rule for $\;\forall q\;$} \langle \forall x,y,p : (x,p) \in f \;\land\; (y,p) \in f : x = y \rangle \calcop{\equiv}{definition of $\;\cdot^{-1}\;$ -- to prepare for the next step} \langle \forall x,y,p : (p,x) \in f^{-1} \;\land\; (p,y) \in f^{-1} : x = y \rangle \calcop{\equiv}{definition of well-defined} f^{-1}\text{ is well-defined} \endcalc$$

MarnixKlooster ReinstateMonica
  • 5,576