I'm trying to formalize the concept os equivalence between optimization problems. Here are the definitions I'm working with:
1) An optimization problem is a pair $(S,f)$ where $S$ is a set and $f\colon S\to\overline{\mathbb{R}}$ is a function.
2) Let $P=(X,f)$ and $Q=(Y,g)$ be optimization problems. A function $\varphi\colon X\to Y$ is a homomorphism from $P$ to $Q$ if$$g(\varphi(x))\leq f(x) \text{, for each }x\in X. $$
3) Let $P$ and $Q$ both be optimization problems. We say that $P$ and $Q$ are equivalent if there exists a homomorphism from $P$ to $Q$ and vice-versa.
One can easily check that this definition of equivalence satisfies all the requirements from an equivalence relation (reflexivity,transitivity, and symmetry). However, since an equivalence relation is defined within a set, I would need to have the set of all optimization problems for it to work, and this is impossible (leading to Russel's Paradox).
Does anyone know how could I fix this? Does my broken equivalence relation still have a name at least?
Scott invented Scott's trick to deal with exactly this sort of difficulty. This even avoids using the axiom of choice. With a strong version of the axiom of choice (so-called global choice), there's a simpler solution. The basic idea with either approach is to chose a representative element from each equivalence class.
Let's work in ZF. (As noted in the comments, if your formal set theory includes proper classes, then equivalence classes are acceptable objects.) So suppose we have a formula $\eta(x,y)$ with exactly two free variables defining the equivalence relation. In ZF, we define the representative element of $x$'s equivalence class to be the set of all elements $y$ of minimal rank that are equivalent to $x$. Formally, and letting $\rho$ stand for the rank functional (see below): $$[x]=\{y:\eta(x,y)\,\&\,\forall z[\eta(x,z)\rightarrow\rho(y)\leq\rho(z)]\}$$ This is a set because it's a subset of $V_\alpha$, where $\alpha$ is the common rank of all the elements of $[x]$. This is Scott's trick: when a naive definition gives you a proper class, replace it with the set of elements of minimal rank in that class.
The rank functional comes from the definition of the von Neumann cumulative hierarchy; this also defines the $V_\alpha$'s.
Global choice asserts that there is a well-ordering of the entire universe; if this is assumed, then you can let the representative of the equivalence class of $x$ be the earliest set that is equivalent to $x$.