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 SS with the property that, given any xx, we have the dichotomy that precisely one of the two conditions x∈Sx \in S or x∉Sx \notin S is true. In the former case, we say that xx is an element of SS, and in the latter, we say that xx is not an element of SS.

A set is often presented in one of the following forms:

  • A complete listing of its elements. Example: the set S={1,2,3,4,5}S = \{1,2,3,4,5\} contains precisely the five smallest positive integers.
  • A listing of some of its elements with ellipses to indicate unnamed elements. Example 1: the set S={3,4,5,…,100}S = \{3,4,5,\ldots,100\} contains the positive integers from 3 to 100, including 6 through 99, even though these latter are not explicitly named. Example 2: the set S={2,4,6,…,2n,…}S = \{2,4,6,\ldots,2n,\ldots\} 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: S={x∈N∣x is prime}S = \{x \in \mathbb{N} \mid x \text{ is prime}\} is the set of primes. Example 2: S={x∈Z∣x2<3}S = \{x \in \mathbb{Z} \mid x^2 < 3\} is the set of integers whose squares are less than 3.

Definition 1.2. Two sets AA and BB are equal if they contain precisely the same elements, that is, x∈Ax \in A if and only if x∈Bx \in B. When AA and BB are equal, we denote this by A=BA = B.

Definition 1.3. A set AA is a subset of a set BB if every element of AA is also an element of BB; that is, if x∈Ax \in A, then x∈Bx \in B. When AA is a subset of BB, we denote this by A⊂BA \subset B.

Theorem 1.4. A=BA = B if and only if A⊂BA \subset B and B⊂AB \subset A.

Proof:

Sufficiency:
Assume A=BA=B i.e. x∈Ax \in A if and only if x∈Bx \in B
If x∈Ax \in A, x∈Bx \in B. Thus by definition1.3, A⊂BA \subset B
If x∈Bx \in B, x∈Ax \in A. Thus by definition1.3, B⊂AB \subset A

Necessity:
Assume A⊂BA \subset B and B⊂AB \subset A.
A⊂BA\subset B, then by definition 1.3, if x∈Ax \in A, then x∈Bx \in B.
B⊂AB \subset A, then by definition 1.2, if x∈Bx \in B, then x∈Ax \in A
i.e. x∈Ax \in A if and only if x∈Bx \in B ; by definition 1.2, A=BA=B∎

Exercise 1.5. Let A={1,{2}}A = \{1,\{2\}\}. Is 1∈A1 \in A? Is 2∈A2 \in A? Is {1}⊂A\{1\} \subset A? Is {2}⊂A\{2\} \subset A? Is {1}∈A\{1\} \in A? Is {2}∈A\{2\} \in A? Is {{2}}⊂A\{\{2\}\} \subset A? 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 AA and BB be two sets. The union of AA and BB is the set

A∪B={x∣x∈A or x∈B}.A \cup B = \{x \mid x \in A \text{ or } x \in B\}.

Definition 1.7. Let AA and BB be two sets. The intersection of AA and BB is the set

A∩B={x∣x∈A and x∈B}.A \cap B = \{x \mid x \in A \text{ and } x \in B\}.

Theorem 1.8. Let AA and BB be two sets. Then:

  1. A⊂A∪BA \subset A \cup B
  2. A∩B⊂AA \cap B \subset A

Proof:
If x∈Ax \in A, then by definition1.6, x∈A∪Bx \in A \cup B. Thus, by definition 1.3, A⊂A∪BA \subset A\cup B
If, x∈A∩Bx \in A\cap B, then by definition 1.7, x∈Ax \in A. Thus, by definition 1.3, A∩B⊂AA\cap B \subset A∎

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 ∅\emptyset. That is, no matter what xx is, we have x∉∅x \notin \emptyset.

Definition 1.10. Two sets AA and BB are disjoint if A∩B=∅A \cap B = \emptyset.

Exercise 1.11. Show that if AA is any set, then ∅⊂A\emptyset \subset A.

Proof:

Assume, for contradiction, that there exists set AA that ∅⊄A\emptyset \not\subset A
i.e. there exists x∈∅x \in \emptyset that x∉Ax \not\in A.
However, by definition 1.9, no matter what xx is, x∉∅x \not\in \emptyset.
This contradicts to the assumption.
Therefore, the assumption is not true. i.e. for all set AA, ∅⊂A\emptyset \subset A.∎

Definition 1.12. Let AA and BB be two sets. The difference of BB from AA is the set

A∖B={x∈A∣x∉B}.A \setminus B = \{x \in A \mid x \notin B\}.

The set A∖BA \setminus B is also called the complement of BB relative to AA. When the set AA is clear from the context, this set is sometimes denoted BcB^c, but we will try to avoid this imprecise formulation and use it only with warning.

Theorem 1.13. (DeMorgan's Laws) Let XX be a set, and let A,B⊂XA, B \subset X. Then:

  1. X∖(A∪B)=(X∖A)∩(X∖B)X \setminus (A \cup B) = (X \setminus A) \cap (X \setminus B)
  2. X∖(A∩B)=(X∖A)∪(X∖B)X \setminus (A \cap B) = (X \setminus A) \cup (X \setminus B)

Definition 1.14. Let AA and BB be two nonempty sets. The Cartesian product of AA and BB is the set of ordered pairs

A×B={(a,b)∣a∈A and b∈B}.A \times B = \{(a,b) \mid a \in A \text{ and } b \in B\}.

Definition 1.15. Let AA be a set. The power set of AA is the set of all subsets of AA and is denoted ℘(A)\wp(A). That is, ℘(A)={B∣B⊂A}\wp(A) = \{B \mid B \subset A\}.

Exercise 1.16. Let A={1,2,3}A = \{1,2,3\}. Identify ℘(A)\wp(A) by explicitly listing its elements.

Definition 1.17. Let AA and BB be two nonempty sets. A function ff from AA to BB is a subset f⊂A×Bf \subset A \times B such that for all a∈Aa \in A there exists a unique b∈Bb \in B satisfying (a,b)∈f(a,b) \in f. To express the idea that (a,b)∈f(a,b) \in f, we most often write f(a)=bf(a) = b. To express that ff is a function from AA to BB in symbols we write f:A→Bf: A \to B.

Exercise 1.18. Let the function f:Z→Zf: \mathbb{Z} \to \mathbb{Z} be defined by f(n)=2nf(n) = 2n. Describe ff as a subset of Z×Z\mathbb{Z} \times \mathbb{Z}.

Definition 1.19. Let f:A→Bf: A \to B be a function. The domain of ff is AA. If X⊂AX \subset A, then the image of XX under ff is the set

f(X)={b∈B∣f(x)=b for some x∈X}.f(X) = \{b \in B \mid f(x) = b \text{ for some } x \in X\}.

If Y⊂BY \subset B, then the preimage of YY under ff is the set

f−1(Y)={a∈A∣f(a)∈Y}.f^{-1}(Y) = \{a \in A \mid f(a) \in Y\}.

Definition 1.20. A function f:A→Bf: A \to B is surjective (also known as 'onto') if, for every b∈Bb \in B, there is some a∈Aa \in A such that f(a)=bf(a) = b. The function ff is injective (also known as 'one-to-one') if for all a,a′∈Aa, a' \in A, if f(a)=f(a′)f(a) = f(a'), then a=a′a = a'. The function ff is bijective (also known as a bijection or a 'one-to-one correspondence') if it is surjective and injective.

Exercise 1.21. Let f:N→Nf: \mathbb{N} \to \mathbb{N} be defined by f(n)=n2f(n) = n^2. Is ff injective? Is ff surjective?

Exercise 1.22. Let f:N→Nf: \mathbb{N} \to \mathbb{N} be defined by f(n)=n+2f(n) = n + 2. Is ff injective? Is ff surjective?

Exercise 1.23. Let f:Z→Zf: \mathbb{Z} \to \mathbb{Z} be defined by f(x)=x2f(x) = x^2. Is ff injective? Is ff surjective?

Exercise 1.24. Let f:Z→Zf: \mathbb{Z} \to \mathbb{Z} be defined by f(x)=x+2f(x) = x + 2. Is ff injective? Is ff surjective?

Lemma 1.25. Suppose that f:A→Bf: A \to B is bijective. Then there exists a bijection g:B→Ag: B \to A.

Definition 1.26. We say that two sets AA and BB are in bijective correspondence when there exists a bijection from AA to BB or, equivalently, from BB to AA.

Cardinality#

Definition 1.27. Let n∈Nn \in \mathbb{N} be a natural number. We define [n][n] to be the set {1,2,…,n}\{1,2,\ldots,n\}. Additionally, we define [0]=∅[0] = \emptyset.

Definition 1.28. A set AA is finite if A=∅A = \emptyset or if there exists a natural number nn and a bijective correspondence between AA and the set [n][n]. In this case, we say that the cardinality of AA is nn, and we write ∣A∣=n|A| = n. If AA is not finite, we say that AA is infinite. In either case, if there exists a bijection between two sets AA and BB, then we say that AA and BB have the same cardinality and write ∣A∣=∣B∣|A| = |B|.

(Supplementary Corollary: ∣[n]∣=n|[n]|=n because, of course, there is a bijective correspondence between such a set and itself, for example, f(x)=xf(x)=x)

Theorem 1.29. Let AA, BB, and CC be sets and suppose that there is a bijective correspondence between AA and BB and a bijective correspondence between BB and CC. Then there is a bijective correspondence between AA and CC.

The following two results show that the cardinality of a finite set is well-defined.

Theorem 1.30. (The Pigeonhole Principle) Let n,m∈Nn, m \in \mathbb{N} with n<mn < m. Then there does not exist an injective function f:[m]→[n]f: [m] \to [n].

Proof:

Suppose, for contradiction, that there exists such an injective function f:[m]→[n]f: [m] \to [n].

Then for all x,x′∈[m]x, x' \in[m] ,if f(x)=f(x′)f(x)=f(x') then x=x′x=x'. i.e. aa and f(a)f(a) is "one to one".
Then ∣[n]∣≥∣[m]∣|[n]|\geq|[m]|
However, By definition 1.27 and 1.28, we know that ∣[m]∣=m>∣[n]∣=n|[m]|=m>|[n]|=n.
This is a contradiction.
Thus, the supposition must be wrong: There does not exist an injective function f:[m]→[n]f: [m] \to [n]..

Similarly, Let n,m∈Nn, m \in \mathbb{N} with n<mn < m. Then there does not exist an surjective function f:[n]→[m]f: [n] \to [m].∎

Corollary 1.30'. Let n,m∈Nn,m \in \mathbb{N}, for a injective function f:[m]→[n]f:[m]\to[n], n≥mn\geq m.

Proof:

Suppose , for contradiction, that n<mn<m.
By theorem 1.30, there doesn't exist an injective function f:[m]→[n]f:[m]\to[n].
This is a contradiction to the supposition.
Thus n,m∈Nn,m \in \mathbb{N}, for a injective function f:[m]→[n]f:[m]\to[n], n≥mn\geq m. ∎

Theorem 1.31. Let AA be a finite set and suppose that ∣A∣=m|A| = m and ∣A∣=n|A| = n. Then m=nm = n.

Proof:

If ∣A∣=m|A| = m and ∣A∣=n|A| = n, then there exists a bijective correspondence between AA and [m][m], and AA and [n][n].

By Theorem 1.29, there is a bijective correspondence between [m][m] and [n][n]. By definition 1.28, cardinalities of [m][m] and [n][n] are equal.
By corollary of definition 1.28, ∣[m]∣=m|[m]|=m and ∣[n]∣=n|[n]|=n
Thus, m=nm=n.∎

Exercise 1.32. Let AA and BB be finite sets. If A⊂BA \subset B, then ∣A∣≤∣B∣|A| \leq |B|.

Proof:

Suppose g:A→[m]g:A\to[m] and i:B→[n]i:B\to[n] are bijections.
By Lemma 1.25, there exists bijective j:[m]→Aj:[m]\to A.
Let f:A→B,f(a)=af:A\to B, f(a)=a, which by definition 1.20 is injective.
Construct function h:[m]→[n],i∘f∘jh:[m]\to [n], i\circ f\circ j.
Then h(a)=i(f(j(x)))h(a)=i(f(j(x)))
Now we prove h(a)h(a) is injective. i.e. for every b∈Bb \in B, there is some a∈Aa \in A such that f(a)=bf(a) = b.
Then by Corollary 1.30',∎

Exercise 1.33. (The Inclusion/Exclusion Principle) Let AA and BB be two finite sets. Then:

∣A∪B∣+∣A∩B∣=∣A∣+∣B∣.|A \cup B| + |A \cap B| = |A| + |B|.

Exercise 1.34. Let AA and BB be two finite sets. Then ∣A×B∣=∣A∣⋅∣B∣|A \times B| = |A| \cdot |B|.

Exercise 1.35. How many subsets does the empty set have?

One, namely ∅\emptyset itself.
The only subset of ∅\emptyset is ∅\emptyset, because if A⊂∅A \subset \emptyset, then every element of AA must be in ∅\emptyset, which contains no elements; hence AA must have no elements, so A=∅A = \emptyset.

Exercise 1.36. How many subsets does [n][n] have?

2n2^n.

Exercise 1.37. Show that if AA is a finite set, then ∣℘(A)∣=2∣A∣|\wp(A)| = 2^{|A|}.