Re: Every set x equinumerous with a set y disjoint from x?

David C. Ullrich wrote:
I really don't see what the problem is. Where does the following
argument use AC?

It doesn't. I was asking about the axiom of choice in your earlier
proof.

Thm. If S is a set then there exists a set S' disjoint from S
which is equinumerous with S.

Proof: Let T be the set of all y such that there exists x with
(x,y) in S. Choose y such that y is not an element of T. Let
S' = S x {y} = {(x,y) : x in S}. Then x <-> (x,y) is a bijection
of S and S', and S' is disjoint from S, since y is not in T. QED.

Thank you very much for that; it settles my original question in the
thread. It's along the lines I was working, but I failed to think of
the strategy of using the range of S.

Silly details, written out explicitly lest AC be lurking in
the bits left to the reader:

You seem a bit miffed. You are doing me a favor, entirely gratis, by
posting such proofs. I appreciate that. But my previous question was
sincere: there was a step in your previous proof that I couldn't figure
out how to justify without the axiom of choice. I had no way of knowing
you had yet another proof in mind that doesn't raise that question.
Anyway, I understand your proof now and I thank you for it.

SD1: Define f : S -> S' by f(x) = (x,y). The definition of
S' shows that f is surjective. And (x,y) = (x',y) implies that
x = x', hence f is injective.

Of course. I wouldn't have questioned this.

SD2: Suppose that z in in S intersect S'. Then the definition
of S' shows that there exists x in S with z = (x,y). So
(x,y) is in S, hence the definition of T shows that t is in
T, contradicting the choice of y.

I think 't' is a typo there (should be 'y'), but of course I wouldn't
have questioned SD2.

SD3: If T is any set then there exists y such that y is not in T.
Proof: Suppose to the contrary that every y is an element of T.
Let A = {y in T: not y in y}. Since A is an element of T we
have A in A if and only if not A in A, contradiction.

I had told you that of course I know that.

Again, thank you for the proof.

MoeBlee

.

Relevant Pages