Sets and Functions PDF

Chapter 1 Sets and Functions We understand a “set” to be any collection M of certain distinct objects of our thought or intuition (called the “elements” of M ) into a whole. (Georg Cantor, 1895) In mathematics you don’t understand things. You just get used to them. (Attri...

Chapter 1 Sets and Functions We understand a “set” to be any collection M of certain distinct objects of our thought or intuition (called the “elements” of M ) into a whole. (Georg Cantor, 1895) In mathematics you don’t understand things. You just get used to them. (Attributed to John von Neumann) In this chapter, we define sets, functions, and relations and discuss some of their general properties. This material can be referred back to as needed in the subsequent chapters. 1.1. Sets A set is a collection of objects, called the elements or members of the set. The objects could be anything (planets, squirrels, characters in Shakespeare’s plays, or other sets) but for us they will be mathematical objects such as numbers, or sets of numbers. We write x ∈ X if x is an element of the set X and x ∈ / X if x is not an element of X. If the definition of a “set” as a “collection” seems circular, that’s because it is. Conceiving of many objects as a single whole is a basic intuition that cannot be analyzed further, and the the notions of “set” and “membership” are primitive ones. These notions can be made mathematically precise by introducing a system of axioms for sets and membership that agrees with our intuition and proving other set-theoretic properties from the axioms. The most commonly used axioms for sets are the ZFC axioms, named somewhat inconsistently after two of their founders (Zermelo and Fraenkel) and one of their axioms (the Axiom of Choice). We won’t state these axioms here; instead, we use “naive” set theory, based on the intuitive properties of sets. Nevertheless, all the set-theory arguments we use can be rigorously formalized within the ZFC system. 1 2 1. Sets and Functions Sets are determined entirely by their elements. Thus, the sets X, Y are equal, written X = Y , if x ∈ X if and only if x ∈ Y. It is convenient to define the empty set, denoted by ∅, as the set with no elements. (Since sets are determined by their elements, there is only one set with no elements!) If X 6= ∅, meaning that X has at least one element, then we say that X is non- empty. We can define a finite set by listing its elements (between curly brackets). For example, X = {2, 3, 5, 7, 11} is a set with five elements. The order in which the elements are listed or repetitions of the same element are irrelevant. Alternatively, we can define X as the set whose elements are the first five prime numbers. It doesn’t matter how we specify the elements of X, only that they are the same. Infinite sets can’t be defined by explicitly listing all of their elements. Never- theless, we will adopt a realist (or “platonist”) approach towards arbitrary infinite sets and regard them as well-defined totalities. In constructive mathematics and computer science, one may be interested only in sets that can be defined by a rule or algorithm — for example, the set of all prime numbers — rather than by infinitely many arbitrary specifications, and there are some mathematicians who consider infinite sets to be meaningless without some way of constructing them. Similar issues arise with the notion of arbitrary subsets, functions, and relations. 1.1.1. Numbers. The infinite sets we use are derived from the natural and real numbers, about which we have a direct intuitive understanding. Our understanding of the natural numbers 1, 2, 3,... derives from counting. We denote the set of natural numbers by N = {1, 2, 3,... }. We define N so that it starts at 1. In set theory and logic, the natural numbers are defined to start at zero, but we denote this set by N0 = {0, 1, 2,... }. Histori- cally, the number 0 was later addition to the number system, primarily by Indian mathematicians in the 5th century AD. The ancient Greek mathematicians, such as Euclid, defined a number as a multiplicity and didn’t consider 1 to be a number either. Our understanding of the real numbers derives from durations of time and lengths in space. We think of the real line, or continuum, as being composed of an (uncountably) infinite number of points, each of which corresponds to a real number, and denote the set of real numbers by R. There are philosophical questions, going back at least to Zeno’s paradoxes, about whether the continuum can be represented as a set of points, and a number of mathematicians have disputed this assumption or introduced alternative models of the continuum. There are, however, no known inconsistencies in treating R as a set of points, and since Cantor’s work it has been the dominant point of view in mathematics because of its precision, power, and simplicity. 1.1. Sets 3 We denote the set of (positive, negative and zero) integers by Z = {... , −3, −2, −1, 0, 1, 2, 3,... }, and the set of rational numbers (ratios of integers) by Q = {p/q : p, q ∈ Z and q 6= 0}. The letter “Z” comes from “zahl” (German for “number”) and “Q” comes from “quotient.” These number systems are discussed further in Chapter 2. Although we will not develop any complex analysis here, we occasionally make use of complex numbers. We denote the set of complex numbers by C = {x + iy : x, y ∈ R} , where we add and multiply complex numbers in the natural way, with the additional identity that i2 = −1, meaning that i is a square root of −1. If z = x + iy ∈ C, we call x =