Take
A,B⊆N. Let
f:A→B be
witness to A≤mB.
The following algorithm performs an enumeration of
A. Initialize
N and
B to empty collections of integers. Begin enumerating in parallel over both
n∈N and
b∈B. On each
n, add
f(n) to
N; on each
b, add
b to
B. After each
n and each
b, compute
X=N∩B, emit all elements of
X, and optionally
1 subtract
X from both
N and
B
Helps with efficiency of the algorithm but does not affect correctness
The reason this works is due to the following
equivalence:
n∈A⟺f(n)∈B⟺(∃b∈B)(f(n)=b)
This final expression—
f(n)=b—is what we are testing in the algorithm; this
equivalence ensures that the algorithm has correct semantics.