Some notes on propositional logic and sets after grading HW1Q6(b)

Hi people, after grading HW1Q6(b) I found some mistakes that are (somewhat) common. They do not affect your correctness in this proof as your reasoning is correct and I get your idea, but I think it’s worth noticing it here as they are, after all, not correct:

1. Set notation

(I guess for some of you it’s typo tho) $\in$ is applied on elements (which could be a set), and $\subseteq$ is applied on sets. If you’ve taken cs61a, think about in operator for $\in$: e.g. Assume, $S={114, 514, 1919, 810}$, then we can say $114 \in S$, but note ${114, 514}\notin S$! ${114,514} \subseteq S$ or more precisely, ${114,514} \subset S$. That doesn’t mean the left hand side cannot be a set for $\in$! For example, $S \in \mathbb{P}(\mathbb{N*})$ but $S \not\subseteq \mathcal{P}(\mathbb{N^*})$.

2. $\forall$ and $\exists$

This might actually a little bit tricky and unintuitive (I don’t really know as my native language isn’t English…), but when you are deciding which one to pick: If you are picking an arbitrary $x$ from a set or stuff, use $\forall$; and use $\exists$ if you are trying to prove that you can pick a specific $x$ for your task. For example, if the proposition is “All readers have taken CS70”, that is, $\text{CS70 su20 Reader} \subseteq \text{People who took CS70}$ you would need to use $\forall$, that is: $\forall x\in \text{CS70 su20 Reader}, x\in \text{People who took CS70}$, or more “logically”: $\forall x, (x\in \text{CS70 su20 Reader} \implies x\in \text{People who took CS70})$. This means that if this is true, you cannot find anybody that is a reader but didn’t take CS70. Of course $\exists x\in \text{CS70 su20 Reader} \implies x\in \text{People who took CS70}$ is guaranteed to be true (think about why), but think about this example:

Prove or disprove: all readers are weeb. This is clearly not correct as although you can find a otaku reader (namely me), not every reader likes anime. If you use $\exists x (x\in \text{CS70 su20 Reader} \implies x\in \text{Weebs})$ to represent this claim, you can prove the proposition by taking $x:=\text{Ruomu}$ which yields incorrect result.

Similarly, in this question, if you want to prove the argument by picking an x and WLOG stuff, you want to prove that $\forall y, y \in f(A\cup B)$ then $y \in f(A)\cup f(B)$ and vice versa. If you write $\exists y, y \in f(A\cup B)$ then $y \in f(A)\cup f(B)$, you are definitely correct but this will only tell you that $(A \cup B) \cap (f(A)\cup f(B)) \neq \varnothing$ (Think about why).

This is to say, although you might say that “pick some $x$” and by that you mean “pick some arbitrary $x$” not “pick some specific $x$ but not other ones, then that is equivalent to “for all $x$ and you should use $\forall$.

Substitute $f(A)\cup f(B)$ to be people who graduated from a California university and $f(A\cup B)$ to be UC faculties - picking Daddy DeNero would make $\exists$ true, but $\forall$ is not as we have Chancellor Carol Christ (just want to mention them two, love Carol and her speeches! lol)

If you are interested in this topic and propositional logic, consider taking a logic course offered by Department of Philosophy, like PHILOS 12A!

Finally, do please select pages and double-checking readability of your submission before you submit it to avoid unnecessary problems!