Unordered $n$-tuples can't define unordered $(n+1)$-tuples

Question

Suppose we are working in the model theory of ZFC set theory. For every positive integer $n$, I define an $n$-ary function $f_n$, such that $f_n(x_1,...,x_n) = \{x_1,...,x_n\}$. Certainly, given two such functions $f_n$ and $f_m$, if $m < n$, then $f_n$ can define $f_m$. For example, unordered pairs can be used to define singletons, like so: $f_2(x,x)=f_1(x)$.

My question is, given two functions $f_m$ and $f_n$, if $m < n$, then is it the case that $f_m$ can't define $f_n$?

I conjecture that it is not definable. Note, I do not allow the membership symbol to be used to define it, it must be a first order with equality formula in terms of $f_m$.

Answer 1

Assume $\mathrm{Con}(\mathsf{ZFC})$, since if $\mathsf{ZFC}$ is inconsistent, then vacuously $f_m$ is definable from $f_n$.

Let $(M,\in)$ be a model of $\mathsf{ZFC}$. For simplicity, let's assume $M$ is (externally) well-founded (but we can get around this assumption, see below).

Let $0<m<n$, and consider the reduct $(M,f_m)$. I claim that there is an automorphism of $(M,f_m)$ that does not preserve $f_n$. It follows from this that $f_n$ is not definable from $f_m$ (not in the model $M$, and hence not uniformly in ZFC).

Define $R = \mathrm{ran}(f_m)\subseteq M$, and note that $R$ is the class of all sets $x\in M$ such that $1\leq |x|^M \leq m$. Define $A = M\setminus \mathrm{ran}(f_m)$.

I will show that any permutation of $A$ extends to an automorphism of $(M,f_m)$. So fix a permutation $\sigma\colon A\to A$. We define $\tau\colon M\to M$ recursively as follows: $$\tau(x) = \begin{cases} \sigma(x) & \text{if }x\in A\\ \{\tau(y_1),\dots,\tau(y_k)\} &\text{if }x = \{y_1,\dots,y_k\}\in R \end{cases}$$ Note that the recursion makes sense because $M$ is externally well-founded. If $M$ is not well-founded, we can instead prove internally, for any fixed definable permutation $\sigma$, that the definable function obtained by applying the internal recursion theorem as above is an automorphism. Thanks to Noah Schweber for clarifying this point in the comments.

We need to check that $\tau$ is an automorphism.

• For all $y_1,\dots,y_m\in M$, $$\tau(f_m(y_1,\dots,y_m)) = \tau(\{y_1,\dots,y_m\}) = \{\tau(y_1),\dots,\tau(y_m)\} = f_m(\tau(y_1),\dots,\tau(y_m)).$$
• $\tau$ is injective. If $x\in A$ and $y\in R$, then $\tau(x) = \sigma(x)\in A$ and $\tau(y)\in R$ (since $1\leq |\tau(y)|^M\leq m$), so we cannot have $\tau(x) = \tau(y)$. Now suppose $\tau(x) = \tau(y)$. If $x,y\in A$, then $\sigma(x) = \sigma(y)$, so $x = y$ since $\sigma$ is injective. We show by $\in^M$-induction that if $x,y\in R$, then $\tau(x) = \tau(y)$ implies $x = y$. Writing $x = \{x_1,\dots,x_k\}$ and $y = \{y_1,\dots,y_\ell\}$, we have $\{\tau(x_1),\dots,\tau(x_k)\} = \{\tau(y_1),\dots,\tau(y_\ell)\}$. For any $x_i\in x$, there is some $y_j\in y$ such that $\tau(x_i) = \tau(y_j)$. By induction, this implies $x_i = y_j$, so $x\subseteq y$. Similarly, $y\subseteq x$, so $x = y$.
• $\tau$ is surjective. If $x\in A$, then $\tau(\sigma^{-1}(x)) = \sigma(\sigma^{-1}(x)) = x$. We show by $\in^M$-induction that if $x\in R$, then there is $y$ such that $\tau(y) = x$. Writing $x = \{x_1,\dots,x_k\}$, by induction there exist $y_1,\dots,y_k$ such that $\tau(y_i) = x_i$, so $\tau(\{y_1,\dots,y_k\}) = \{\tau(y_1),\dots,\tau(y_k)\} = x$.

Now let $x_1,\dots,x_n$ be $n$ distinct elements of $A$, and let $y = \{x_1,\dots,x_n\}$, so $y = f_n(x_1,\dots,x_n)$. Note that $|y|^M = n > m$, so $y\in A$. Let $z$ be an element of $A\setminus \{x_1,\dots,x_n,y\}$. Let $\sigma$ be the permutation of $A$ swapping $y$ and $z$ and leaving all other elements fixed [in the non-well-founded case, note that this $\sigma$ is definable]. Then $\sigma$ extends to an automorphism $\tau$ of $(M,f_n)$, but $\tau$ does not preserve $f_n$, since $$\tau(f_n(x_1,\dots,x_n)) = \tau(y) = \sigma(y) = z,$$ while $$f_n(\tau(x_1),\dots,\tau(x_n)) = f_n(\sigma(x_1),\dots,\sigma(x_n)) = f_n(x_1,\dots,x_n) = y.$$