Set Theory contradiction

If

f

is a one to one function of the set

X

to the set

Y

and

A, B \subseteq X,

then

f(A \oplus B) = f(A) \oplus f(B)

If

y \in f(A \oplus B)

then there exists

x \in A \oplus B

so that

f(x) = y

. Then

x \in A \setminus B

or

x \in B \setminus A

So then

x \in A

so

f(x) \in f(A)

and

f(x) \in f(B)

as well so there exists

a \ z \in B

with

f(x) = f(z)

and

f

is a one to one so surely

z = x

with

x \in B

contradicting

x \in A \setminus B

So the contradiction proves that

f(A \oplus B) \subseteq f(A \oplus B)

and in turn

f(A \oplus B) = f(A) \oplus (B)

is true.

Is this correct?

Reply 1

DFranklin

18

Original post by AishaGirl

If

f

is a one to one function of the set

X

to the set

Y

and

A, B \subseteq X,

then

f(A \oplus B) = f(A) \oplus f(B)

What is

\oplus

supposed to mean here? I've never seen that notation used in this context.

So the contradiction proves that

f(A \oplus B) \subseteq f(A \oplus B)

I think you have a typo here: showing

f(A \oplus B) \subseteq f(A \oplus B)

is hardly an achievement!

Reply 2

EternalLight

OP

2

Original post by DFranklin

What is

\oplus

supposed to mean here? I've never seen that notation used in this context.

I think you have a typo here: showing

f(A \oplus B) \subseteq f(A \oplus B)

is hardly an achievement!

Oh yes my bad, I meant to say it proves that

f(A) \oplus (B) \subseteq f(A \oplus B)

\oplus

is the symmetric difference, some books use the

\triangle

symbol. Sorry I should have clarified that.

Reply 3

DFranklin

18

Original post by AishaGirl

Oh yes my bad, I meant to say it proves that

f(A) \oplus (B) \subseteq f(A \oplus B)

\oplus

is the symmetric difference, some books use the

\triangle

symbol. Sorry I should have clarified that.

OK, I perhaps should have guessed, but

\oplus

is used for a lot of other things at university and so it's not usual for it to be used for symmetric difference at that level.

Original post by AishaGirl

If

y \in f(A \oplus B)

then there exists

x \in A \oplus B

so that

f(x) = y

. Then

x \in A \setminus B

or

x \in B \setminus A

So then

x \in A

so

f(x) \in f(A)

and

f(x) \in f(B)

as well

I don't see why this line follows. (I also don't see where you are "starting" your contradiction; it's usual to say something like

"assume (for contradiction) that X is true. {...your argument...}, but this gives a contradiction and therefore it cannot be the case that X is true".

It's important to have the preamble, because (since you want a contradiction) the initial assumption is wrong, and if you're going to write something you know is wrong, you need to make it clear what the reason is). You don't have to actively say "for contradiction" (though I would do so at A-level), but you do need to make it clear it's an assumption, not something you think is actually true.

I'm not sure I'd prove this by contradiction anyhow, rather show that if

x \in f(A \oplus B)

then

x \in f(A) \oplus f(B)

and vice-versa.

(edited 7 years ago)

Reply 4

EternalLight

OP

2

@DFranklin

If I do it in the other direction and suppose

y \in f(A) \oplus f(B)

then

y \in f(A) \setminus f(B)

or

y \in f(B) \setminus f(A)

then

x \in A

such that

f(x) = y

Suppose that

x \in B

also then

y = f(x) \in f(B)

again contradicting the fact that

y \in f(A) \setminus f(B)

So

y \in A \setminus B

proves that it the subset is true? I don't see the problem with using contradiction, are you just saying it's a lengthier way of doing it or rather that it's bad practice?

What is a simpler way of doing it?

Thanks.

Reply 5

DFranklin

18

Original post by AishaGirl

@DFranklin

If I do it in the other direction and suppose

y \in f(A) \oplus f(B)

then

y \in f(A) \setminus f(B)

or

y \in f(B) \setminus f(A)

then

x \in A

Why do you say that

x \in A

? It clearly doesn't have to be.

I don't see the problem with using contradiction, are you just saying it's a lengthier way of doing it or rather that it's bad practice?

Actually I'll kind of take that back; I think you'll probably have some contradiction argument somewhere. It's just that when you say "I'm going to prove X by contradiction", you usually mean "I'm going to assume X isn't true and derive a contradiction", whereas here it's more you're going to get some way down the road and then say to finish "I'd like Y to be true, and it must be true, because otherwise we get a contradiction".

Reply 6

atsruser

11

Original post by AishaGirl

What is a simpler way of doing it?

I've only skimmed the previous posts so I'm not sure if your contradiction approach will work, but DFranklin has already outline another approach.

In fact, it is the standard approach. If you want to prove that

A=B

where A and B are sets, then you have to show that

x \in A \Leftrightarrow x \in B

since that is the definition of equal sets.

Reply 7

DFranklin

18

Original post by atsruser

I've only skimmed the previous posts so I'm not sure if your contradiction approach will work, but DFranklin has already outline another approach.

In fact, it is the standard approach. If you want to prove that

A=B

where A and B are sets, then you have to show that

x \in A \Leftrightarrow x \in B

since that is the definition of equal sets.

So, actually I think this is what she's trying to do; the contradiction comes later. "As you know...", if you're trying to prove things with the symmetric difference it's pretty common to get to a point where you want to say x is in M or N, but not both, and so end up with something like, "suppose X is in M and M, then ... which is a contradiction".

I have to say that I kind of hate "fundamental" questions about set operations, because it always feels to me like "it's obvious", and any step-by-step proof doesn't actually make the truth of the statement clearer, rather the opposite. This probably indicates some deep flaw in my character... :smile:

Set Theory contradiction

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you