Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|cite|improve this question
Did you miss the "from $A$ onto $B$"? – Robert Israel Jul 1 '12 at 21:55
@Arturo: I suppose that total means that the domain is the entire $A$ since computability often deals with partial functions, it makes sense to distinguish total functions. – Asaf Karagila Jul 1 '12 at 21:56
@RobertIsrael, does that imply that $f$ is onto? I'm not familiar with the terminology or convention. – arbn Jul 1 '12 at 21:57
@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. – Arturo Magidin Jul 1 '12 at 21:57

1 Answer 1

up vote 1 down vote accepted

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$.

share|cite|improve this answer
Thanks. I didn't know that writing it that way was the same as stating simply that it's "onto". – arbn Jul 1 '12 at 22:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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