(ZFC)Prove that the two conditions are equivalent:
S/~≤T & T≤S
∃f (f:S↠T & ∀s1∀s2(f(s1)=f(s2)⇒s1~s2)).
My attempt: I start with the first, trying to prove the second.
- S/~ is defined as the union of all equivalent classes of the form [a]/~, such that a ∈ S. Hence S/ is the number of proper classes of S/~, such that ∪([a]/~|a∈ S).
- Since T≤S ⇒∃(f:S↠T) and f is not an injection.
Proof: Let x1 and x2 be two arbitrary elements from S. Since the number of elements of S is bigger than those in T⇒ under some condition f(x1)=f(x2).
But from AC it follows that if S/~ consists of pairwise disjoint non-empty sets, there exists at least one set C, such that it contains exactly one element in common with each of the sets in S/~. Hence ∃(g:S⤖C) and since T≤C.
But from def of proper classes, namely ∀s1∀s2(<s1,s2> ∈ S/~ ⇒ Comp~(s1,s2)⇔f(s1)=f(s2).
Not sure wether it works, so please help me.
In its current format (i.e., without assuming that range of $f$ is $T$), the second bullet point is equivalent to $|S/{\sim}|\le |T|$.
Indeed, if a function $f:S\to T$ satisfies $f(s_1)=f(s_2)\implies s_1\sim s_2$, then, using axiom of choice, choose a representative of every equivalence class by a function $u:S/{\sim}\,\to S$ that satisfies $\pi\circ u={\rm id}$ where $\pi:S\to S/{\sim}$ is the natural map $\pi(s)=[s]_\sim$.
Then the condition on $f$ implies that $f\circ u:S/{\sim}\,\to T$ is injective.
For the other direction, if $g:S/{\sim}\,\to T$ is injective, then the composition $g\circ\pi:S\to T$ satisfies the condition.
If, moreover $f$ in second bullet point is assumed to be surjective, then it also implies $|T|\le |S|$ (by taking any right inverse of $f$, which exists by the axiom of choice).
Finally, assuming injections $g:S/{\sim}\,\to T$ and $h:T\to S$, we can define $f$ so that
$\quad f(s)=t\quad$ if $h(t)=s$ and $t\notin{\rm range}(g)$
$\quad f(s)=g([s]_\sim)\quad$ otherwise,
then its range is $T$ by construction, and verify that it satisfies $f(s_1)=f(s_2)\implies s_1\sim s_2$.