Quick Notes on Elementary Set Theory and Functions

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$
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$ .
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) \}$ .
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\}$ .
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}$
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$
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$
Other words used as synonyms for the word ‘function’ are ‘transformation’, ‘map’, ‘mapping’, ‘correspondence’ and ‘operator’.
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$ .
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)$
Into Function

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

A function $f$ is onto $Y$ iff the range of $f$ is $Y$ . i.e., $R_f=Y$
Generally a mapping is represented by $f : X \rightarrow Y$ .
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)$
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$ .
Extension of function

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