Welcome to our community

Be a part of something great, join today!

How to remember set theory properties?

Ragnarok

Member
Jul 10, 2013
41
I'm an undergraduate studying math taking intermediate proof-writing courses, and there are certain basic identities of set theory and functions that still confuse me - i.e., I have to reprove them or think about them carefully every time. Examples:

\(\displaystyle (A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)\)

If \(\displaystyle g\circ f\) is injective, then \(\displaystyle f\) is injective (but not necessarily \(\displaystyle g\)). If \(\displaystyle g\circ f\) is surjective, then \(\displaystyle g\) is surjective (but not necessarily \(\displaystyle f\)).

Given \(\displaystyle f:A\rightarrow B\), \(\displaystyle A_0,A_1\subset A\) and \(\displaystyle B_0,B_1\subset B\):

\(\displaystyle f^{-1}(B_0\cap B_1)=f^{-1}(B_0)\cap f^{-1}(B_1)\) and

\(\displaystyle f(A_0\cap A_1)\subset f(A_0)\cap f(A_1)\) - equality holds if \(\displaystyle f\) is injective.

The thing is, proving such things doesn't seem to help me remember them since the proof is rather mechanical and symbolic. Does anyone have any tips for learning them better, or any book suggestions that might give me some intuition for it? Thanks!
 

ThePerfectHacker

Well-known member
Jan 26, 2012
236
I do not remember any of those rules. I just assume the appropriate rules are true anytime I have to prove something and then do a quick check for the ones I assumed.
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
These are not "proofs" (for which there are, truly, "no substitutes") but "heuristics" which may, or may not help you.

For your first example, think of the two projection functions:

$p_1:X \times Y \to X$
$p_2: X \times Y \to Y$

defined in the obvious way.

For your second example: we have two "cases" with functions:

1. A function "preseves" set information (this is what injective functions do)
2. A function "collapes" set information

If the first function is a composition "collapses information" there is no way for the second function to "blow it back up". So if $g\circ f$ is injective, we cannot have $f$ NOT injective. We can actually say a "little bit" about $g$ in this situation: it is injective on the image of $f$ which lies in its domain. We can't tell what $g$ does to points of its domain NOT in the image of $f$, because $g \circ f$ never sees them.

On the other hand, if $g \circ f$ is surjective, then every element of the co-domain of $g \circ f$ was once an element in the domain of $f$. To get there it had to "pass through $g$", so there must have been some element in the domain of $g$ (which is also in the image of $f$) that $g$ maps to our original co-domain element.

When thinking about injective functions $f:X \to Y$, it is often helpful to use the "typical" injective function $1_X: X \to X$ as a quick "reality check". Similarly, it is often helpful to think of a CONSTANT function $g:X \to \{x\}$ as a "typical" surjective function.

With the "inverse map" $f^{-1}$ you can safely assume it preserves ALL set operations. Verify this ONE TIME, and then just use this fact forever more.

Similarly, if $f$ is injective, it preserves ALL set operations. If it is NOT injective, we have a function of the "collapsing" type. One simple way to keep straight "which way" the containment goes is to use a simple function like this:

$A = \{a,b,c\}, B = \{x,y\}$

$f: A \to B$ defined as: $f(a) = x, f(b) = y, f(c) = x$.

Let $A_0 = \{a,b\}$ and $A_1 = \{b,c\}$

Then $f(A_0 \cap A_1) = f(\{b\}) = \{y\}$

whereas $f(A_0) \cap f(A_1) = B \cap B = B$.
 

solakis

Active member
Dec 9, 2012
304
I'm an undergraduate studying math taking intermediate proof-writing courses, and there are certain basic identities of set theory and functions that still confuse me - i.e., I have to reprove them or think about them carefully every time. Examples:

\(\displaystyle (A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)\)

If \(\displaystyle g\circ f\) is injective, then \(\displaystyle f\) is injective (but not necessarily \(\displaystyle g\)). If \(\displaystyle g\circ f\) is surjective, then \(\displaystyle g\) is surjective (but not necessarily \(\displaystyle f\)).

Given \(\displaystyle f:A\rightarrow B\), \(\displaystyle A_0,A_1\subset A\) and \(\displaystyle B_0,B_1\subset B\):

\(\displaystyle f^{-1}(B_0\cap B_1)=f^{-1}(B_0)\cap f^{-1}(B_1)\) and

\(\displaystyle f(A_0\cap A_1)\subset f(A_0)\cap f(A_1)\) - equality holds if \(\displaystyle f\) is injective.

The thing is, proving such things doesn't seem to help me remember them since the proof is rather mechanical and symbolic. Does anyone have any tips for learning them better, or any book suggestions that might give me some intuition for it? Thanks!
If WE PUT :

A={a,b}

B={c,d}

C={e,f}

D={k,l}

Can you then prove the set identity you mentioned??
 

Ragnarok

Member
Jul 10, 2013
41
Thank you so much for the detailed response, Deveno, and I'm sorry it took me so long to respond to it. Your advice is exactly what I was looking for!