4
$\begingroup$

in a previous question, I mistakenly attempted to subtract one cardinal number from another. Anyway, this got me to thinking, suppose I have two sets $X$ and $Y$, with $Y\subseteq X$. Suppose also that $|X|=|Y|=|X-Y|=\kappa$ for some cardinal number $\kappa$. Does there exist some bijection $f\colon X\to X$ such that $Y$ consists of all fixed points of $f$?

I thought the easiest example comes from working with countable sets. If $X=\mathbb{Z}$ and $Y$ is the set of even integers, then we could take $f$ to be $ f(x)=\begin{cases} x, &\text{if }x\text{ is even} \\ x+2, &\text{if }x\text{ is odd} \\ \end{cases} $

Of course, we could do the same thing with the set of odds. I wasn't able to think of any more examples.

But I'm curious, is it possible to do this in the more general sense, for any sets where $|X|=|Y|=|X-Y|=\kappa$, and $Y\subseteq X$? That is, can we prove there exists a bijection on $X$ such that $Y=\{x\in X\ |\ f(x)=x\}$? After thinking about it, I suppose it suffices to find a derangement $g$ (I hope I'm using that term correctly, I've only seen it used in combinatorics on finite sets) on $X-Y$, and then we could let $f=g\cup id|_Y$. Thanks!

  • 0
    @Arturo, thank you for your efforts, I'll be quite happy to see the end product. Of course there is no rush.2011-04-02

2 Answers 2

4

Of course, as Arturo points out, the axiom of choice is enough to show what you are asking for. A slightly simpler way to show it is this: Let $Z$ be an infinite set. Since by the axiom of choice we have $|Z\times 2|=|Z|$ take a function $g$ such that $g(a,0)=(a,1)$ and $g(a,1)=(a,0)$ for every $a\in Z$. Then $id\cap g=\varnothing$. Composing a bijection $f:Z\to Z\times2$ with $g$ and then with $f^{-1}$ you get what you want.

On the other hand I have constructed a model in which the countable axiom of choice is true (also the axiom of dependent choice is true) while there exists a subset of real numbers for which no such function you are looking for exists. The construction is done either through forcing or using atoms. You can find about generic models and symmetric models in Jech's "Set Theory" or Jech's "The Axiom of Choice".

The basic idea is to add regular many Cohen reals ($\aleph_1$ for example) through the notion of forcing (or have $\aleph_1$ atoms). Then take a normal filter on the group of permutations of $\aleph_1$ (or of the atoms) that is generated by the countable subsets of $\aleph_1$ ( i.e. generated by $\{\pi\in\mathcal{G} : \pi_{\upharpoonright E}=id\}$ for $E\subset\aleph_1$ and $|E|\leq\aleph_0$ and $\mathcal{G}$ the permutations of $\aleph_1$).

Then functions with countable domain will remain inside the symmetric submodel and thus countable choice and dependant choice will be satisfied by the symmetric model. But a permutation of all the Cohen reals that isn't finally constant will be impossible to exist inside the symmetric submodel thus making what you are asking for impossible and a fortiori making $|Z|+|Z|=|Z|$ fail inside the model.

Edit: As Asaf points out in the comments this easily generalizes (for every cardinal $\kappa$) to make $AC_\kappa$ hold in the symmetric model while there exists a counterexample to what you are looking for.

  • 0
    @Arturo: I wholeheartedly recommend that you do. It is a great reference book, and the proofs are not very hard once you understand the Fraenkel models (permutation models of ZFA).2011-04-03
2

As you note, the question amounts to asking if you can find a derangement of any infinite set. So let $Z$ be an infinite set.

Assuming the Axiom of Choice, the answer is "yes". There is a bijection between $Z$ and $Z\times\omega$, where $\omega$ is the first infinite ordinal (since $\kappa\aleph_0 = \max\{\kappa,\aleph_0\}=\kappa$). Let $g\colon Z\to Z\times\omega$ be a bijection. Now let $f$ be a derangement of $\omega$ (e.g., map $2n$ to $2n+1$, and $2n+1$ to $2n$ for every nonnegative $n$). Define $h\colon Z\to Z$ by $h= g^{-1}\circ(\mathrm{id}\times f)\circ g$, where $\mathrm{id}\times f\colon Z\times\omega \to Z\times\omega$ is given by $(\mathrm{id}\times f)(z,k) = (z,f(k))$.

Since no element of $Z\times \omega$ is fixed by $\mathrm{id}\times f$, and $g$ is a bijection, no element of $Z$ is fixed by $h$.

Disclaimer: I don't know exactly how much AC is needed here; it is only required to find a bijection between infinite $X$ and $X\times\omega$, which may or may not require less than full AC; I'm sure one of our resident set theorists will set me straight on this at some point.

So, given $X$ and $Y$ as you describe, construct a derangement $h$ for $X-Y$ and take $h\cup\mathrm{id}_Y$, as you suggest.

  • 0
    @Apostolos: Mostly, I am curious as to just how much AC is needed for the above, and I'm not surprised that *some* choice is needed; perhaps posting details would be too much, but some indication of how much choice suffices (or how much does not suffice) would probably be a nice addition.2011-04-02