Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What you need id to make $Z$ and $W$ disjoint, isn't it. –  awllower Feb 18 '11 at 15:00
add comment

2 Answers 2

up vote 3 down vote accepted

$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$

share|improve this answer
    
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? –  yunone Feb 18 '11 at 8:14
    
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. –  joriki Feb 18 '11 at 8:54
    
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? –  yunone Feb 18 '11 at 9:12
    
@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 :-) –  joriki Feb 18 '11 at 9:42
    
To be specific, it requires the Zorn's lemma, which is obviously equivalent to The Axiom of Choice. –  awllower Feb 18 '11 at 15:05
add comment

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$

share|improve this answer
    
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. –  yunone Feb 18 '11 at 9:29
    
That is indeed what I was trying to do. –  Henry Feb 18 '11 at 11:42
    
Things may be easier using the product of sets, the set-theoretical sum of sets here and your question will be totally settled up by basic theorems of set theory. –  awllower Feb 18 '11 at 15:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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