SP20:Lecture 2 Set definitions
If element of .we say that is an
Here are some useful sets:
- The set natural numbers. of
- The set integers. of
Sets can contain things other than numbers:
- Let be the set of people in the room
The defining feature of a set is that every object is unambiguously either in or not in . You don't need an algorithm for determining which is true. For example:
- Let be the set of Java programs that never crash
This is a perfectly good set (assuming you define "Java program" and "crash"), even though there is no algorithm to determine whether a given program crashes or not. It either does or it doesn't, we don't have to know which.
This is an example of a degenerate object. An informal definition of a set would be something that has things in it; the empty set has no things in it, so perhaps we should rule it out. But most proofs work just as well with special cases as they do for the general case, so by default we include the special cases. We do the same thing when we define subset below.
We can list (or enumerate) the elements of a set:
You can think of this as shorthand for the set comprehension .
Sometimes we include a $\dots$ in an enumerated set if its meaning is clear (such as in the definition of inductively defined set.). This can be formalized more carefully as an
Sets can contain other sets:
- is a set containing two elements: the first is the set ; the second is the set containing .
- Note that
[]: ; the former contains one thing (the empty set), while the latter contains no things. This is analogous to the difference in python between
>>> len() 0 >>> len([]) 1
One easy way to construct a set is to draw a picture of it. A common way of doing so is a Venn diagram such as this one:
This diagram indicates that the setconsists of all of the points in the left-hand circle, while set consists of the points in the right hand circle.
Be careful: although Venn diagrams are a great way to create examples, they do not provide proofs that work for arbitrary sets. For example, an argument made using the diagram above does not describe the cases whereor when . Moreover, it doesn't consider finite sets or sets that are larger than any set of points in the plane. Venn diagrams give intuition (and examples) but not proofs.
The notation denotes the set of all that satisfy the property. You should read as "such that". For example,
We may want to specify that we're only interested in natural numbers; we often use notation like natural numbers which are even".. This should be read as "the set of
We can also have more complicated expressions to the left of the vertical bar, for example natural numbers: because and , while because there is no natural number that when multiplied by 2 gives 7.also denotes the set of even
Set comprehension example
Note that set comprehension notation can sometimes be tricky. Just because , doesn't necessarily mean satisfies .
For example, we know that, because , but that doesn't mean that .
The defining feature of a set is the collections of elements that are in or not in it. This suggests that we should consider two sets to be the same if they contain the same elements. This motivates the definition of equality:
This is equivalent to the following definition:
Here is a third variant:
These three definitions are equivalent (proof left as an exercise), so you can use them interchangeably.
This definition tells us that sets "ignore" duplicates and order. For example, every in the left hand side (LHS) is in the right hand side (RHS); by inspection, we see that , and . Then, we check that every in the RHS is in the LHS; which they are, again by inspection.; we can prove this using the definition. First, we check
The following claim follows immediately from the definition of ∅: