About this module¶
-
Prerequisites: Basic Set Notations, Quantifiers
-
Objectives: Set theory using quantifiers
Rationale¶
Although basic set theory was already discussed in module Basic Set Notations, that was discussed without the use of quantifiers. Quantifiers are useful tools for a variety of math topics, set theory is a part of those topics. By reexamining basic set theory, we reinforce the understanding of both set theory and quantifiers.
Equality¶
Given two items, $x$ and $y$, how do we know they are the same? In order words, how do we evaluate $x=y$?
First of all, if one is a set and the other is not, then $x=y$ is false.
Given that $x$ and $y$ are not sets, then the "normal" comparison applies.
Given that $x$ and $y$ are sets, then we can say the following:
$(x=y) \Leftrightarrow ((\forall e \in x(e \in y)) \wedge (\forall e \in y(e \in x)))$
There is a more concise statement that states the same:
$(x=y) \Leftrightarrow (\forall e((e \in x) \Leftrightarrow (e \in y)))$
Set description¶
Recall the notation $E=\{x|P(x)\}$ describes a set $E$ where all its elements make the predicate $P$ true. We mentioned how this means $x \in E \Leftrightarrow P(x)$ in module Basic Set Notations. The more correct statement is as follows:
$\forall x(x \in E \Leftrightarrow P(x))$
This makes it clear where we get (how we bind) the value of the variable to some "thing." $x$ can be anything in the universe! Without the quantifier $\forall$, one can ask where do we get a value for $x$ to be evaluated.
The empty set¶
How do we know that a set $S$ is empty?
$\neg \exists x(x \in S)$
This literally says "there does not exist a thing $x$ such that $x$ is in $S$."
Intersection and Union¶
$\forall x((x \in (A \cap B)) \Leftrightarrow (x \in A \wedge x \in B))$
and
$\forall x((x \in (A \cup B)) \Leftrightarrow (x \in A \vee x \in B))$
Cartesian product¶
$\forall x \in A(\forall y \in B((x,y) \in (A \times B))) \wedge \forall (x,y) \in A \times B(x \in A \wedge y \in B)$
Subset¶
$A \subseteq B \Leftrightarrow \forall e \in A(e \in B)$
$A \subset B \Leftrightarrow (A \subseteq B \wedge \exists x \in B(\neg x \in A))$
AI-generated questions¶
1. What does it mean for two sets $A$ and $B$ to be equal?
Two sets $A$ and $B$ are equal if every element of $A$ is an element of $B$ and every element of $B$ is an element of $A$. In formal terms:
$$A = B \Leftrightarrow \forall e \in A(e \in B) \wedge \forall e \in B(e \in A)$$
2. How can you express the empty set using quantifiers?
The empty set $S$ can be expressed using quantifiers as follows:
$$\neg \exists x(x \in S)$$
This means that there does not exist any element $x$ such that $x$ is in $S$.
3. How do you represent the intersection of two sets $A$ and $B$ using quantifiers?
The intersection of two sets $A$ and $B$ can be represented using quantifiers as:
$$\forall x((x \in (A \cap B)) \Leftrightarrow (x \in A \wedge x \in B))$$
4. How do you represent the union of two sets $A$ and $B$ using quantifiers?
The union of two sets $A$ and $B$ can be represented using quantifiers as:
$$\forall x((x \in (A \cup B)) \Leftrightarrow (x \in A \vee x \in B))$$
5. What does $A \subseteq B$ mean in terms of quantifiers?
The statement $A \subseteq B$ means that every element of $A$ is also an element of $B$, and can be expressed as:
$$A \subseteq B \Leftrightarrow \forall e \in A(e \in B)$$
6. What does $A \subset B$ mean in terms of quantifiers?
The statement $A \subset B$ means that $A$ is a subset of $B$ but $A$ is not equal to $B$. It can be expressed as:
$$A \subset B \Leftrightarrow (A \subseteq B \wedge \exists x \in B(\neg x \in A))$$
7. How can you describe a set $E$ using quantifiers if the set is defined by a predicate $P(x)$?
If a set $E$ is defined by a predicate $P(x)$, you can describe the set using quantifiers as:
$$\forall x(x \in E \Leftrightarrow P(x))$$
8. How is the Cartesian product $A \times B$ defined using quantifiers?
The Cartesian product of two sets $A$ and $B$ can be defined using quantifiers as:
$$\forall x \in A(\forall y \in B((x,y) \in (A \times B))) \wedge \forall (x,y) \in A \times B(x \in A \wedge y \in B)$$
9. What does the statement $x \in E \Leftrightarrow P(x)$ mean in terms of set notation and quantifiers?
The statement $x \in E \Leftrightarrow P(x)$ implies that $E$ is the set of all $x$ such that $P(x)$ is true, and can be formally written as:
$$E = \{x | P(x)\}$$
In quantifier form: $$\forall x(x \in E \Leftrightarrow P(x))$$
10. How would you express the equality of two sets $A$ and $B$ using a single quantifier expression?
The equality of two sets $A$ and $B$ can be expressed concisely with the following quantifier expression:
$$A = B \Leftrightarrow \forall e((e \in A) \Leftrightarrow (e \in B))$$