PS1, Part 1: Set Theory

Problem One: Much Ado About Nothing

Do this problem in the QT project.

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++

Do this problem in the QT project.

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.

For the purposes of this problem, we’ve created a custom C++ type called Object to represent individual elements of a set. Be they integers, real numbers, U.S. coins, plant species, people, or other sets, Object can represent any type that might be an element of a set.

Since one of the element types that Object can represent is actually another set, we have gven you a way to test if an Object is a just a set in disguise, using this helper function:

bool isSet(Object o);

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

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

Of course, be sure not to call asSet(o) unleess you are sure that o is actually a set!

Notice that the type of set that we are using is always going to be std::set<Object>. In other words, we are using the C++ Standard Template Library std::set (not the Stanford Library version! Cool/exciting for you 106B alumni!), and we will always have the set hold our type Object. For the purposes of this problem, you just need to know a couple of the member functions of std::set (specifically count() and size()) and how to for-loop over it. All three features are demonstrated for you in the code snippet below. Notice how before using those std::set features, we first test if an Object is a actually set, and then use asSet() to officially treat it as one:

// Just a sample function
bool foo(Object obj) {

    // test if Object obj is a set
    if (isSet(obj)) {
        
        // convert Object into type std::set<Object> in our program
        std::set<Object> s = asSet(obj);

        /*** Now ready to do set things with s ***/

        // Iterate over elements of a set
        for (Object elem : s) {
            // ... do something with elem ...
        }

        // Test if an Object x is an element of a set
        Object x; // pretend we set x to something
        if (s.count(x)) {    
            // yes! x is an element of s
        } else {
            // no, it is not
        }

        // Get the size of a set (i.e., get its cardinality)
        if (s.size() == 2) {
            // the cardinality is 2
        }

    }
    return true;
}

By the way, don't worry if you see a warning message when using the style of for-loop shown above; it's perfectly fine for our purposes.

Those are all the std::set functions you should need for this assignment! You're now ready to begin coding.

Begin Coding: In QT Creator, open the file SetTheory.cpp from the pset0 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 other than SetTheory.cpp.

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$.

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$.

For this problem, we welcome you to use functions that you write as helper functions for the other parts of the problem. Now that you've written a subset function, keep that in mind for later.

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.

You shouldn’t need to write code that computes $\wp(T)$ explicitly. See if you can find a different way to do this, using your knowledge of what "power set" means.

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

Do this problem on Overleaf in the LaTeX file, or your choice of text editor (e.g., Google Doc, Microsoft Word).

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?