How to use recursion to build a 1:1 correspondence.

Question

Let $\gamma$ be a binary relation with $V$ the departure set and $W$ the destination set.
Suppose the following are true:

$\tag 1 x \gamma y \land x \gamma z \text{ then } y = z$ $\tag 2 y \gamma x \land z \gamma x \text{ then } y = z$

By the symmetry of $\text{(1)}$ and $\text{(2)}$, $\gamma^{-1}$ also satisfies these two conditions.

Any relation satisfying both $\text{(1)}$ and $\text{(2)}$ is said to be a $\text{1:1 build}$. Moreover, any pair $(x,y) \in V \times W$ satisfying

$\tag 3 \gamma \cup \{(x,y)\} \text{ is a 1:1 build} $

is said to be a a builder pair for $\gamma$ .

I need help proving the following

Proposition: Let $f: V \to V$ and $g: W \to W$ be any two functions and $v \in V$ and $w \in W$.
Then

$\tag 1 \text{ There exist a 1:1 build } \Gamma \text{ between } V \text{and } W \text{ with } (v,w) \in \Gamma \text{ such that}$ $\quad \quad \quad \quad \quad \quad \text{If } (x,y) \in \Gamma \text{ and } (f(x),g(y)) \text{ is a builder pair for } \Gamma \text{ then } (f(x),g(y)) \in \Gamma$

I tried working this out but I'm not sure which recursion theorem to use. It may also be so simple that recursion isn't even necessary, where the answer uses more general ideas that can handle the specifics given here.

My work:

Intuitively, step by step you apply $f \times g$. If you get a builder pair, you add it to $\Gamma$. If you don't get a builder pair, you stop. If you keep getting builder pairs, you will build a bijective correspondence between two countably infinite sets that is 'closed under a $f \times g$ pass thru' . But that sounds like hand waving.

Answer 1

It sounds like you have a solid idea! Now you need only make it rigorous. I'd start as follows:

Set $(v_0,w_0):=(v,w).$ Given $(v_n,w_n)\in V\times W,$ let $(v_{n+1},w_{n+1}):=\bigl(f(v_n),g(w_n)\bigr).$

From there, you'd want to show that this recursively defines a sequence of elements $(v_n,w_n)\in V\times W,$ which is straightforward. Next, I'd show that if $\bigl\{(v_n,w_n)\mid n\in\omega\bigr\}$ is not a $1:1$ build between $V$ and $W,$ then there is a least $n\in\omega$ such that $(v_{n+1},w_{n+1})$ is not a builder pair for $\bigl\{(v_k,w_k)\mid k\in\omega,k\le n\bigr\},$ at which point, you've got the finite $1:1$ build case.