discrete mathematics chapter 2 sets

Set is the one of the most fundamental concepts in mathematics today. Set theory is created by a single individual: Georg Cantor.

Set: a collection of objects with a certain common property.

Element: an object belonging to a set. Such as $A = lbrace 1, 2, 3 rbrace$, and we say $1 in A$. But an element $4 notin A$.

Equal Set: $A = B$, which means that $A$ and $B$ consist of exactly the same elements, such that $A = lbrace x, y, z rbrace$ and $B = lbrace y, z, x rbrace$. The orders do not matter in the equal relationship.

Subset: A set $X$ is called a subset of a set $Y$, written $X subseteq Y$. If every element of $A$ also belongs to $B$. For example, $Bbb N subseteq Bbb Z$, $Bbb Z subseteq Bbb Q$ and $Bbb Q subseteq Bbb R$. However, if $X$ is not a subset of $B$, then we write $X nsubseteq Y$. If $X nsubseteq Y$, then there is some elements of $X$ that does not belong to $Y$. And for every set, the empty set $emptyset$ is always a subset.

Proper Subset: $A subset B$: $A$ is a subset of $B$ and $A ne B$.

Empty Set: denoted by $emptyset$ and $emptyset = lbrace rbrace$, is the set containing no elements.

Nonempty Set: the set that contains at least one element.

University Set: the set containing all objects under consideration.

Cardinality: denoted by $|A|$, is the number of elements in $A$. For example, $A = lbrace x, y, z rbrace$ has cardinality 3 and so $|A| = 3$. This implies $A$ must be a finite set, which means the elements of $A$ are finite numbers.

Power Set: $mathcal P(A)$, the set of all subsets of a set $A$ is called power set of $A$. Such that if $A$ is a set with $|A| = n$, where n is a nonnegative integer, then $|mathcal P(A)| = 2^n$.

Nature Numbers: denoted by $Bbb N$, is the set of natural numbers (positive integers).

Integers: denoted by $Bbb Z$, is the set of integers (both positive and negative).

Rational numbers: denote by $Bbb Q$, is the set of rational numbers (fraction), which means the ratio $a/b$ of two integers $a$ and $b$.

Irrational numbers: the real number that is not rational, such as $sqrt 2$ and $pi$.

Real numbers, denoted by $Bbb R$, is the set of real numbers, which consists of the rational numbers and irrational numbers.

Venn Diagram: a diagram that proctorially represent a set or sets under consideration.

Intersection: $A cap B$, the set of all elements belonging to both $A$ and $B$, $A cap B = lbrace x: x in A ; and ; x in B rbrace$. For $n ge 2$, $A_1, A_2, …, A_n$, the intersection of these sets is
$$
begin{equation}
bigcap_{i=1}^n A_i = A_1 cap A_2 cap … cap A_n = lbrace x: x in A_i ; for ; every ; i ; with ; 1 le i le n rbrace
end{equation}
$$

Union: $A cup B$, the set of all elements belonging to at least one of $A$ and $B$. $A cup B = lbrace x: x in A ; or ; x in B rbrace$. For $n ge 2$, $A_1, A_2, …, A_n$, the union of these sets is
$$
begin{equation}
bigcup_{i = 1}^n A_i = A_1 cup A_2 cup … cup A_n = lbrace x: x in A_i ; for ; some; i ; with ; 1 le i le n rbrace
end{equation}
$$

Commutative Laws: $A cap B = B cap A$ and $A cup B = B cup A$.

Associative Laws: $(A cap B) cap C = A cap (B cap C)$ and $(A cup B) cup C = A cup (B cup C)$.

Distributive Laws: $A cap (B cup C) = (A cap B) cup (A cap C)$ and $A cup (B cap C) = (A cup B) cap (A cup C)$.

Disjoint Sets: two sets having no elements in common ($A cap B = emptyset$). For example, $A = lbrace x, y, z rbrace$ and $B = lbrace a, b, c rbrace$ are disjoint.

Pairwise Disjoint Sets: a collection of sets such that every two distinct sets are disjoint. For example, $A = lbrace a, b, c rbrace$, $B = lbrace x, y rbrace$ and $C = lbrace z rbrace$ are pairwise disjoint science every two of the sets $A, B$ and $C$ are disjoint.

Difference: $A - B$, the set of all elements belonging to $A$ but not to B. $A - B = lbrace x: x in A ; and ; x notin B rbrace$.

Symmetric Difference: $A oplus B$, the set of elements belonging to $A$ or $B$ but not to both. $A oplus B = (A - B) cup (B - A)$.

Complement: $overline{A}$, the set of all elements (in the universal set) not belonging to $A$. $overline{A} = lbrace x in U : x notin A rbrace = U - A$.

De Morgan’s Laws: $overline{A cup B} = overline{A} cap overline{B}$ and $overline{A cap B} = overline{A} cup overline{B}$.

Cartesian (cross) Product: $A times B$ of $A$ and $B$ is the set of all ordered pairs whose first coordinate belongs to $A$ and whose second coordinate belongs to $B$. $A times B = lbrace (a, b): a in A ; and ; b in B rbrace$. For example, we have the sets $A = lbrace 0, 1 rbrace$ and $B = lbrace emptyset, lbrace 1 rbrace, 2 rbrace$, so $A times B = lbrace (0, emptyset), (0, lbrace 1 rbrace), (0, 2), (1, emptyset), (1, lbrace 1 rbrace), (1, 2) rbrace$. Additionally, the Cartesian product of the $n$ sets $A_1, A_2, …, A_n$, denoted by $A_1 times A_2 times … times A_n$, the set of ordered $n$-tuples ($a_1, a_2, …, a_n$), where $a_i in A_i$ for $1 le i le n$.

Partition: a collecting nonempty subsets which are mutually disjointed and cover the entire set. For example, the set $A = lbrace 1, 2, …, 10 rbrace$ and the subsets $S_1 = lbrace 1, 7, 8 rbrace$, $S_2 = lbrace 2, 4, 9 rbrace$, $S_3 = lbrace 3 rbrace$, $S_4 = lbrace 5, 6, 10 rbrace$ of $A$, the set $mathcal P(S_1, S_2, S_3, S_4)$ is a partition of $A$.