Equivalence between elements of different sets - how to formally define the "equivalence classes"?

Question

What would be a good formal definition for the set $\mathcal T$ constructed below? I will try and give a simple example.

Consider the set $[\;n\;]=\{1,2,\ldots,n\}$, as well the family $\mathcal{C}$ of all subsets of cardinality 3 of $[\;n\;]$: $$\mathcal{C}=\{\{1,2,3\}, \{1,2,4\}, \ldots, \{n-2,n-1,n\}\}.$$ Obviously, every set $C \in \mathcal{C}$ has the same structure - it consists of three elements, $C=\{c^{C}_{1},c^{C}_{2},c^{C}_{3}\}$ with $c^{C}_{1}<c^{C}_{2}<c^{C}_{3}$ - or in other words, every set $C \in \mathcal{C}$ has a smallest, a second-smallest and a largest element.

I would now like to define a set $\mathcal{T}=\{t_{1},t_{2},t_{3}\}$ which generalizes the sets $C\in \mathcal{C}$ in the following sense: $t_{1}$ is a symbol representing the smallest element of a three-element set, $t_{2}$ represents the second-smallest element, and $t_{3}$ represents the largest element. (The intention is to view $\mathcal{T}$ as a poset and use its properties to draw conclusions about $\mathcal{C}$, but that is irrelevant for the current question.)

One possible way of defining $\mathcal{T}$ might be to construct its elements as equivalence classes in the following way:

---

Definition Ver. 1: Consider a multiset $$D=\bigcup_{C\in\mathcal{C}}\bigcup_{j=1}^{3}\left\{ c_{j}^{C}\right\}$$ and the following equivalence relation $\sim$ defined on $D$: $$c_{j_{1}}^{C_{1}}\sim c_{j_{2}}^{C_{2}}\Longleftrightarrow j_{1}=j_{2}.$$ We define the set $\mathcal{T}$ as $\mathcal{T}=D/\sim$ and its elements as the equivalence classes $t_{j}=\left[c_{j}^{C}\right]$.

---

What I like about this version is the idea of defining each $t_{j}$ as an equivalence class, which gets rid of this weird "$t_{j}$ is a symbol representing the $j^\text{th}$-smallest element of a set" formulation. On the other hand - and this is my biggest issue here - is this equivalence relation well-defined? The statement $j_{1}=j_{2}$ makes sense while we're talking about the variables $c_{j_{1}}^{C_{1}}$ and $c_{j_{2}}^{C_{2}}$; but I'm somewhat inclined towards looking at them as their values, i.e. the actual elements of the set $[\;n\;]$, at which point they lose their information about which index $j$ and subset $C$ they are associated with... Which interpretation is the correct one here?

Here's an alternative version for this definition:

---

Definition Ver. 2: Consider the set $$\mathcal{T} = \bigcup_{j=1}^{3}\left\{ t_{j}\right\}.$$ For a given set $C \in \mathcal{C}$, identify every element $c^{C}_{j}$ of $C$ with the element $t_{j}$ of $\mathcal{T}$ via the isomorphism $\tau_{C}:\mathcal{T}\rightarrow C$, $\tau_{C}:t_{j}\mapsto c^{C}_{j}.$

---

Using isomorphisms kind of makes more sense to me. On the other hand, now I'm stuck with my elements $t_{j}$ of $\mathcal{T}$ just being symbols without any further meaning to begin with. Furthermore, it seems like a strange construction to identify elements $t_{j}$ and $c^{C}_{j}$ by matching their indices $j$ - is it even clear when writing it like this? And is it legitimate to define $\mathcal{T}$ and $\tau_{C}$ together in one breath like that? (I could separate the definitions, but that makes the introduction of the object $\mathcal{T}$ even less understandable...)

Any help to clarify this will be greatly appreciated!

Answer 1

I find your proposed definitions a bit difficult to parse. I think, however, that the following may be close to what you're looking for:

We start by strengthening your initial observation, that each of the elements of $\mathcal{C}$ (thought of as linear orders) are "the same." In fact, they're all the same in a unique way. Precisely, for any two three-element linear orderings $L_1,L_2$ there is a unique isomorphism $L_1\cong L_2$. This uniqueness is crucial: it lets us unambiguously talk about "$L_1$'s version of $x$" when $x$ is in $L_2$.

Thinking in terms of the "$L_1$'s version of $x$"-language, and generalizing to arbitrary structures since we don't really need to talk about linear orderings specifically (for your specific example, see below), this sets up the following idea. Suppose we have a set $\mathcal{X}$ of structures such that for any $A,B\in\mathcal{X}$ there is a unique isomorphism $A\cong B$. Let $$\mathfrak{X}=\{\langle A,a\rangle: A\in \mathcal{X}, a\in A\}$$ be the set of "labelled elements" of elements of $\mathcal{X}$. We get an equivalence relation $\sim$ on $\mathfrak{X}$ given by $$\langle A,a\rangle\sim \langle B,b\rangle\iff f_{A,B}(a)=b$$ where $f_{A,B}$ is the unique isomorphism $A\cong B$. We can then naturally view $\mathfrak{X}/\sim$ as a structure of the same type as the elements of $\mathcal{X}$ - and in fact we'll have $\mathfrak{X}/\sim$ be uniquely isomorphic to each element of $\mathcal{X}$ as expected.

---

In your specific example, here's what the above approach amounts to:

• $\mathfrak{X}$ has $3\cdot{n\choose 3}$ elements, including $\langle\{1,2,3\}, 2\rangle$ and $\langle \{2,3,4\},2\rangle$.

• The equivalence relation $\sim$ identifies $\langle A,a\rangle$ and $\langle B,b\rangle$ when $a$ occupies the same "place" in $A$ that $b$ does in $B$. So for example we have $$\langle \{1,2,3\},2\rangle\sim \langle \{1,2,4\},2\rangle$$ but $$\langle \{1,2,3\},2\rangle\not\sim \langle \{2,3,4\},2\rangle$$ (in the latter case, "$2$" is the second element of $\{1,2,3\}$ but the first element of $\{2,3,4\}$: the unique isomorphism between those two three-element linear orders sends $1$ to $2$, $2$ to $3$, and $3$ to $4$).

• There are, as desired, exactly three $\sim$-classes of elements of $\mathfrak{X}$. So $\mathfrak{X}/\sim$ is a set with three elements, each of which is itself a set of $n\choose 3$ elements, each of which is itself an ordered pair, the first coordinate of which is a three element subset of $[n]$ and the second coordinate of which is an element of that subset. Whew!

• The set $\mathfrak{X}/\sim$ can be turned into a linear order in a natural way: we set $$[\langle A,a\rangle]_\sim \le [\langle B,b\rangle]_\sim$$ iff we have $f_{A,B}(a)\le_Bb$, where

  • $f_{A,B}$ is the unique isomorphism from $A$ to $B$, and

  • "$\le_B$" means "$\le$ in the sense of $B$" (which here is really just "$\le$," I'm using the more complicated notation to emphasize that we could be playing with very different $A$s and $B$s but things would still work).

  Of course we need to show that this $(i)$ is well-defined and $(ii)$ actually satisfies the linear order axioms, but this isn't hard.

---

Let me end by saying a bit about the importance of the uniqueness which I mentioned in the second paragraph and used crucially in defining $\sim$.

Suppose I have two structures $A$ and $B$ which are isomorphic but not uniquely isomorphic. For example, maybe $A$ is the linear ordering consisting of the rationals and $B$ is the linear ordering consisting of the dyadic rationals. It turns out that these are isomorphic, although that's not at all obvious. Now my question is:

What's $B$'s version of $1\over 3$?

The point is that there are lots of ways to define an isomorphism between $A$ and $B$. In fact, there are as many as possible in a precise sense: a countable dense linear order is homogeneous. This prevents us from translating from one structure to the other in an unambiguous way.

We may still have some clever way of choosing a particular isomorphism between two structures according to some other special criteria, but if there are multiple isomorphisms to choose from this will probably be difficult. So if you have a huge collection $\mathcal{X}$ of non-uniquely-isomorphic structures, your best bet is probably to just pick a specific element of $\mathcal{X}$ to work with rather than try to whip up an "unbiased" version.