2

I would like to characterize the class of (finite) structures that can be partitioned into two disjoint sets $X,Y$ having the same cardinality, using second order logic (with usual logical connectives plus equality) :

we can define an unary predicate $X(x)$ that is true iif $x \in X$ and a binary predicate $B(x,y)$ for the 1:1 mapping between elements of $X$ and $Y$; so we have:

$\exists X, \exists B$
$(\forall x,y \; B(x,y)\rightarrow B(y,x))$ (B is symmetric)
$\land (\forall x,y,z \; (B(x,y) \land B(x,z))\rightarrow y=z)$ (B is a mapping)
$\land (\forall x \; X(x) \rightarrow \exists y (\neg X(y) \land B(x,y)))$ (every element of X is mapped to an element of Y)
$\land (\forall x \; \neg X(x) \rightarrow \exists y (X(y) \land B(x,y)))$ (every element of Y is mapped to an element of X)

Is there a more succinct formula?

Vor
  • 690

1 Answers1

2

$$\exists f\forall x, y[(f(x)=f(y)\iff x=y)\wedge (f(x)\not=x)\wedge (f(f(x))=x)].$$ This says intuitively that the universe can be partitioned into pairs (the $f$-orbits); for finite structures, this is the same as saying that the universe has domain of even cardinality.

Interestingly, this is meaningfully different from what you've written! It is consistent with ZF (= set theory without choice) that there is an infinite set $A$ which can be partitioned into pairs but cannot be partitioned into two equal-size sets (or indeed any pair of infinite sets). A structure with such a set as its domain would satisfy my sentence but not yours. Of course, with choice our sentences are equivalent.

Noah Schweber
  • 245,398