If a structure has a definable ordered pairing function, must it have a definable unordered pairing function, and vice versa?

Question

Is there a structure $M$ with a definable ordered pair function, but no definable unordered pair function? Also, is there a structure $M$ with a definable unordered pair function, but no definable ordered pair function?

Answer 1

This is a surprisingly tricky question! The short version is that unordered pairs always yield ordered pairs but not conversely. To keep things precise, given a structure $\mathcal{A}$ say that:

• $\mathcal{A}$ has a pairing function iff there is a formula $\varphi(x,y,z)$ with parameters from $\mathcal{A}$ such that $$\mathcal{A}\models\forall x,y\exists!z\varphi(x,y,z)\wedge \forall x,y,x',y',z(\varphi(x,y,z)\wedge\varphi(x',y',z)\leftrightarrow x=x'\wedge y=y'),$$ and

• $\mathcal{A}$ has an unordered pairing function iff there is a formula $\varphi(x,y,z)$ with parameters from $\mathcal{A}$ satisfying the same condition but with the clause $x=x'\wedge y=y'$ replaced by $(x=x'\wedge y=y')\vee (x=y'\wedge y=x')$.

The first thing to observe is that any of the usual set-theoretic definitions of ordered pairing functions (e.g. Kuratowski) yield the following:

Fact 1: If $\mathcal{M}$ has a definable unordered pairing function, then $\mathcal{M}$ has a definable ordered pairing function.

Proof: If $f:\mathcal{M}^2\rightarrow\mathcal{M}$ is a definable unordered pairing function, consider the new function $$f_{Kur}:(a,b)\mapsto f(f(a,b),f(a,a)).$$ This basically implements the Kuratowski ordered pair. $\quad\Box$

Getting rid of order turns out to be harder. In fact, it's impossible in general!

Fact 3: There is a structure $\mathcal{M}$ which has a definable ordered pairing function but has no definable unordered pairing function.

This was pointed out to me by Fedor Pakhomov at MO, and is a consequence of a quantifier elimination theorem of Mal'tsev.

That said, there are nontrivial "strength criteria" on structures which ensure that pairing functions can always be de-orderd. Most obviously, we have the following:

Fact 3: Suppose $\mathcal{M}$ has a definable linear order (with domain all of $\mathcal{M}$ itself). Then if $\mathcal{M}$ has a definable ordered pairing function, it also has a definable unordered pairing function.

Proof: If $\trianglelefteq$ is a definable linear order on $\mathcal{M}$ and $f$ is a definable ordered pairing function on $\mathcal{M}$, consider the function $$g(a,b)=\begin{cases} f(a,b) & \mbox{ if } a\trianglelefteq b\\ f(b,a) & \mbox{ otherwise.} \end{cases}$$ This has the desired property. $\quad\Box$

More generally, it's enough for $\mathcal{M}$ to have a definable tournament - that is, a definable map $t:\mathcal{M}^2\rightarrow\mathcal{M}$ with $t(a,b)=t(b,a)\in\{a,b\}$ for all $a,b\in\mathcal{M}$. A linear order yields this via "pick the least." Interestingly, even a tournament is overkill: James Hanson observed that there are "base structures" which have no definable ordered pairing function, do have enough power to definably "de-order" an auxiliary ordered pairing function, but don't have a definable tournament. This paragraph constitutes, in my opinion, a respectable Fact 4 on which to end.