PS1, Part 1: Set Theory

Problem One: Much Ado About Nothing

It can take a bit of practice to get used to the empty set. This problem will ask you to think about a few different sets related to $\emptyset$.

Answer each part of this question by editing the file MuchAdoAboutNothing.sets in the res/ directory of the starter files. There’s information in the top of each of the files about how to represent sets; most importantly, note that to write out the empty set, you should write {} rather than using the empty-set symbol. For example, the set $\Set{\emptyset}$ would be written as { { } }.

Give a set equal to $\emptyset \cup \Set{\emptyset}$.

Give a set equal to $\emptyset \cap \Set{\emptyset}$.

Give a set equal to $\Set{\emptyset} \cup \Set{\Set{\emptyset}}$.

Give a set equal to $\Set{\emptyset} \cap \Set{\Set{\emptyset}}$.

Give a set equal to $\wp(\wp(\emptyset))$.

Give a set equal to $\wp(\wp(\wp(\emptyset)))$.

The starter code contains a driver program you can use to see the contents of your files and run tests to check your answers. Submit your answers through GradeScope under “Coding Problems for Problem Set One” by uploading your edited files. You’re welcome to submit as many times as you’d like; we’ll count as your grade the last version of the uploaded files.

Problem Two: Set Theory in C++

The C++ standard library contains a type called std::set that represents a set of elements, all of which must be of the same type. For example, the type std::set<int> represents a set of integers, the type std::set<std::string> represents a set of strings, and std::set<std::set<int>> is a type representing a set of sets of integers.

There are all sorts of operations you can perform on std::sets. For example, here’s how you iterate over all the elements of a set:

std::set<T> mySet;
for (T elem: mySet) {
    /* … do something with the current element elem … */
}

(Don't worry if you see a warning message when using this style of loop; it's perfectly fine for our purposes.)

Here’s how you check whether a particular value is an element of a set:

if (mySet.count(value)) {
    /* … value ∈ mySet … */
} else {
    /* … value ∉ mySet … */
}

And, finally, here’s how you can get the cardinality of a set:

size_t size = mySet.size();

Here, the size_t type is a type representing a natural number, since sets can’t have negative size. (The folks who designed the C++ standard libraries had a strong discrete math background.)

One of the major differences between the sets we’ve talked about in CS103 and the std::set type is that in discrete mathematics, sets can contain anything – numbers, philosophies, recipes, other sets, etc. – but in C++ all objects in a set must have the same type. For the purposes of this problem, we’ve created a custom C++ type called Object. Variables of type Object can represent just about anything, so a std::set<Object> represents something pretty similar to the sets we’ve been studying so far.

Some Objects are actually just std::sets in disguise. If you have an Object, you can test whether it’s actually a set by using this provided helper function:

bool isSet(Object o);

This takes in an Object, then returns true if that Object is actually a set and false otherwise. If you have an Object that really is a set, you can convert it to a set by using this helper function:

std::set<Object> asSet(Object o);

This function takes in an Object that you know happens to be a set, then returns the std::set<Object> that it actually is.

For example, suppose you have an Object that you know is really the set $\Set{1, 2, 3, 4}$. You could iterate over it using this code:

Object reallyASet = /* … */;
for (Object x: asSet(reallyASet)) {
    /* … do something with x … */
}

In this problem, we’d like you to demonstrate your understanding of sets and set theory by coding up a number of functions in C++ that operate on sets. In doing so, we hope that you’ll solidify your grasp of the distinctions between related concepts in set theory, such as the the $\in$ and $\subseteq$ relations and power sets.

Open the file SetTheory.cpp from the starter files. There, you’ll find a bunch of stubs of functions that you’ll need to implement. The provided starter code contains a test harness you can use to try out your functions. You won’t need to modify any of the other C++ files bundled with the starter code.

As with Problem One, you’ll submit the code that you write through GradeScope separately from the rest of the problems on this problem set. The GradeScope autograder will get back to you with feedback about how you’re doing on this problem, and you’re welcome to submit as many times as you’d like.

Implement a function
```
bool isElementOf(Object S, Object T);
```
that takes as input two Objects $S$ and $T$, then returns whether $S \in T$.

$S$ and $T$ might not be sets; you’ll need to use the isSet and asSet functions appropriately.

Implement a function
```
bool isSubsetOf(Object S, Object T);
```
that takes as input an object $S$ and an object $T$, then returns whether $S \subseteq T$.

$S$ and $T$ might not be sets; use the isSet predicate to check whether the appropriate arguments are sets and asSet to get a view of them as sets.

Implement a function
```
bool areDisjointSets(Object S, Object T);
```
that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets where $S \cap T = \emptyset$. (Two sets with this property are called disjoint.) The input parameters $S$ and $T$ may or may not be sets, and if they aren’t, your function should return false.

Implement a function
```
bool isSingletonOf(Object S, Object T);
```
that takes as input two objects $S$ and $T$, then returns whether $S = \Set{T}$. Again, $S$ and $T$ may or may not be sets.

Implement a function
```
bool isElementOfPowerSet(Object S, Object T);
```
that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \in \wp(T)$. Again, $S$ and $T$ may or may not be sets.

As a hint, you shouldn’t need to write code that computes $\wp(T)$ explicitly. See if you can find a different way to do this.

Implement a function
```
bool isSubsetOfPowerSet(Object S, Object T);
```
that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \subseteq \wp(T)$. Again, $S$ and $T$ may or may not be sets.

Implement a function
```
bool isSubsetOfDoublePowerSet(Object S, Object T);
```
that takes as input two objects $S$ and $T$, then returns whether $S$ and $T$ are sets and $S \subseteq \wp(\wp(T))$. Again, $S$ and $T$ may or may not be sets.

To submit your work, upload your edited SetTheory.cpp file to GradeScope. You’ll get immediate feedback on your score from our autograder, and you’re allowed to resubmit as many times as you’d like.

As a note, you shouldn’t edit SetTheory.h; our autograder will always use the default version of that file when running tests.

Problem Three: Describing the World in Set Theory

The notation of set theory (e.g. $\cup, \cap, \wp, \subseteq, \in, \emptyset, =,$ etc.) is a great tool for describing the real world. Answer each of the following questions by writing an expression using set theory notation, but without using plain English, without using set-builder notation, without introducing any new variables, and without using propositional or first-order logic (which we’ll cover next week). No justification is required.

Let $C$ be the set of all cats and $D$ be the set of all dogs. Let $A$ be the set of all adorable things and $B$ be the set of all bouncy things. Write an expression that says "all cats and all dogs are both adorable and bouncy."

Once you’ve written up your answer to this problem, take a minute to type-check it. As an example, suppose that you have the following answer:
\[(A \in B) \cap (A \in C).\]
This expression can’t be correct, and here’s one way to see this. The expression $A \in B$ is of type Boolean – either $A \in B$ is true or it isn’t – and the same is true of $A \in C$. However, the intersection operator $\cap$ can only be applied to sets. The expression therefore contains a type error: it tries to apply an operator that only works on sets to Boolean values.

You can type-check this answer in a different way. For example, suppose you came up with this expression:
\[A \cup D.\]
Here, $A$ and $D$ are sets, so it’s perfectly fine to write $A \cup D$, which evaluates to an object of type set. But notice that the statement here asks you to write an expression that says “all cats and all dogs are both adorable and bouncy,” and that statement is of type Boolean (cats and dogs either have these properties or they don’t). Therefore, $A \cup D$ can’t possibly be an expression with the right meaning, since the type of the expression (set) doesn’t match the type of the statement (Boolean).

If you’re having trouble with this problem, consider working backwards. You know that you need an expression that evaluates to type Boolean. What operations on sets do you have that produce Booleans? Or perhaps make the problem simpler. How would you say "all cats are adorable?" How about "all cats are both adorable and bouncy?"

Suppose you’re on an exciting first date. Let $Y$ represent the set of all your hobbies and $D$ represent the set of all your date’s hobbies. Write an expression that says that you have a hobby that your date doesn’t have.

As before, type-check your answer! Should your answer represent a set? A Boolean? Something else?

Let’s say that a committee is a group of people, which we can think of as being represented by the set of people that comprise it. Let’s have $S$ represent the set of all students at Stanford and let $F$ represent the set of all faculty at Stanford. Write an expression representing the set of all committees you can make from Stanford students and faculty that contain at least one student and at least one faculty member. You can assume no one is both a student and a faculty member.

Something to think about: how would you say “all committees made purely of students?” Something else to think about: what is the type of the statement to translate? Is it a Boolean? A set? Neither?