Sets and functions are among the most fundamental objects in mathematics. A formal treatment of set theory was first undertaken at the end of the 19th Century and was finally codified in the form of the Zermelo-Fraenkel axioms. While fascinating in its own right, pursuit of these formalisms at this point would distract us from our main purpose of studying Calculus. Thus, we present a simplified version that will suffice for our immediate purposes.
Sets#
Definition 1.1. (Working Definition) A set is an object with the property that, given any , we have the dichotomy that precisely one of the two conditions or is true. In the former case, we say that is an element of , and in the latter, we say that is not an element of .
A set is often presented in one of the following forms:
- A complete listing of its elements. Example: the set contains precisely the five smallest positive integers.
- A listing of some of its elements with ellipses to indicate unnamed elements. Example 1: the set contains the positive integers from 3 to 100, including 6 through 99, even though these latter are not explicitly named. Example 2: the set is the set of all positive even integers.
- A two-part indication of the elements of the set by first identifying the source of all elements and then giving additional conditions for membership in the set. Example 1: is the set of primes. Example 2: is the set of integers whose squares are less than 3.
Definition 1.2. Two sets and are equal if they contain precisely the same elements, that is, if and only if . When and are equal, we denote this by .
Definition 1.3. A set is a subset of a set if every element of is also an element of ; that is, if , then . When is a subset of , we denote this by .
Theorem 1.4. if and only if and .
Proof:
Sufficiency:
Assume i.e. if and only if
If , . Thus by definition1.3,
If , . Thus by definition1.3,
Necessity:
Assume and .
, then by definition 1.3, if , then .
, then by definition 1.2, if , then
i.e. if and only if ; by definition 1.2, ∎
Exercise 1.5. Let . Is ? Is ? Is ? Is ? Is ? Is ? Is ? Explain.
Yes, No, Yes, No, No, Yes, Yes.
1 is the element of A. {2} is the element of A while 2 itself is not.
{1}and {{2}} are subsets and not the elements of A.
Definition 1.6. Let and be two sets. The union of and is the set
Definition 1.7. Let and be two sets. The intersection of and is the set
Theorem 1.8. Let and be two sets. Then:
Proof:
If , then by definition1.6, . Thus, by definition 1.3,
If, , then by definition 1.7, . Thus, by definition 1.3, ∎
A special example of the intersection of two sets is when the two sets have no elements in common. This motivates the following definition.
Definition 1.9. The empty set is the set with no elements, and it is denoted . That is, no matter what is, we have .
Definition 1.10. Two sets and are disjoint if .
Exercise 1.11. Show that if is any set, then .
Proof:
Assume, for contradiction, that there exists set that
i.e. there exists that .
However, by definition 1.9, no matter what is, .
This contradicts to the assumption.
Therefore, the assumption is not true. i.e. for all set , .∎
Definition 1.12. Let and be two sets. The difference of from is the set
The set is also called the complement of relative to . When the set is clear from the context, this set is sometimes denoted , but we will try to avoid this imprecise formulation and use it only with warning.
Theorem 1.13. (DeMorgan's Laws) Let be a set, and let . Then:
Definition 1.14. Let and be two nonempty sets. The Cartesian product of and is the set of ordered pairs
Definition 1.15. Let be a set. The power set of is the set of all subsets of and is denoted . That is, .
Exercise 1.16. Let . Identify by explicitly listing its elements.
Definition 1.17. Let and be two nonempty sets. A function from to is a subset such that for all there exists a unique satisfying . To express the idea that , we most often write . To express that is a function from to in symbols we write .
Exercise 1.18. Let the function be defined by . Describe as a subset of .
Definition 1.19. Let be a function. The domain of is . If , then the image of under is the set
If , then the preimage of under is the set
Definition 1.20. A function is surjective (also known as 'onto') if, for every , there is some such that . The function is injective (also known as 'one-to-one') if for all , if , then . The function is bijective (also known as a bijection or a 'one-to-one correspondence') if it is surjective and injective.
Exercise 1.21. Let be defined by . Is injective? Is surjective?
Exercise 1.22. Let be defined by . Is injective? Is surjective?
Exercise 1.23. Let be defined by . Is injective? Is surjective?
Exercise 1.24. Let be defined by . Is injective? Is surjective?
Lemma 1.25. Suppose that is bijective. Then there exists a bijection .
Definition 1.26. We say that two sets and are in bijective correspondence when there exists a bijection from to or, equivalently, from to .
Cardinality#
Definition 1.27. Let be a natural number. We define to be the set . Additionally, we define .
Definition 1.28. A set is finite if or if there exists a natural number and a bijective correspondence between and the set . In this case, we say that the cardinality of is , and we write . If is not finite, we say that is infinite. In either case, if there exists a bijection between two sets and , then we say that and have the same cardinality and write .
(Supplementary Corollary: because, of course, there is a bijective correspondence between such a set and itself, for example, )
Theorem 1.29. Let , , and be sets and suppose that there is a bijective correspondence between and and a bijective correspondence between and . Then there is a bijective correspondence between and .
The following two results show that the cardinality of a finite set is well-defined.
Theorem 1.30. (The Pigeonhole Principle) Let with . Then there does not exist an injective function .
Proof:
Suppose, for contradiction, that there exists such an injective function .
Then for all ,if then . i.e. and is "one to one".
Then
However, By definition 1.27 and 1.28, we know that .
This is a contradiction.
Thus, the supposition must be wrong: There does not exist an injective function ..
Similarly, Let with . Then there does not exist an surjective function .∎
Corollary 1.30'. Let , for a injective function , .
Proof:
Suppose , for contradiction, that .
By theorem 1.30, there doesn't exist an injective function .
This is a contradiction to the supposition.
Thus , for a injective function , . ∎
Theorem 1.31. Let be a finite set and suppose that and . Then .
Proof:
If and , then there exists a bijective correspondence between and , and and .
By Theorem 1.29, there is a bijective correspondence between and . By definition 1.28, cardinalities of and are equal.
By corollary of definition 1.28, and
Thus, .∎
Exercise 1.32. Let and be finite sets. If , then .
Proof:
Suppose and are bijections.
By Lemma 1.25, there exists bijective .
Let , which by definition 1.20 is injective.
Construct function .
Then
Now we prove is injective. i.e. for every , there is some such that .
Then by Corollary 1.30',∎
Exercise 1.33. (The Inclusion/Exclusion Principle) Let and be two finite sets. Then:
Exercise 1.34. Let and be two finite sets. Then .
Exercise 1.35. How many subsets does the empty set have?
One, namely itself.
The only subset of is , because if , then every element of must be in , which contains no elements; hence must have no elements, so .
Exercise 1.36. How many subsets does have?
.
Exercise 1.37. Show that if is a finite set, then .