20.1 Basic set theory notions
The core definition in set theory is as to whether or not something is a member of a set or not. We write if is a member of a set and if not.
If we consider then but .
We say that is a subset of (written ) if and only if every member of is also a member of . In logic-y notation, this is
We say that two sets and are equal (written ) if and only they contain the same elements.
We can write this in logic symbols as
Two sets and are equal if and only if and .
Note: this requires a bit of knowledge of some of the basics of logic.
We start by applying a standard technique; to prove an implication we assume that the antecedent (aka \sayleft-hand side) is true, and prove that therefore the right-hand side must also be true.
Therefore, we assume that the left-hand side is true, and will try to show that therefore . We can do this by showing that and .
To show that , let be arbitrary. In this case we can show this
Note that the other direction follows by symmetry; if we swap and in the above proof, then the statement is still true and thus (under the assumptions set out).
20.1.1 Some example set theory proofs
Prove that .
To prove this statement we must show that , that is, for every value of , this value of is in the left-hand side set if and only if (read: exactly when) it is in the right-hand side set.
We can then apply De Morgan’s laws here, which tell us that (read: \sayx is not in and ) is equivalent to or 11 1 Don’t forget that is the negation of . Therefore, our statement is true if and only if
Now, it is important not to forget that logical and distributes over logical or, i.e. this is equivalent to
Then we know that this is equivalent to (by applying the definitions)
Then, after applying the definition of set union, we know that the previous is true if and only if
which is what we wanted to prove.