- Which of these are correct (one, both, or neither)? Discuss.\begin{align*} 2\subseteq \{1,2,3\}\amp \amp 2\in \{1,2,3\} \end{align*}
- Which of these are correct (one, both, or neither)? Discuss.\begin{align*} \emptyset\subseteq \{1,2,3\} \amp \amp \emptyset \in \{1,2,3\} \end{align*}
- Are any of the following things the same? Discuss.\begin{align*} \{0\}\amp \amp \{\emptyset\} \amp \amp \emptyset \amp \amp \{ \} \end{align*}
Section 1.1 Sets
A set is a collection of objects called the elements or members of the set. Given an object \(x\) and a set \(A\text{,}\) exactly one of two things is true: either \(x\) is an element of \(A\text{,}\) denoted \(x\in
A\), or \(x\) is not an element of \(A\text{,}\) denoted \(x\not
\in A\). Two sets are equal if they contain exactly the same elements.
To denote a set that contains a small number of elements, we list the elements, separated by commas, and enclosed in curly brackets "\(\{\ldots\}\)". For example, the set \(A=\{x,y,z\}\) contains elements \(x,y,z\text{,}\) and contains no other objects. In this notation, the order in which the objects are listed does not matter. Redundancy also does not matter: the same object may be listed more than once. For example, we may write
\begin{equation*}
A=\{x,y,z\}=\{y,z,x\}=\{y,x,y,z\}.
\end{equation*}
Another way to denote a set is the notation \(\{x\colon x \text{ satisfies condition } C\}\text{,}\) where the colon ":" is pronounced "such that". For example, the closed unit interval of the real numbers \(\R\) is the set \(\{x\in \R \colon 0\leq x\leq 1\}\text{.}\)
The set that contains no elements is called the empty set, denoted \(\emptyset\).
We say that \(A\) is a subset of \(B\text{,}\) denoted \(A\subseteq B\), if every element in the set \(A\) is also in the set \(B\text{,}\) and we write \(A\not\subseteq
B\) to indicate that there is at least one element in \(A\) that is not an element in \(B\text{.}\) A consequence of these definitions is that if \(A=B\text{,}\) then \(A\subseteq B\) and \(B\subseteq
A\text{.}\) Conversely, if \(A\subseteq B\) and \(B\subseteq A\text{,}\) then \(A=B\text{.}\) Another consequence is that the empty set is a subset of any given set \(A\) because there is no element in \(\emptyset\) that is not in \(A\text{.}\)
Checkpoint 1.1.1.
The intersection of sets \(A,B\text{,}\) denoted \(A\cap B\), is the set
\begin{equation*}
A\cap B =\{x\colon x\in A \text{ and } x\in B\}.
\end{equation*}
The union of sets \(A,B\text{,}\) denoted \(A\cup
B\), is the set
\begin{equation*}
A\cup B =\{x\colon x\in A \text{ or } x\in B\}
\end{equation*}
where the word "or" means "one or the other or both". The set
\begin{equation*}
A\setminus B =\{x\colon x\in A \text{ and } x\not \in B\}
\end{equation*}
(also sometimes denoted \(A-B\)) is called the difference of set \(A\) minus set \(B\), or just \(\text{"}\!A\) minus \(B\text{"}\) for short.
Checkpoint 1.1.2.
Let \(A,B\) be sets, and let \(R=A\cap B\text{,}\) \(S=A\cup
B\text{,}\) \(T=A\setminus B\text{,}\) and \(U=B\setminus A\text{.}\)
- Give an example for which \(R,S,T,U\) are four different sets.
- Give an example for which \(R,S,T,U\) are exactly two different sets.
- Give an example for which \(R,S,T,U\) are all the same set.
Exercises Exercises
1.
One of the following statements is always true, and the other statement is sometimes true, and sometimes false. Determine which is which. Demonstrate the "sometimes true" statement by giving two specific examples — one example for which the statement is true, and one example for which the statement is false. "Specific" means that you will write all of the sets \(S,A,B\) as lists of elements inside curly brackets, and write both of the sets on the left side and on the right sides of the equation as lists of elements in curly brackets.
- For any subsets \(A,B\) of of a set \(S\text{,}\) we have \(S\setminus (A \cap B) = (S\setminus A) \cap (S\setminus B)\text{.}\)
- For any three subsets \(A,B\) of a set \(S\text{,}\) we have \(S\setminus (A\cap B) = (S\setminus A)\cup (S\setminus B)\text{.}\)
2.
Given a set \(A\text{,}\) the power set of \(A\text{,}\) denoted \({\mathcal
P}(A)\), is defined to be the set of all subsets of \(A\text{.}\)
- Explain why \(\emptyset \in \mathcal{P}(A)\) for any set \(A\text{.}\)
- Write out \(\mathcal{P}(\{a,b\})\) with all of its elements.
- Write out \(\mathcal{P}(\{a,b,c\})\) with all of its elements.
3.
Let \(S\) be a set. An algebra of subsets of \(S\) is a set \({\mathcal A}\) whose elements are subsets of \(S\) for which the following properties hold.
- One algebra of subsets of \(S=\{a,b\}\) is the power set \(\mathcal{P}(S)\) of \(S\text{.}\) Are there any other algebras of subsets of \(S\text{?}\)
- Find all possible algebras of subsets of \(\{a,b,c\}\text{.}\)
- Give an example of a collection of subsets of some set \(S\) for which exactly three of the four set algebra properties hold.
4.
A hypergraph is a pair of sets \((V,E)\text{,}\) where \(V\) is a set and \(E\) is a set of nonempty subsets of \(V\text{.}\) Write out all of the hypergraphs \((V,E)\) for \(V=\{a,b\}\text{.}\)
