Basic proof of identity in introductory set theory

**HeadmasterEel** · March 28th 2011, 06:53 AM

Hi, this is my first post here so please tell me if there is something wrong about it...

I just started to read "Notes on set theory" by Yiannis Moschovakis which is available online through my university library and now I am very unsure even about the first few introductory exercise. I would really appreciate some verification of my way to think here, especially since I am not very good in math and haven't read any thorough courses in logic et.c. before. Because this is just an online book which I picked up and started reading, there are no lecturers or such to ask either, hence I turn to mathhelpforum =)
Also, sorry about this wall of text! But I guess I should post my entire attempt...
...in the end of the post I try to be a bit more specific!
I realize that I may be way off with this attempt and there may very well be MAJOR misconceptions and errors. I appreciate all input, big thx in advance!

An example of a problem is :"Show that for every injection f : X $\rightarrow$ Y, and all $A,B \subseteq$ X

f[A $\cap$ B] = f[A] $\cap$ f[B].

Also show that this is identity does not always hold if f is not an injection."

First attempt at solution:

____________________start of first attempt________________________________

if x $\epsilon$ f[A $\cap$ B], then there is some y $\epsilon$ A $\cap$ B such that f(y)=x.

y $\epsilon$ (A $\cap$ B) $\Leftrightarrow$ y $\epsilon$ A $\wedge$ y $\epsilon$ B

Hence, x $\epsilon$ f[A $\cap$ B] $\Leftrightarrow$ y $\epsilon$ A $\wedge$ y $\epsilon$ B

If x $\epsilon$ f[A] $\cap$ f[B], then there is some y´ $\epsilon$ A $\wedge$ y´ $\epsilon$ B such that f(y´) = x.
That is, x $\epsilon$ f[A] $\cap$ f[B] $\Leftrightarrow$ y´ $\epsilon$ A $\wedge$ y´ $\epsilon$ B

Since f is an injection (stated in the problem formulation); x=f(y)=f(y´) $\Leftrightarrow$ y´= y

Using this to evolve the result from above:

x $\epsilon$ f[A] $\cap$ f[B] $\Leftrightarrow$ y´ $\epsilon$ A $\wedge$ y´ $\epsilon$ B $\Leftrightarrow$ y $\epsilon$ A $\wedge$ y $\epsilon$ B $\Leftrightarrow$ x $\epsilon$ f[A $\cap$ B]

f[A $\cap$ B] = f[A] $\cap$ f[B]

If f isn't an injection, then x=f(y)=f(y´) does not imply y=y´.

________________________end of first attempt_____________________________

Then I started to think about an example wof when the relation does not hold and I realized that my solution might not be very good.

Hence, I tried to adjust my first attempt:

____________________start of augmentation___________________________

If x $\epsilon$ f[A] $\cap$ f[B], then there is some y´ $\epsilon$ A such that f(y´) = x and y´´ $\epsilon$ B such that f(y´´)=x.

Since f is an injection, x=f(y´)=f(y´´) implies y´=y´´.
y´ $\epsilon$ A $\wedge$ y´ $\epsilon$ B

___________________________end of augmentation_____________________

Would this augmentation make the solution correct?
Then if y´ is not equal to y´´ , I think it would be quite easy to make a specific example of when the identity does not hold for a non-injective fcn. (for instance say f(x)=x^2 and y´=-y´´, right?)

What I´m concerned about is probably mainly this:

x

f[A]

f[B]

y´

A

y´

B

y

A

y

B
by the argument that x=f(y)=f(y´) implies y=y´for an injection.
Thereby, both
x

f[A

B]

y

A

y

B
and
x

f[A]

f[B]

y

A

y

B.

is this even correct?? necessary?

Big thx in advance for any input! // HeadmasterEel

**Plato** · March 28th 2011, 07:14 AM

Hello and welcome to MathHelpForum. I must tell you the your formatting makes that post very difficult to read, much less follow.

For any function $f[A\cap B]\subseteq f[A]\cap f[B]$ .
That is a straightforward proof from the definitions.

If $f$ is injective the equality holds. Suppose that $y\in(f[A]\cap f[B])$ .
Then $\left( {\exists a \in A} \right)\left[ {f(a) = y} \right] \wedge \left( {\exists b \in B} \right)\left[ {f(b) = y} \right]$ .
But $f$ is injective and $f(a)=y=f(b)$ so $a=b$ .
This means that $y\in f[A\cap B]$ . DONE.

**HeadmasterEel** · March 28th 2011, 01:15 PM

Thank you for your reply Plato!

I will try to make my posts more readable, but I have a hard time using this LaTex properly despite reading a tutorial...
Another issue is that I am not 100% sure how to formally use all logic symbols, so there may also be some peculiarities because of this. I beg any readers pardon and promise I will work on my logic skills!=)

I think the proof you presented is indeed straightforward.

May I state another identity and my attempt at a proof and ask you forum guys to verify it?

Let's say f is injective and I want to show that $f(A \setminus B) = f(A) \setminus f(B)$

$x \epsilon f(A \setminus B) \Leftrightarrow (\exists y \epsilon (A \setminus B))[f(y)=x]$
Since f is injective, $(\neg \exists b \epsilon B)[f(b)=x]$ , because f(b)=x would imply y=b but $y \epsilon (A \setminus B)$
Therefore, under the assumption that f is injective;
$x \epsilon f(A \setminus B) \Leftrightarrow ( (\exists y \epsilon (A \setminus B))[f(y)=x] \wedge (\neg \exists b \epsilon B)[f(b)=x]) ) \Leftrightarrow x \epsilon (f(A) \setminus f(B))$

Extra question:

$x \epsilon (f(A) \setminus f(B) ) \Rightarrow x \epsilon f(A\setminus B)$ regardless of if f is injective, but the reverse is only always true if f is injective. Am I right?

Thanks in advance!

**Plato** · March 28th 2011, 01:37 PM

Is it clear to you that if $f(y)\notin f[B]$ then it must follow that $y\notin B~?$

What is the relation between $f[B^c]~\&~(f[B])^c~?$ .

Then think about the fact that $A\setminus B=A\cap B^c$

Look at the first question you posted.

Thread: Basic proof of identity in introductory set theory

LinkBack

Thread Tools

Display

Basic proof of identity in introductory set theory

Similar Math Help Forum Discussions

Basic Set Theory

(Basic) Combinatorial Identity.

Basic Trig Identity

Basic identity proving

Introductory Number Theory Book?

Search Tags