1
$\begingroup$

The problem, from Boolos and Jeffrey's Computability and Logic, states the following definitions:

  1. "If a function $f(a)$ (from $A$ to $B$) is defined for every element $a$ of $A$, then it is called total"

  2. "A correspondence between sets $A$ and $B$ is a one-to-one, total function from $A$ onto $B$."

  3. "Two sets are said to be equinumerous if and only if there is a correspondence between $A$ and $B$."

Then, it asks the reader to show that if $A$ is equinumerous with $B$, then $B$ is equinumerous with $A$. So far, the work I've done is to show that, for a function $f : A \rightarrow B$, there exists a function $f^{-1} : B \rightarrow A$ that is onto (which follows from $f$ being total), and one-to-one (which follows from $f$ existing). However, it remains to be shown that $f^{-1}$ is total. This seems to require that $f$ is onto, which doesn't seem to be stated by the problem. I would appreciate any hints on how to show that $f^{-1}$ must be total, given the constraints.

  • 0
    @arbin: Look carefully at the penultimate word in condition 2. You notice that it is **onto** and not merely "to"? That's what tells you that $f$ is onto.2012-07-01

1 Answers 1

1

It is common to write that the function is "onto $B$" to mean that it is surjective (onto). Otherwise, we would say that a function $f$ is a [total] function "from $A$ to $B$".

So when it says that it is a total one-to-one, function from $A$ onto $B$ it is telling you (i) the domain is all of $A$; (ii) the function is one-to-one; and (iii) the image is all of $B$.

  • 0
    Thanks. I didn't know that writing it that way was the same as stating simply that it's "onto".2012-07-01