Set Theory: Foundations, Operations, and Cartesian Products

Flashcards covering definitions, set notations, special sets, subset properties, cardinality, power sets, fundamental set operations, inclusion-exclusion principle, Cartesian products, and set identities based on Set Theory lecture parts 1 and 2 by Dr. Shihan Miah.

What are the date, duration, question count, and topics for the Mid-Term Test described in the lecture?

The test takes place in Week 6 (Monday 2nd Nov & Wednesday 4th Nov), lasts $60$ minutes, contains $20$ questions, and covers Logic & Set Theory.

What is the formal definition of a set?

A set is a well-defined collection of distinct objects.

In the roster method of defining sets, what rules apply to element ordering and repetition?

Order does not matter (e.g., $\{a, b, c\} = \{c, b, a\}$) and there is no repetition (e.g., $\{a, b, c\} = \{a, a, b, b, c, c\}$).

What is the formal structure of set-builder notation $S = \{x \mid P(x)\}$?

It specifies that $S$ contains all elements $x$ for which property $P(x)$ is true.

What chain of subset relationships connects the standard number sets: natural numbers ($\mathbb{N}$), integers ($\mathbb{Z}$), rational numbers ($\mathbb{Q}$), real numbers ($\mathbb{R}$), and complex numbers ($\mathbb{C}$)?

$\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$, where each set properly contains the previous set.

How is the empty set $\emptyset$ defined in set-builder notation?

$\emptyset = \{x \mid x \neq x\} = \{x \mid \text{False}\} = \{\}$.

What is the difference between the empty set $\emptyset$ and the set containing the empty set $\{\emptyset\}$?

$\emptyset$ has cardinality $0$ (contains no elements), while $\{\emptyset\}$ is a singleton set of cardinality $1$ whose single element is the empty set ($\emptyset \in \{\emptyset\}$ and $\emptyset \subset \{\emptyset\}$).

What is the distinction between a subset ($A \subseteq B$) and a proper subset ($A \subset B$)?

$A \subseteq B$ means every element of $A$ is in $B$. $A \subset B$ means $A \subseteq B$ and $A \neq B$.

What are the four fundamental subset properties stated in the Subset Properties Theorem?

1. Reflexivity: $A \subseteq A$
2. Transitivity: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$
3. Empty set: $\emptyset \subseteq A$ for every set $A$
4. Antisymmetry: If $A \subseteq B$ and $B \subseteq A$, then $A = B$

How do you prove that if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$?

Let $x \in A$. Since $A \subseteq B$, $x \in B$. Since $B \subseteq C$, $x \in C$. Therefore, every element of $A$ is in $C$, which shows $A \subseteq C$.

What is the cardinality of a set $S$, denoted $|S|$?

The cardinality $|S|$ is the number of distinct elements in $S$.

What does Cantor's Theorem state regarding the cardinality of any set $A$ and its power set $\mathcal{P}(A)$?

It states that $|\mathcal{P}(A)| > |A|$ for any set $A$.

What is the definition of the power set $\mathcal{P}(A)$, and what is its cardinality if $|A| = n$?

$\mathcal{P}(A) = \{X \mid X \subseteq A\}$. If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.

What is the general formula for the cardinality of the nested power set $|\mathcal{P}(\mathcal{P}(A))|$ when $|A| = n$?

$|\mathcal{P}(\mathcal{P}(A))| = 2^{2^n}$. For example, if $n = 3$, $|\mathcal{P}(\mathcal{P}(A))| = 2^8 = 256$, and if $n = 4$, $|\mathcal{P}(\mathcal{P}(A))| = 2^{16} = 65{,}536$.

How is set union ($A \cup B$) defined formally, and to which logical operator does it correspond?

$A \cup B = \{x \mid x \in A \text{ or } x \in B\}$, which corresponds directly to the logical OR ($\lor$) operator.

How is set intersection ($A \cap B$) defined formally, and to which logical operator does it correspond?

$A \cap B = \{x \mid x \in A \text{ and } x \in B\}$, which corresponds directly to the logical AND ($\land$) operator.

How is the set difference ($A - B$) defined formally?

$A - B = \{x \mid x \in A \text{ and } x \notin B\}$, representing elements in $A$ but not in $B$. Note that $A - B \neq B - A$.

How is the complement of a set $A$ (denoted $\overline{A}$) defined, and what must be specified to evaluate it?

$\overline{A} = U - A = \{x \in U \mid x \notin A\}$. It requires explicitly specifying the universal set $U$.

What does it mean for two sets $A$ and $B$ to be disjoint?

Sets $A$ and $B$ are disjoint if they share no common elements, meaning $A \cap B = \emptyset$.

What is the formula for the Inclusion–Exclusion Principle for two finite sets $A$ and $B$?

$|A \cup B| = |A| + |B| - |A \cap B|$.

What is the formula for the Inclusion–Exclusion Principle for three finite sets $A$, $B$, and $C$?

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.

What is the formal definition of the Cartesian product $A \times B$?

$A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$, which is the set of all ordered pairs where the first element is from $A$ and the second element is from $B$.

What is the Cardinality Rule for the Cartesian product of two finite sets $A$ and $B$ where $|A| = m$ and $|B| = n$?

$|A \times B| = m \times n$.

What is the result of taking the Cartesian product of any set $A$ with the empty set $\emptyset$?

$A \times \emptyset = \emptyset$ and $\emptyset \times A = \emptyset$, because there are no elements in $\emptyset$ to form ordered pairs.

What are the Identity Laws and Domination Laws for set operations?

Identity Laws: $A \cup \emptyset = A$ and $A \cap U = A$. Domination Laws: $A \cup U = U$ and $A \cap \emptyset = \emptyset$.

What are De Morgan's Laws for sets?

$\overline{A \cup B} = \overline{A} \cap \overline{B}$ (the complement of the union is the intersection of the complements) and $\overline{A \cap B} = \overline{A} \cup \overline{B}$ (the complement of the intersection is the union of the complements).