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!

  • $\begingroup$ Is the cases environment not working now? $\endgroup$ – yunone Apr 2 '11 at 2:53
  • $\begingroup$ It is traditional to denote infinite cardinals with greek letters; you might want to use $\kappa$ (\kappa) instead of $k$, and specify it is infinite (though of course, the only other possibility is $|X|=|Y|=|X-Y|=0$... (-: ) $\endgroup$ – Arturo Magidin Apr 2 '11 at 2:53
  • $\begingroup$ @Arturo, thanks!, I was not aware. I'll do that right now. $\endgroup$ – yunone Apr 2 '11 at 2:54
  • $\begingroup$ @yunone: You should not put math formulas inside of \text arguments; that's what confused the renderer. See the edit for the fix. $\endgroup$ – Arturo Magidin Apr 2 '11 at 2:54
  • $\begingroup$ @Arturo, thanks for that as well, I will remember that for next time. $\endgroup$ – yunone Apr 2 '11 at 2:56

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.

  • $\begingroup$ Sigh; can't believe I went all the way to $\omega$ when $2$ was enough... (-: $\endgroup$ – Arturo Magidin Apr 2 '11 at 20:02
  • 2
    $\begingroup$ Without the full blown power of choice there will always be some pathological examples like that. One can do the same process with $\kappa$ many atoms and ensure $AC_\kappa$ holds in the permutation model. However do note that working in models of ZFA and using the Jech-Sochor theorem requires less attention to the minor details which you have looked over when working in forcing models. Nonetheless, that is a good answer! $\endgroup$ – Asaf Karagila Apr 2 '11 at 20:05
  • 1
    $\begingroup$ @yunone: Yes. The point is that the full axiom of choice is needed. My argument shows that the axiom of countable choice and the axiom of dependent choice (which are two weaker "forms" of the axiom of choice) are not enough to show that any set has a derangement. This is done by showing that in a model that satisfies these axioms there exists a set that doesn't have a derangement. Furthermore, as Asaf points out the result can be generalized to axioms stronger than the ones I mentioned but still weaker that the axiom of choice. (cont.) $\endgroup$ – Apostolos Apr 3 '11 at 0:11
  • 1
    $\begingroup$ @yunone: The construction of models in which choice fails is related with arguments of symmetry that were noticed early on. Bertram Russell gave the following example to show when the axiom of choice is needed: If we have an infinite pair of shoes there are ways to pick one shoe from each pair, for example pick the left shoe of each pair. Choice is needed when we have an infinite pair of socks since socks in a pair are indistinguishable from one another. In turn Fraenkel came up with a model of set theory with atoms in which choice failed. (cont.) $\endgroup$ – Apostolos Apr 3 '11 at 0:12
  • 1
    $\begingroup$ @yunone: Fraenkel's construction was about sets that weren't altered under certain permutations of the atoms: Given an infinite pair of socks (the atoms) the permutation that sends the left sock to the right one (and vice versa) of all but finite of the pairs, leaves each pair unchanged and the set of the pairs unchanged. But any choice function for the infinite pair of socks is bound to change since only finite of the pairs don't have their socks interchange. I wanted countable choice so I used permutations that changed all but countable many elements. This is the basic idea behind my post. $\endgroup$ – Apostolos Apr 3 '11 at 0:14

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.

  • $\begingroup$ Thanks for your quick answer Arturo. I too am now curious to see how much choice is needed. $\endgroup$ – yunone Apr 2 '11 at 3:18
  • $\begingroup$ @yunone: Well, if none of them poke their head in here (say, by Monday afternoon; it is the weekend, after all (-; ) we can always post it as a question. $\endgroup$ – Arturo Magidin Apr 2 '11 at 3:20
  • $\begingroup$ @yunone: I came up with a model that I'm fairly certain satisfies the countable axiom of choice (and I think that it satisfies the principle of dependent choice) in which no such function exists, though to construct it either forcing or set theory with atoms is required. Should I post it or are you looking for something more specific? $\endgroup$ – Apostolos Apr 2 '11 at 16:09
  • $\begingroup$ @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. $\endgroup$ – Arturo Magidin Apr 2 '11 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.