5
$\begingroup$

I've found some time to read a little more on set theory, and I've come across the following question.

Suppose I have four sets $X$, $Y$, $Z$, and $W$ such that $Y\subseteq W$ and $Z\subseteq X$. Suppose also that $X\cup Y\sim Y$, where by $\sim$ I mean that the two sets $X\cup Y$ and $Y$ are equinumerous. How can I show that $Z\cup W\sim W$?

I thought the Bernstein-Schroeder theorem might be applicable. The identity function maps $W$ into $Z\cup W$ injectively, so I figured it suffices to show that there is an injection from $Z\cup W$ into $W$. From $X\cup Y\sim Y$, there is an injection $f\colon X\cup Y\to Y$, and thus $f|_X$ is an injection from $X$ into $Y$. Since $Z\subseteq X$ there is an injection from $Z$ to $X$, and likewise from $Y$ into $W$. Composing all these would give an injection from $Z$ into $W$. Those were my thoughts, but I don't think I can use them to show that $Z\cup W$ maps injectively into $W$. There must be a better way. Thanks for any help.

  • 0
    What you need id to make $Z$ and $W$ disjoint, isn't it.2011-02-18

2 Answers 2

4

$Z \cup W \subseteq X \cup W = X \cup (Y \cup (W \;\backslash Y)) = (X \cup Y) \cup (W \;\backslash Y) \sim Y \cup (W \;\backslash Y) = W \subseteq Z \cup W$

  • 0
    Thanks joriki, this looks like a neat solution! So in general, is it true that $A\sim B\implies A\cup C\sim B\cup C$? I figure one way to see this is that $A\cup C=A\cup (C\setminus A)$ and $B\cup C=B\cup(C\setminus B)$, and then if $f\colon A\to B$ is a bijection, define $g\colon A\cup C\to B\cup C$ by $g(x)=f(x)$ if $x\in A$ and $g(x)=x$ if $x\in C\setminus A$? Is this reasoning correct?2011-02-18
  • 0
    No, this is not true in general (though I also would have thought so at first sight) -- take $A=\{1\}$, $B=\{2\}$ and $C=\{2\}$. But there are two cases in which it's true, and both (can be made to) apply here: a) $A$ and $B$ disjoint from $C$, and b) $A$ and $B$ infinite. For a), form $X' = X \backslash (W \backslash Y)$ disjoint from $W \backslash Y$, and note $X' \cup Y \subseteq X \cup Y \sim Y \subseteq X' \cup Y$. For b), note that since $X \cup Y \sim Y$, either $X \subseteq Y$, in which case the statement to be proved is trivial, or $Y$ is infinite.2011-02-18
  • 0
    thanks for the further explanation. I see in this case that $X\cup Y$ and $Y$ are obviously not disjoint. Also, if $X\subseteq Y$, then the statement is trivial. So if $X\not\subseteq Y$, then we must necessarily have that $Y$ is infinite. But I don't see why $A\cup C\sim B\cup C$ when $A$ and $B$ are infinite is obviously true. How do you know this?2011-02-18
  • 0
    @yunone: The question isn't whether $X \cup Y$ and $Y$ are disjoint (BTW technically they could be if $X=Y=\{\}$), but whether they are both disjoint from $W \;\backslash Y$. Clearly $Y$ is, and, as I showed above, it doesn't matter whether $X$ (and hence $X \cup Y$) is. About infinite sets: This follows using cardinal arithmetic: $|A \cup C| \le |A| + |C| = |B| + |C| = \max(|B|,|C|) \le |B \cup C|$, but I see now that $|B| + |C| = \max(|B|,|C|)$ requires the axiom of choice, so we'd better stick with the argument from disjointness :-)2011-02-18
  • 0
    To be specific, it requires the Zorn's lemma, which is obviously equivalent to The Axiom of Choice.2011-02-18
1

If $f\colon X\cup Y\to Y$ is an injection and and $Z\subseteq X$, then the restriction to $f\colon Z\cup Y\to Y$ is also an injection. With $Y\subseteq W$ and using the identity injection $i\colon W \backslash Y \to W \backslash Y$ restricted to the injection $i\colon W \backslash (Z \cup Y) \to W \backslash Y$, you can combine $f|_{Z\cup Y}$ and $i|_{W \backslash (Z \cup Y)}$ to provide an injection from $Z\cup W$ to $W$

  • 0
    Thanks for your response Henry. I take it you're suggesting something like this: $g\colon Z\cup W\to W$ such that $g(x)=f(x)$ if $x\in Z\cup Y$, and $g(x)=x$ if $x\in W\setminus(Z\cup Y)$. So when $g(x)=f(x)$, $g(x)\in Y$, and otherwise $g(x)=x\in W\setminus(Z\cup Y)$. So since $f$ and $i$ have disjoint ranges, and are injective on their own domains, $g$ must be injective as well.2011-02-18
  • 0
    That is indeed what I was trying to do.2011-02-18
  • 0
    Things may be easier using the product of sets, the set-theoretical sum of sets [here](http://en.wikipedia.org/wiki/Disjoint_union#Set_theory_definition) and your question will be totally settled up by basic theorems of set theory.2011-02-18