Home » Math » Quick Notes on Elementary Set Theory and Functions

1. # Cantor’s Concept of a set

A set $S$ is any collection of definite, distinguishable objects of our intuition or of our intellect to be conceived as a whole. The objects are called the elements or members of set $S$

2. # The intuitive principle of extension for sets

Two sets are equal if and only if (iff) they have the same members. i.e., $X=Y \, \Leftrightarrow \,\forall x \in X \text{and} \ x \in Y$.

3. # The intuitive principle of abstraction

A formula (syn: property) $P(x)$ defines a set $A$ by the convention that the members of $A$ are exactly those objects $a$ such that $P(a)$ is a true statement. $\Rightarrow a \in \{ x|P(x) \}$.

4. # Operations with/for sets

• Union (Sum or Join)$A \cup B= \{ x | x \in A \, \text{or} \, x \in B \}$
• Intersection (Product or Meet)
$A \cap B= \{ x| x\in A \, \text{and} \, x\in B \}$
• Disjoint Sets $A$ and $B$ are disjoint sets iff $A \cap B=\emptyset : \text{an empty set}$ and they intersect iff $A \cap B \ne \emptyset$
• Partition of Sets A partition of a set $X$ is a disjoint collection
$\mathfrak{X}$ of non-empty and distinct subsets of $X$ such that each member of $X$ is a member of some (and hence exactly one) member of $\mathfrak{X}$.
For example: $\{ \{a,b\} \, \{c \} \, \{d, e\} \}$ is a partition of $\{a,b,c,d,e\}$.
• Absolute Complement of a set $A$ is usually represented by $\Bar{A} = U-A = \{ x | x \notin A \}$ where $U$ is universal set.
• Relative Complement of a set $A \, \text{relative to another set} \, X$ is given by $X-A=X\cap \Bar{A}=\{ x \in X | x \notin A\}$.
5. # Theorems on Sets

1. $A \cup (B \cup C) = (A \cup B) \cup C$
2. $A \cap (B \cap C) = (A \cap B) \cap C$
3. $A \cup B= B \cup A$
4. $A \cap B= B \cap A$
5. $A \cup (B \cap C)= (A \cup B) \cap (A \cup C)$
6. $A \cap (B \cup C)= (A \cap B) \cup (A \cap C)$
7. $A \cup \emptyset= A$
8. $A \cap \emptyset= \emptyset$
9. $A \cup U=U$
10. $A \cap U=A$
11. $A \cup \Bar{A}=U$
12. $A \cap \Bar{A}=\emptyset$
13. If $\forall A \ , A \cup B=A$ $\Rightarrow B=\emptyset$
14. If $\forall A \ , A \cap B=A \Rightarrow B=U$
15. Self-dual Property: If $A \cup B =U$ and $A \cap B=\emptyset \ \Rightarrow B=\Bar{A}$
16. Self Dual: $\Bar{\Bar{A}}=A$
17. $\overline{\emptyset}=U$
18. $\Bar{U}= \emptyset$
19. Idempotent Law: $A \cup A=A$
20. Idempotent Law: $A \cap A =A$
21. Absorption Law: $A \cup (A \cap B) =A$
22. Absorption Law: $A \cap (A \cup B) =A$
23. de Morgen Law: $\overline{A \cup B} =\Bar{A} \cap \Bar{B}$
24. de Morgen Law: $\overline{A \cap B} =\Bar{A} \cup \Bar{B}$
6. # Another Theorem

The following statements about set A and set B are equivalent to one another

1. $A \subseteq B$
2. $A \cap B=A$
3. $A \cup B =B$
7. # Functions

Function is a relation such that no two distinct members have the same first co-ordinate in its graph. $f$ is a function iff

1. The members of $f$ are ordered pairs.
2. If ordered pairs $(x, y)$ and $(x, z)$ are members of $f$, then $y=z$
8. Other words used as synonyms for the word ‘function’ are ‘transformation’, ‘map’, ‘mapping’, ‘correspondence’ and ‘operator’.
9. # Notations for functions

A function is usually defined as ordered-pairs, see above, and $\text{ordered pair } (x,y) \in \text{function } f$ so that $xfy$ is (was) a way to represent where $x$ is an argument of $f$ and $y$ is image (value) of $f$.
Other popular notations for $(x,y)\in f$ are: $y : xf$, $y=f(x)$, $y=fx$, $y=x^f$.

10. # Intuitive law of extension for Functions

Two sets $f$ and $g$ are equal iff they have the same members (here, Domain and Range) $\Rightarrow f=g \Leftrightarrow D_f=D_g \ \text{and } \ f(x)=g(x)$

11. # Into Function

A function $f$ is into $Y$ iff the range of $f$ is a subset of $Y$. i.e., $R_f \subset Y$

12. # Onto Function

A function $f$ is onto $Y$ iff the range of $f$ is $Y$. i.e., $R_f=Y$

13. Generally a mapping is represented by $f : X \rightarrow Y$.
14. # One-to-One function

A function is called one-to-one if it maps distinct elements onto distinct elements.
A function $f$ is one-to-one iff $x_1 \ne x_2 \Leftrightarrow f(x_1) \ne f(x_2)$ and $x_1 = x_2 \Leftrightarrow f(x_1)=f(x_2)$

15. # Restriction of Function

If $f : X \rightarrow Y$ and if $A \subseteq X$, then $f \cap (A \times Y)$ is a function on $A \ \text{into } \ Y$, called the restriction of $f$ to $A$ and $f \cap (A \times Y)$ is usually abbrevated by $f|A$.

16. # Extension of function

The function $f$ is an extension of a function $g$ iff $g \subseteq f$.