MHB How to remember set theory properties?

Ragnarok7
Messages
50
Reaction score
0
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:

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

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

Given $$f:A\rightarrow B$$, $$A_0,A_1\subset A$$ and $$B_0,B_1\subset B$$:

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

$$f(A_0\cap A_1)\subset f(A_0)\cap f(A_1)$$ - equality holds if $$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!
 
Physics news on Phys.org
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.
 
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$.
 
Ragnarok said:
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:

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

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

Given $$f:A\rightarrow B$$, $$A_0,A_1\subset A$$ and $$B_0,B_1\subset B$$:

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

$$f(A_0\cap A_1)\subset f(A_0)\cap f(A_1)$$ - equality holds if $$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??
 
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!
 
Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
Thread 'Detail of Diagonalization Lemma'
The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.

Similar threads

Back
Top