# Thread: Basic proof of identity in introductory set theory

1. ## Basic proof of identity in introductory set theory

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 =)
...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$ $\epsilon$ B such that f(y´) = x.
That is, x $\epsilon$ f[A] $\cap$ f[B] $\Leftrightarrow$ $\epsilon$ A $\wedge$ $\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$ $\epsilon$ A $\wedge$ $\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´´.
$\epsilon$A $\wedge$ $\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] A B yA yB
by the argument that x=f(y)=f(y´) implies y=y´for an injection.
Thereby, both
x f[A B] yA yB
and
x f[A] f[B] yA yB.

is this even correct?? necessary?

2. 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.

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?

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