Oz's crib sheet: basic set theory
By Toby Bartels

Sets

A set is a mathematical creature that knows only one thing: whether things belong to it or not. Whatever belongs to a set are its elements. If X is a set, all you can say about X is stuff like x in X and y in X. You can't say how many times x belongs to X, nor in what order the elements of X belong to it, nor what relationships the elements may have with one another. If the only element of X is x, then X may be denoted "{x}". Notice that {x, x} is the same thing as {x}. If the elements of X are x, y, and z, then X may be denoted "{x, y, z}". Notice that {x, y, z} is the same thing as {z, y, x}. If the elements of X are x1 through xn, then X may be denoted "{x1, ..., xn}" or "{xi | i = 1, ..., n}". In modern mathematics, everything is constructed from sets, but the details of how that is done needn't concern us here.

Empty set: the set with no elements. Originally denoted by the Scandivanian O with a slash through it ("Ø"), it's now more commonly denoted as a numeral zero with a slash through it. (Anyone who tells you it's a Greek Phi is just wrong.) Of course, you could also say "{}". I will say "Ø" on this crib sheet.

Collection: a set whose elements are themselves sets, or possibly even sets with some extra structure (such as manifolds). While an ordinary set just has elements, a collection has elements' elements (the elements of the sets which are its elements). Since the elements of Ø are all sets (trivially), Ø is also a collection, the empty collection.

Subset: a set which is part of another set. If X and Y are sets, then Y is a subset of X if and only if, for all possible elements x, x is an element of X whenever x is an element of Y. It's possible that X has no elements other than those of Y; then X = Y. More often, however, X will have additional elements which Y doesn't share. Ø is a subset of every other set (as well as of itself).

Power set: For every set X, there is a collection ¶X of all the subsets of X. Note that X will itself belong to ¶X, as will Ø. This power set is usually denoted with some fancy form of the letter Pe, not necessarily "¶".

Union: If C is a collection of sets, then the set of all of C's elements' elements is UC, the union of C. That is, x in UC if and only if x in X for some X in C. The union is usually denoted by a big, thin lined curve in the shape of a U, rather than by an actual letter U. Notice that, if C is the empty collection Ø, then UC is also Ø. The union is most often encountered when C is rather small, and then you can see "X U Y" for U{X, Y}, "X U Y U Z" for U{X, Y, Z}, or even "X1 U ··· U Xn" for U{X1, ..., Xn}. (When it appears between symbols instead of in front of them, the union symbol is slightly smaller.) The last can also be written "Ui=1n Xi", where the "i = 1" and "n" should appear directly above and below the union symbol, just like in a summation formula.

Exercise to see if you're paying attention: What is U¶X, the union of the power set of X?

Intersection: Recall that x in UC if and only if x in X for some X in C. Well, x in IC if and only if x in X for all X in C. The real symbol for intersection is upside down of the symbol for union, never anything like the letter I. All the notational variations listed for union above apply to intersection the same way.

Intersection of the empty collection: Theoretically, IØ would be the set of everything. Aside from creating many interesting (but irrelevant to us) paradoxes, this possibility may violate the spirit of the context you're working in. For example, suppose C is an arbitrary subcollection of ¶X. Then we'd like UC and IC to be subsets of X. This will always happen for the union, and it will always happen for the intersection if C is nonempty. In order to make IØ a subset of X as well, define it to be X. This will work out quite well in what follows.

Exercise to see if you're paying attention: What is I¶X, the intersection of the power set of X?

Summary exercise that's a little deeper: Start with ¶X. The smallest subcollection of ¶X is the empty collection Ø, while the largest subcollection of ¶X is ¶X itself. Compare UØ, IØ, U¶X, and I¶X. What do you think?

Exercise that links with the topology crib sheet: Recall that the formal definition of topology that Michael gave consisted of a set X along with a collection T of subsets of X, such that T satisfied 3 conditions. Making judicial use of the concept of the empty collection, how can you reduce this to 2 conditions?

Complement: If Y is a subset of X, the complement of Y in X is the set of all elements of X which are not in Y. The complement of Y is denoted "Y'", "Yc", "Y" with a bar over it, or any of a number of different things. If you want to make mention of X explicit, say "X \ Y" (which is sometimes incorrectly written with a minus sign).

Major theorem (de Morgan): If X and Y are both subsets of some larger set, then (X U Y)' = X' I Y' and (X I Y)' = X' U Y'. This works if you take unions and intersections of more or fewer than 2 sets, too. Exercise: How does this relate to the summary exercise above? (This is kind of a trick question.)

OK, take a little breather now.

Functions

Function: If X and Y are sets, then f is a function from X to Y whenever f assigns a unique element of Y to each element of X. X is the domain of f, and Y is the codomain. The fact that f is a function from X to Y is written "f: X -> Y". If x is an element of X, then the specific element of Y which f assigns to x is called "f(x)". Despite what one commonly sees even in college math textbooks, "f(x)" is not the name of the function; "f" is. You can define a function by a formula; if f(x) is always x2, then an alternative notation for f is "x |-> x2". If you're working in a context where "x" is always used for a generic element of the domain, then you can abbreviate this as simply "x2". If you want to say that f and x |-> x2 are the same function, write "f: x |-> x2". Or put it all together as "f: X -> Y: x |-> x2". Sometimes people will mix the different kinds of arrows "->" and "|->". (Like all the arrows on this site, these are really each a single symbol all stuck together.) Note this terminology: f(x) is assigned to x, while x is mapped to f(x).

Identity function: For every set X, there is a special function 1X: X -> X: x |-> x. This is the identity function on X. The identity function is also called "idX" or "IX".

Injection, monic, one to one: These are all the same thing. A function f: X -> Y is one to one if f(x) never equals f(y) unless x = y. Thus, if you're told what f(x) is, then you automatically know what x is. In other words, the equation f(x) = y has at most 1 solution for x. (Of course, it might not have any.) Some people use the term "one to one" to mean one to one and onto. You'll usually see "one-to-one" spelled with hyphens, but I don't believe in hyphens.

Surjection, epic, onto: These are all the same thing. A function f: X -> Y is onto if every y in Y is f(x) for some x in X. In other words, the equation f(x) = y has at least 1 solution for x. (Of course, it might have more than 1.)

Range: If f: X -> Y, then the range of f is the set {f(x) | x in X}, that is the set of all elements of Y which are f(x) for some x in X. Note that the range of f is a subset of the codomain Y. If f is not onto, then we can shrink the codomain down to the range, so that f becomes onto. (Of course, it's a different f now, since the codomain is different.)

Image: If f: X -> Y and A is a subset of X, then the image f(A) of A under f is {f(x) | x in A}, that is the set of all elements of Y which are f(x) for some x in A. In this way, f defines a function (also called "f") from ¶X to ¶Y. The image of Ø is Ø. The image of the domain is the range. Sometimes people will say "the image of f" to mean the image of the domain of f, that is the range, especially in the sort of context where they'd say "map" instead of "function". For example, I did this in the definition of embedding on the topology crib sheet.

Preimage: If f: X -> Y and A is a subset of Y, then the preimage f-1(A) of A under f is {x | f(x) in A}, that is the set of all x in X such that f(x) is an element of A. In this way, f defines a function (called "f-1") from ¶Y to ¶X. The preimage of Ø is Ø. The preimage of the codomain, or of the range, or of anything between the range and the codomain, is the domain.

Exercise: If you start with the codomain, take the preimage, and then take the image, you get the range, which is a subset of the codomain. Is f(f-1(A)) always a subset of A? Is f-1(f(A)) always a subset of A? How about the other way around?

Related exercise: Is there a formula for f(A U B) in terms of f(A) and f(B)? How about f(A I B)? How about f-1(A U B)? How about f-1(A I B)?

Related exercise: If f: X -> Y is one to one or onto, what does this say about f: ¶X -> ¶Y? How about f-1: ¶Y -> ¶X?

Bijection: a function which is both one to one and onto. If f is a bijection, then the equation f(x) = y has exactly 1 solution for x.

Inverse: Suppose f: X -> Y is a bijection. If y in Y, then there is a unique element x in X such that f(x) = y. Therefore, that equation defines a function from Y to X. This function, like the preimage, is called "f-1". Notice that, if f: X -> Y and f-1: Y -> X are inverses, then so are f: ¶X -> ¶Y and f-1: ¶Y -> ¶X.

Composition: If f: X -> Y and g: Y -> Z, then you can get from X to Z by combining f and g into a single function g ° f. g ° f is defined to be x |-> g(f(x)). If f: X -> Y, then 1Y ° f = f = f ° 1X. If you think of ° as multiplication, now you know where the notation "1" for identity functions comes from. If f is also a bijection, then f ° f-1 = 1Y and f-1 ° f = 1X. So, now you know where the notation "-1" for inverses comes from.

OK, take another little breather now.

Families

How to think of an extended whole number as a set of natural numbers: Think of the number n as a set with n elements. Thus, 0 is the empty set Ø, n is the set {1, ..., n}, and infinity is the set {1, 2, 3, ...}. You can think of this as a notational convenience; whenever we want to refer to one of the sets above, we can just use the symbol for the number.

Sequence: a function whose domain is one of the sets above. A sequence of 0 terms (or empty sequence) is a function whose domain is Ø. A sequence of n terms (or finite sequence of length n) is a function whose domain is {1, ..., n}. A sequence of infinity terms (or infinite sequence) is a function whose domain is {1, 2, 3, ...}. If f is a sequence, write "fi" instead of "f(i)". The sequence can be given explicitly in the form "(f1, f2, f3, ...)". An ordered pair is simply a finite sequence of length 2.

Family: A family is a function whose codomain is more important than its domain. A sequence is a good example of a family, since nothing is more obvious than the set {1, ..., n}. As with a sequence, we use subscripts, writing "fi" instead of "f(i)". In fact, we usually don't even use a symbol like "f", prefering instead to use, say, "x" if the codomain is called "X". In the next section, I'll be working with families whose codomains are collections. Since the elements of collections are sets, such families are called "families of sets". An index set is the domain of a family. If I is an index set, you may see notation like "(xi | i in I)" being used for the family. If the family is a sequence, the notation might be "(xi | i = 1, ..., n)". For example, (i2 | i = 1, 2, 3, ...) is a family of natural numbers which maps every index number to its square. Sometimes people will be sloppy and use curly braces "{" and "}" instead of parentheses "(" and ")". Strictly speaking, {xi | i in I} is the range of the family, not the family itself. I will not be so sloppy here.

Constant family: If x in X and I is another set, we can make a constant family c whose index set is I. Simply say that, for all i in I, ci = x. Then whenever the notation "ci" might show up, you can just replace it with "x" instead. You can also express this family as "(x | i in I)". This is a very simple concept, but it's important.

Operations on families which you already know about: If x is an infinite sequence of real numbers, then x is actually a family whose index set is infinity. Then the sum of the sequence is written "+i=1infinity xi" (only with a large uppercase Greek Sigma instead of a plus sign and with the subscripts and superscripts directly above and below the Sigma). Similarly, the product of the sequence is written the same way, only with a Pi instead of a Sigma. So, addition and multiplication are actually operations on families of real numbers.

Operations on families whose index set is 2: If you think of 2 as the set {1, 2}, then 2 is just another possible index set for a family; such a family is a finite sequence of length 2, or ordered pair. But the notation for operations on such families is often different. For example, if you're given elements x and y of a set X, then you automatically have the ordered pair (x, y), a family of elements of X. Rather than construct a name (such as "z") for this family and then saying something like "+i=12 zi", you can just say "x + y". And notice that you use a different symbol in this case, an actual plus sign instead of a Sigma. That's a common circumstance with operations on families; a large symbol is used for the operation on an arbitrary family, with the elements of the family given by either a formula or a variable with a subscript, while a small symbol is used for the operation on an ordered pair, placed between explicit expressions for the elements of the ordered pair. (The small and large symbols are usually the same thing at different sizes, but not always. Indeed, for multiplication, the small symbol is blank!)

Operations on families of sets which you already know about: If X is a family of sets with index set I, then the union Ui in I Xi of the family is simply the union of the range of X as a function. There is also the abbreviated notation "Ui Xi", and of course "Ui=1n Xi" for sequences, which you may recognise from the paragraph on unions from before. (So, I was secretly already talking about families!) Of course, you can do the exact same things for intersection, although you'll want to make X a family of subsets of a given set Y, so that you can define the intersection of the empty family (the family whose index set is Ø), which will be Y, of course. Note that, because the union and intersection of a family of sets doesn't depend on how often the sets appear, or the order they appear in, or so on, I could define union and intersection of simple collections of sets earlier. But this won't work for the concepts I introduce in the next section, which is why we need families.

Prepare for the next section by taking another little breather.

Operations on families of sets

Disjoint union: bears only a superficial resemblance to union, or a deep categorical link. Take your pick. Anyway, the definition is pretty straightforward. If X is a family of sets with index set I, then the disjoint union +i in I Xi is {(x, i) | x in Xi, i in I}, that is the set of all ordered pairs of the form (x, i), where x is an element of Xi. Of course, you'd use a large uppercase Greek Sigma instead of the plus sign. If the index set I is 2, however, then you can use the plus sign to write "X1 + X2" for the disjoint union. That said, there are at least half a dozen other notations for disjoint union.

Deep but easy exercise to see if you're paying attention: What is the disjoint union of the empty family of sets?

Another deep exercise: If m and n are extended whole numbers being thought of as sets, what does the disjoint union of the sets have to do with the ordinary sum of the numbers?

Binary Cartesian product: If X and Y are sets, consider the constant family of sets whose index set is Y and whose constant value is X. Then you can form the disjoint union +y in Y X, which is {(x, y) | x in X, y in Y}. In other words, it's the set of all ordered pairs which can be made from an element of X and an element of Y. With any luck, you've seen this before. There is a special notation for this, of course: "X × Y".

Another deep exercise: If m and n are extended whole numbers being thought of as sets, what does the Cartesian product of the sets have to do with the ordinary product of the numbers?

Generic Cartesian product: The binary Cartesian product × is an operation on an ordered pair. Can we extend this to an operation on an arbitrary family? Yes! If X is a family of sets with index set I, then the Cartesian product ×i in I Xi is a set of families: the set of all families x with index set I such that xi in Xi. (We can take Ui Xi for the codomain of the families.) Of course, that should really be a large uppercase Greek Pi instead of "×".

Deep but easy exercise to see if you're paying attention: What is the Cartesian product of the empty family of sets? (No, it's not empty!)

Exercise to see if I'm lying to you: If X is a family with index set 2, is the generic Cartesian product ×i = 12 Xi really the same as the binary Cartesian product X1 × X2? If not, what is the relationship between them?

Exponentiation of sets: If X and Y are sets, consider the constant family of sets whose index set is Y and whose constant value is X. Then you can form the Cartesian product ×y in Y X, which is the set of all families f with index set Y such that fy in X. Or, more prosaically, it's the set of all functions f: Y -> X. There's a special notation for this: "XY". If n is an extended whole number, interpret n as a set to get Xn. Thus, Xinfinity is the set of infinite sequences of elements of X, Xn is the set of finite sequences of length n of elements of X, and X0 is the set of empty sequences in X (there is exactly 1). You're familiar with this in the case where X is the set R of real numbers.

Last deep exercise: If m and n are extended whole numbers being thought of as sets, what does the power mn of the sets have to do with the ordinary power of the numbers?

OK, I'm done, so take a breather. You deserve it.

Go back to Oz's crib sheet.
This web page was written between 2000 and 2002 by Toby Bartels. Toby reserves no legal rights to it.

The permanent URI of this web page is https://tobybartels.name/Oz/sets/.