Let $C$ be a set of sets defined as follows,

Question

I'm in Theory of Computation, I've already taken Set Theory so I'm familiar with the terminology but this question is not making sense to me.

Let $C$ be a set of sets defined as follows:

1. $\emptyset\in C$

2. If $S_1\in C$ and $S_2\in C$ then $\{S_1, S_2\}\in C$.

3. If $S_1\in C$ and $S_2\in C$ then $S_1\times S_2\in C$.

4. Nothing is in $C$ except that which follows from (1), (2), and (3).

b) Give an example of a set $S$ of ordered pairs such that $S\in C$, and $|S|>1$

c) Does $C$ contain any infinite sets?

d) Is $C$ countable or uncountable?

I'm not looking for an answer, just a way of understanding what exactly is going on and a way to find the answer would be a lifesaver!

Thank you!

Answer 1

According to 1 and 2, the set $\{\emptyset,\emptyset\} = \{\emptyset\}$ is in $C$ (taking $S_1=S_2=\emptyset$). Note this is not the empty set, for it's not empty.

According again to 1 and 2 and the fact we just proved, the set $s:=\{\emptyset, \{\emptyset\}\}$ is in the set. (Taking $S_1=\emptyset$, $S_2=\{\emptyset\}$).

According to 3, taking $S_1=S_2=s$, we have $t:=\{(\emptyset,\emptyset),(\emptyset,\{\emptyset\}),(\{\emptyset\},\emptyset),(\{\emptyset\},\{\emptyset\})\}$ in the set. Note the round parentheses, meaning ordered pairs, introduced by the Cartesian product.

Answer 2

Here, we will see that the set, $C$ is countable and contains only finite sets. To do this we will construct a sequence of sets, $$C_0\subset C_1\subset C_2\cdots$$ such that $C_0=\emptyset$ and $\bigcup_{n\geq 0} C_n=C$. We define these sets inductively. Suppose that $C_n$ has been constructed. Since we are only able to construct only those things that follow from (1), (2), and (3), we construct the set $C_{n+1}$ as follows: for any pair of sets in $C_n$, $X,Y$, we form two new sets, $\{X,Y\}$, and $X\times Y$ (some of theses sets may have been constructed already, but we do get some new sets). Thus we set $$C_{n+1}=\{\{X,Y\}:X,Y\in C_n\}\cup\{X\times Y:X,Y\in C_n\}.$$ Note that $C_{n+1}$ are exactly the elements that follow directly from the construction rules and $C_n$. Thus the union over all $C_n$ is the desired set, $C$.

We will now prove that each set, $C_n$ is finite, by induction. Note that $C_0$ is finite since it just contains the empty set. Now if $C_n$ is finite, so are the sets $\{\{X,Y\}:X,Y\in C_n\}$, and $\{X\times Y:X,Y\in C_n\}$, we construct two elements for each pair of elements from $C_n$. But since the countable union of countable sets is countable, the set, $C$ is countable.

We will likewise prove that each element of $C$ is finite, again by induction. Note that the only element of $C_0$ is the empty set, so it is finite. Now suppose that all elements of $C_n$ are finite. We now show that all elements of $C_{n+1}$ are finite.Let $X,Y\in C_n$. But all elements of the form, $\{X,Y\}$ have cardinality two ,and all elements of the from of the form $X\times Y$ have cardinality $|X|\times |Y|$ but by induction since $X$ and $Y$ have finite cardinality, so does, $X\times Y$.