Definitions and Notations
A set is a well-defined, unordered collection of distinct objects. These objects are also called elements of the set $A$, that may be numbers or any other objects.
Generally, a set is represented using curly braces { } that contain its elements, and is typically denoted by an upper case and the elements are denoted by lower case; that is $A=\{a,b,c \cdots \cdots \}$ or $A=\{a_1,a_2,a_3 \cdots \cdots \}$ .
For example, $A = \{101, 102, 103, 104, 105\} $or $B =\{a, e, i, o, u\}$, etc. A set can also be defined using predicates or rules — that is, a condition or property that all elements of the set must satisfy. For example, the set $A = \{101, 102, 103, 104, 105\}$ can be described as the set of the first five room numbers of a motel, and $B = \{a, e, i, o, u\}$ can be described as the set of vowels in the English alphabet.
Well-defined means the question “does x belong to $A$?” has a definitive yes or no answer based on the condition or property of the set. Distinct means each element appears at most once — $\{1, 1, 2\}$ reduces to $\{1, 2\}$.
We write $x \in A$ to indicate that $x$ is a member (or an element) of $A$; when $x$ is not an element of $A$ then we write $x \notin A$
The set that contains no elements is called the empty set, if it has at least one element then it is called non-empty set. Technically the symbol for empty set is $A=\emptyset$ or most commonly used symbol is $A=\phi$ or sometimes $A=\{ \}$
Also the number of elements of a set is termed as cardinality that is denoted by |A| , accordingly |∅| = 0
A singleton is a set with exactly one element: $A=\{a\}$ and $|A| = 1$.
If $A$ and $B$ are two sets, and if every element of $A$ is an element of $B$, we say that $A$ is a subset of $B$ and write $A \subseteq B$ or $B \supseteq A$; it is also termed as – “$B$ contains $A$ or $A$ is contained in $B$”
Further, if there is an element of $B$ which is not in $A$ then $A$ is a proper subset of $B$, $A \subset B$
If $A \subset B$ and $B \subset A$ then $A = B$ otherwise $A \ne B$
Familiar Number Systems – well defined examples for sets
$\mathbb{N} = \{1, 2, 3, \cdots \cdots \}$, set of Natural numbers
$\mathbb{Z} = \{\cdots \cdots -3,-2, -1, 0, 1, 2, 3, \cdots \cdots \}$, set of Integers
$\mathbb{Q} = $ Set of Rationals, numbers of the form $\frac{m}{n}$ such that $m, n \in \mathbb{Z}$ and $n \ne 0 $ or $\mathbb{Q} =\{\frac{m}{n} / m, n \in \mathbb{Z}, n \ne 0\}$
Set of Irrationals $\mathbb{S}$ are the numbers that cannot be written in the form $\frac{m}{n}, n \ne 0$
It is obvious to see, $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q}$
1. Set Operations
Let us assume $A = $ { x ∈ ℤ / x is even }, and $B = $ { x ∈ ℤ / x is divisible by 3 }
1.1 Union: A ∪ B
$$A \cup B = \{x : x \in A \text{ or } x \in B \}$$ All elements belonging to $A$ or $B$ or both; so union of two sets yield a set whose elements posess the property of $A$ or $B$ or both.
In the example, $A \cup B =$ integers that are even or divisible by 3 or both =$\{…, −6, −4, −3, −2, 0, 2, 3, 4, 6, 8, 9, 10, 12, …\}$
1.2 Intersection: A ∩ B
$$A \cap B = \{ x : x \in A \text{ and } x \in B \}$$ Only elements belonging to both simultaneously; so intersection of two sets yield a set whose elements possess the property of $A$ and $B$.
Example: $A \cap B =$ integers divisible by both 2 and 3 $= \{ \cdots \cdots, −12, −6, 0, 6, 12, 18, \cdots \cdots, \}$
Two sets are disjoint if $A \cap B = \phi$ — they share no elements.
1.3 Difference: $A − B$
$$A – B = \{ x : x \in A \text{ and } x \notin B \}$$ Elements of $A$ with all elements of $B$ removed.
Example: $A − B =$ even integers not divisible by 3 $= \cdots \cdots, −4, −2, 2, 4, 8, 10, 14, 16, \cdots \cdots \}$
1.4 Difference: $B − A$
$$B – A = \{ x : x \notin A \text{ and } x \in B \}$$ Elements of $B$ with all elements of $A$ removed.
Example: $B − A =$ odd multiples of 3: $= \cdots \cdots, −9, −3, 3, 9, 15, 21= \cdots \cdots, \}$
1.5 Symmetric Difference: A △ B
$$A \triangle B = (A – B) \cup (B – A) $$
Elements in exactly one of $A$ or $B$ — not in both. Equivalently, $A \triangle B = (A \cup B) − (A \cap B)$.
Example: integers that are even or divisible by 3, but not both — excludes multiples of 6 entirely.
1.6 Complement: Aᶜ
$$A^c = \{ x \notin A \}$$ Elements that do not belong to A; does not satisfy the properties of $A$. The complement depends entirely on what the reference or universal set $U$ is.
- if $U = ℤ, A = $even integers then $A^c =$ odd integers
- if $U = $ First ten natural numbers, and $A = \{1,3,5,7,9\}$ then $A^c= \{2,4,6,8,10\}$
Key identities: $A \cup A^c = U, A \cap A^c = \phi, (A^c)^c = A$
1.7 Power Set: 𝒫(A)
$$\mathcal{P}(A) = \{ S : S \subseteq A \}$$
The set of all subsets of A.
- If $|A| = n$ then $|\mathcal{P}(A)| = 2^n$
- $\phi \in \mathcal{P}(A)$ always
- $A \in \mathcal{P}(A)$ always
1.8 Cartesian Product: A × B
$$A \times B = \{ (a, b) : a \in A,\ b \in B \}$$
All ordered pairs where the first element comes from A and the second from B. Order matters: (a, b) ≠ (b, a) in general, so A × B ≠ B × A unless A = B.
It can be noted that cardinality is |A × B| = |A| · |B|.
Example: {0,1} × {0,1} = { (0,0), (0,1), (1,0), (1,1) } .
Relation Between Set Operations and Logic
Set operations are built using one or more logical connectives. In the definitions of union, intersection, difference, and complement given above, the conditions are joined precisely using “or”, “and”, and “not”. Every operation on sets can be traced back to the basic connectives of logic. In the logic system “or” can be used in two different ways – inclusive and exclusive.
Inclusive: $A \cup B$, $A$ or $B$ or both. Means, elements of $A \cup B$ satisfy the property of $A$ or $B$ or both. Either …Or is usually used in this sense
Exclusive: $A \cap B^c \cup A^c \cap B$, $A$ or $B$ but not both. Means, elements of $A \cup B$ satisfy the property of $A$ or $B$ but not both, simultaneously. In formally “Only one” can be thought of exclusive OR
On the other hand $A \cap B$ makes the condition more stringent that its elements should satisfy the properties of $A$ and $B$, a bit restrictive
Another day-to-day usage of logic “neither…nor” too has equivalent set operation, $A^c \cap B^c$
Here are some sentences that may help to note the usage of logical connectors
- You can have soup or salad with your meal.
- The interview is at 10 AM or 11 AM, depending on the slot they assign you.
- She speaks French or German.
- The number you pick must be even or odd.
- I’ll wear the blue shirt or the white shirt today.
- The switch is either on or off.
- I prefer coffee or tea
- I will play cricket or foot ball between 4 and 6 PM tomorrow
- You’ll find me at the gym or the library most evenings.
- The package will arrive either today or tomorrow.
- Neither the manager nor the intern showed up for the meeting.
- You can pay by card or cash at checkout.
- He’s not particularly tall, nor is he especially short.
- Either you finish the report, or someone else will have to.
- The flight gets delayed or cancelled when the weather turns bad.
- Neither the AC nor the fan was working in that room.
- You can take the stairs or the elevator to the fourth floor.
- The password must contain a number or a special character.
- Either the milk has gone bad, or the fridge isn’t cooling properly.
- Neither tea nor coffee was available at the counter that morning.
A Note on Number Systems – Real Numbers
We have set of real numbers, one of the predominant number systems that is defined as $\mathbb{R} = \mathbb{Q} \cup \mathbb{S}$ so that it can be understood that$\mathbb{R} – \mathbb{Q} = \mathbb{S}$
Cartesian product $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ is called set of all 2-tuples or a 2-dimensional element, ordered pairs of real numbers. Similarly n-tuple (n-dimensional element) is $\mathbb{R} \times \mathbb{R} \cdots \cdots \times \mathbb{R} = \mathbb{R}^n$
Also, note that
- Rationals: decimal expansion either terminates (0.5) or repeats (0.333…)
- Irrationals: decimal expansion is non-terminating and non-repeating (π = 3.14159…)
2. Functions
Consider two sets $A$ and $B$, whose elements may be numbers or any objects. Let us suppose that for each element $x$ of $A$, there is associated an element of $B$. For example, for every natural number $n \in \mathbb{N}$ let us associate $\frac{1}{n}$ in $\mathbb{R}$; for every vehicle we may associate its registration number etc. Such association may be naturally bounded by a relation or rule in one or some manner. This idea can be understood as function or mapping from the set $A$ into the set $B$
Formally, $f: A \rightarrow B$ represents a function from $A$ into $B$
- The set $A$ is called the domain of $f$, or we say $f$ is defined on $A$
- The set of all elements $f(x) / x \in A$ is called values of $f$
- The set of all values of $f$ is called the range of $f$
- A function $f: A \to B$ maps every element of the domain $A$ to exactly one element in the codomain $B$.
Example:
- $f: \mathbb{N} \to \mathbb{N}$ as $f(n) = n+1$
- $g: \mathbb{Q}-\{1\} \to \mathbb{R}$ as $g(x) = \frac{1}{(x+1)}$
- $f: \mathbb{R} \to \mathbb{R}$ as $f(x) = \begin {cases} x & x \ge 0 \\ -x & x < 0 \end{cases} $
- Let $A$ be the first 100 words in a dictionary of any language; we define, $f: A \to \mathbb{N}$ as $f(a_i)=$ Length of the word $a_i$ where $i = 1, 2 \cdots \cdots 100$
- Let $A$ and $B$ be two sets and $A \subset B$. Define $f:A \to B$ as $f(x) = x, \forall x \in A$
- Same as (5) but another function $g$ defined as $g:A \to B$ as $g(a) = b, \forall a \in A$ for some $b \in B$
Some Definitions: Let $A$ and $B$ be two sets and let $f$ be a mapping of $A$ into $B$. If $A_1$ is a set such that $A_1 \subset A$, then $f(A_1)$ is defined to be the set of all elements of $f(x)$, for all $x \in A_1$. Then $f(A_1)$ is the image of $A_1$ under $f$. In the similar spirit, we can say $f(A)$ is the range of $f$. Also it can be understood that $f(A) \subset B$. These ideas from set to functions will help us to define some characteristics of functions
2.1 One-to-One (Injective)
A mapping $f$ is one-to-one (or 1-1) of $A$ into $B$ when distinct elements of $A$ are mapped into distinct elements of $B$. that is $f(x_1) = f(x_2) \implies x_1 = x_2$ or $x_1 \ne x_2 \implies f(x_1) \ne f(x_2)$ whenever, both $x_1,x_2 \in A$
Examples
$f: \mathbb{R} \to \mathbb{R}$ such that $f(x) = x$ is 1-1
$g: \mathbb{R} \to \mathbb{R}$ such that $g(x) = x^2$ is not 1-1
$h: \mathbb{N} \to \mathbb{R}$ such that $h(n) = n^2$ is 1-1
Earlier we have seen that the image $f(D)$ of a set $D \subset A$ under the mapping $f: A \to B$ is always a subset of $B$, that is $f(D) \subset B$. This leads to another class of functions
2.2 Onto (Surjective)
A mapping $f: A \to B$ is said to be onto if $f(A) = B$. We say that $f$ maps $A$ onto $B$. This can also be stated as $\forall\, b \in B,\ \exists\, a \in A \text{ such that } f(a) = b$
Examples
$f: \mathbb{N} \to \mathbb{N}$ as $f(n) = n+1$ is not onto
$f: \mathbb{R} \to \mathbb{R}$ such that $f(x) = x$ is onto
$g: \mathbb{R} \to \mathbb{R}$ such that $g(x) = x^2$ is not onto
$h: \mathbb{R} \to \mathbb{R}^+$ such that $h(x) = x^2$ is onto
2.3 Bijective (One-to-One and Onto)
A function $f: A \to B$ is bijective if it is both injective and surjective; that is $f$ is a 1-1 mapping of $A$ onto $B$
For example, $f(x) = 2x + 3$ in $\mathbb{R} \to \mathbb{R}$ such that $f(x) = 2x + 3$ is a bijective mapping
2.4. Inverse Image and Inverse Function
If $E \subset B$ then we define $f^{-1}(E)$ as the set of all $x \in A$ such that $f(x) \in E$. The set $f^{-1}(E)$ is called the inverse image of $E$ under $f$. In a similar way, if $y \in B, f^{-1}$ is the set of all $x \in A$ such that $f(x) = y$. Also, for each $y \in B$ if $f^{-1}(y)$ consists of at most one element of $A$, then $f$ is 1-1
Hence, a function $f$ has an inverse $f^{-1}$ if and only if $f$ is bijective and we can write $f^{-1}: B \to A \quad \text{such that} \quad f^{-1}(y) = x$ where $y=f(x)$
3. Types of Sets
Infinite Set. Let $A$ be a set. If for every $n \in \mathbb{N}$, there exists a subset $S \subseteq A$ with $|S| = n$, then $A$ is infinite.
A set which is not an infinite set is called a finite set. That is, A is finite ⟺ ∃ n ∈ ℕ such that |A| = n
A set is countable if it is finite or can be put into a one-to-one correspondence with $\mathbb{N}$ (positive integers). Hence, the elements of $A$ can be indexed as the first element, second element, and so on. Therefore, $A$ can be written as: $A = \{a_1, a_2, a_3, \ldots\}$.
For example, the natural numbers ℕ = {0, 1, 2, 3, …}, the integers ℤ = {…, −2, −1, 0, 1, 2, …}, and the rationals ℚ = { p/q : p, q ∈ ℤ, q ≠ 0 } are all countably infinite.
A set $A$ is uncountable if there is no one-to-one mapping between $A$ and $\mathbb{N}$. An uncountably infinite set cannot be matched with ℕ. That is, $A$ is uncountable $\iff$ $A$ is not countable. For example, the set of all real number $\mathbb{R}$ is uncountable
3.1 Notable form of subsets in $\mathbb{R}$
For any $a, b \in \mathbb{R} $, we define an Interval on the order property of real numbers.
- Open intervals: $(a, b) = \{x \in \mathbb{R} / a < x < b\} $
- Closed intervals: $[a, b] = \{x \in \mathbb{R} / a \le x \le b\} $
- Half intervals: $(a, b] = \{x \in \mathbb{R} / a < x \le b\} $ or $[a, b) = \{x \in \mathbb{R} / a \le x < b\} $
In general, $a$ is called Lower (left) Limit and $b$ is called Upper (right) Limit of the interval; also, these intervals are uncountable. However, this can be a finite or countable set if the domain is chosen accordingly; for example, for any $a, b \in \mathbb{R}, (a, b) = \{x \in \mathbb{N} / a < x < b\} $ may be finite or an empty set
3.2 The Extended Real Number System
If the real number set $\mathbb{R}$ consists of two symbols $+ \infty$ and $- \infty$ and we can write the set of all real numbers in this extended system as $\{x / -\infty < x <+\infty\} = (-\infty, +\infty)$. Also it may be noted that, if $x \in \mathbb{R}$ then,
- $x+ \infty = +\infty$
- $x – \infty = -\infty$
- $\frac{x}{-\infty}=\frac{x}{+\infty}=0$
- If $x > 0$ then $x (+\infty) = +\infty, x (-\infty) = -\infty$
- If $x < 0$ then $x (+\infty) = -\infty, x (-\infty) = +\infty$
In this case, our earlier defined set $(a, b) = \{x \in \mathbb{N} / a < x < b\} $ can be countably infinite.
It is worth to note that interval $(a,b)$ is called finite / bounded interval when $a, b \in \mathbb{R}$ but not $+\infty$ or $-\infty$. In case, if $a=-\infty$ or $b=+\infty$ then the interval is called infinite / unbounded interval
4. Universal and Empty Set Identities
- A ∪ ∅ = A — union with empty adds nothing
- A ∩ ∅ = ∅ — intersection with empty is empty
- A ∪ U = U — union with universal is universal
- A ∩ U = A — intersection with universal is A
- A − ∅ = A — removing nothing changes nothing
- ∅ − A = ∅ — nothing minus anything is still nothing
- ∅ ⊆ A — the empty set is a subset of every set
- A ∩ Aᶜ = ∅ — a set and its complement are disjoint
- A ∪ Aᶜ = U — a set and its complement cover everything
- DeMorgan’s Laws: $(A \cup B)^c = A^c \cap B^c$; $(A \cap B)^c = A^c \cup B^c$
5. Set Algebra Laws
- Idempotent: A ∪ A = A, and A ∩ A = A.
- Identity: A ∪ ∅ = A, and A ∩ U = A.
- Domination: A ∪ U = U, and A ∩ ∅ = ∅.
- Complement: A ∪ Aᶜ = U, and A ∩ Aᶜ = ∅.
- Double Complement: (Aᶜ)ᶜ = A.
- Commutativity: A ∪ B = B ∪ A, and A ∩ B = B ∩ A.
- Associativity: (A ∪ B) ∪ C = A ∪ (B ∪ C), and (A ∩ B) ∩ C = A ∩ (B ∩ C).
- Distributivity: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
- De Morgan: (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ, and (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.
- Absorption: A ∪ (A ∩ B) = A, and A ∩ (A ∪ B) = A.