Class Notes (835,926)
Canada (509,504)
Brock University (12,091)
Economics (200)
ECON 2P30 (6)


13 Pages
Unlock Document

Lester Kwong

The Theory of Sets Lester M.K. Kwong ∗ Department of Economics Brock University Version: 3.1.1 Revised: September 18, 2012 ∗ Copyright ' 2004-2012 Lester M.K. Kwong. Department of Economics, Brock Uni- versity, 500 Glenridge Ave.Catharines, Ontario, L2S 3A1, CanEmail: lk- [email protected] Tel: +1 (905) 688-5550, Ext. 5137. This document was typeset with the LE XDocumentation System usingYthe X -pic and the MnSymbol packages. 1 Introduction Much of advanced economic theory is described using the notion of sets. For example, a consumer’s objective is to maximize his utility by choosing a bundle from the set of all a▯ordable bundles. Conversely, a player is to choose a strategy from the set of all possible strategies to maximize his expected payo▯ in a game theoretical scenario. Due to the wide usage of sets across the discipline, any progress into an understanding of economic theory will require a clear and precise understanding of the fundamental concepts often used in set theory. The remainder of this chapter is organized as follows. Section 2 intro- duces the basic concepts used in set theory. Namely, the notion of elements, empty sets, subsets, and power sets will be discussed. The introduction of elementary binary operations such as union, intersection, and complementa- tion are then discussed in Section 3. The discussion to include extended set operations and subsequently an introduction to concepts such as indexing and partitions are found in Section 4. Lastly, some review exercises follows. 2 Sets A set, in a nutshell, is simply some collection of objects which satisfy some characteristics de▯ning the set. An object which belongs to, or is a member of, a set is called an element. For example, the set N is the set of natural numbers whose members, or elements are the individual counting numbers. However, sets need not be restricted to numbers. A set of textbooks, for example, can have as elements the title of textbooks for certain courses or the set of teams in the NHL will have as elements teams in the National Hockey League such as the Vancouver Canucks. It is standard convention to denote sets using capital letters and its ob- jects, whether it is a member of the set or not, using lowercase letters. So for example, x is an object and X is a set. If x is an element of the set X, we denote this by writing x ∈ X read \x is in X," \x belongs to X," or just simply \x is an element of X." In the event that the object x does not belong to the set X, that is ∼ (x ∈ X), we write x ∉ X read \x is not an element of X." So for example, if N denotes the set of all teams in the NHL then Vancouver Canucks ∈ N whereas the New York Yankees ∉ N. Since a set is a collection of objects which satisfy some prede▯ned char- 1 acteristics, it is standard to write: X = {x ∶ S(x)} where S(x) is the predicate de▯ning such characteristics. The above notation is read \the set X is equal to the objects x (from the universe) so that S(x) is true." So, for example, if the universe is the set of all integers and S(x) =\x is a number strictly between 2 and 5," then the set X = {x ∶ S(x)} = {3;4}. Similarly, if the universe is the set of all NHL teams and S(x) =\x is a team in the Northwest Division," then X = {Calgary Flames, Colorado Avalanche, Edmonton Oilers, Minnesota Wild, Vancouver Canucks}. Note 1 that much like the \square" bracket as in [a;b], is used to denote the interval of real numbers from a to b inclusive, the usage of the \curly" brackets (i.e., the pair {;}) in the description of a set is also by convention. Hence, it is unconventional and rather meaningless to denote, for example, the set of odd numbers from 1 to 5 as [1;3;5] just as it is incorrect to refer to the closed interval from a to b, with a < b as {a;b}. It is also important to note that the symbolic de▯nition of a set given by X = {x ∶ S(x)} is merely a shortcut to the statement \the set X contains the objects x for which the predicate S(x) is true." Since the predicate is a description of characteristics explainable in words, the de▯nition of sets could be equally de▯ned using words as we have in the above examples. Additionally, since a set is de▯ned using predicates, the universe at hand should be precisely de▯ned unless the context under which the predicate appears makes it clear. For example, consider the set X = {x ∶ x = 4}. Under normal circumstances, it is appropriate to think that X = {−2;2}. However, if the universe is not the real numbers,R, (or integers, Z), but rather the set of natural numbers, N, then X = {2}. Clearly, the objects belonging to a set is precisely de▯ned relative to the universe concerned. For this reason, the universe is precisely stated in the characterization of the set. For example, if the universe is the set of real numbers, R, and we are characterizing the objects x from the universe so that x > 3, we may write {x ∈ R ∶ x > 3} for its de▯nition. This notation is read \the set of objects x from the set of real numbers so that x is strictly greater than 3." Alternatively, it could also be condensed further to read \the set of real numbers for which is strictly greater than 3." 1Of course, one may be tempted to use the example S(x) =\x is the best team in the NHL" in which case X = {Vancouver Canucks}. However, since the notion of best is rather subjective, we will treat this example as merely a credible, yet hypothetical possibility. 2 Consider the set {x ∶ x ≠ x}. This is the collection of objects from the universe so that the object x is not equal to the object x. On surface, this is a rather bizarre statement but will have important usages later on. Since every object from the universe, in principle, is equal to itself, the set {x ∶ x ≠ x} contains no elements. For this reason, we refer to this set as the empty set to literally imply a set containing no elements and denoted ∅ or sometimes {}. Since the empty set is a set containing no elements, the statement x ∈ ∅ is false for every x from the universe. This will be a very important point to remember for what follows. Also note that for the simple reason that the notation ∅ refers to a very speci▯c set and is written identically to the number 0 with a slash across it, it is poor habit to use ∅ with the number 0 interchangeably. Readers are strongly encouraged to abandon such poor habits from herein. Not only is it misleading, but also incorrect usage of standard notation in mathematics. Example 2.1 The”following are all examples of empty sets; (i) {x ∈ R ∶ x = −1} (ii) {x ∈ Z ∶ 2x + 2 = 7} (iii) {x ∈ N ∶ x + 2 = −1}. Let X and Y be two sets. The set X is said to be a subset of Y if and only if for every element of X is also an element of Y . If X is a subset of Y , we write X ⊆ Y . Symbolically, we can therefore de▯ne a subset by: X ⊆ Y ⇔ ƒx;x ∈ X ⇒ x ∈ Y If the conditions for X to be a subset of Y is violated, that is, ∃x ∈ X so that x ∉ Y , we say that X is not a subset of Y denoted symbolically as X ⊈ Y . Theorem 2.1 For every set X, (i) ∅ ⊆ X and (ii) X ⊆ X. Proof: Take any set X. (i) By the de▯nition of a subset, we need to show that x ∈ ∅ ⇒ x ∈ X. Since the antecedent of this statement (x ∈ ∅) is false, this conditional statement is always true. Hence, ∅ ⊆ X. (ii) Here, we need to show that x ∈ X ⇒ x ∈ X. For any proposition P (here, x ∈ X), P ⇒ P is a tautology, hence, X ⊆ X. ∎ Consider two sets X and Y . We say that the set X is equal to the set Y , denoted X = Y , if and only if X ⊆ Y and Y ⊆ X. Clearly, if either conditions 3 Universe Universe ’$ ’▯▯ ▯▯ xq x ▯▯ ▯▯ &%Y &%Y Figure 1: Venn diagrams. required for the equality of two sets are not satis▯ed, the sets are said to be not equal, denoted X ≠ Y . By Theorem 2.1, since the sets ∅ and X are always subsets of a set X they are referred to as improper subsets of X. In the case that for some set X, X ≠ Y , X ≠ ∅, and X ⊆ Y , we say that X is 2 a proper subsIt is convention to use the notation X ‘ Y if X is a proper subset of Y . A simple but useful visual tool when dealing with elementary relationships between sets is a Venn diagram named after its inventor John Venn. For example, in Figure 1, the left panel illustrates the case where X ⊈ Y . In particular, the element x ∈ X but that x ∉ Y . Conversely, the right panel of Figure 1 illustrates the case where X ⊆ Y . Example 2.2 Suppose we have the sets A = {1;2;3;4;5;8}, B = {3;4;5}, and C = {8}. Then B ‘ A and C ‘ A. Example 2.3 Let X = {x ∈ R ∶ 0 ≤ x ≤ 10} and Y = {x ∈ R ∶ 0 ≤ x ≤ 5}. Then Y ‘ X. This follows since 5 < 10 and hence, if x ≤ 5, then x ≤ 10 (in fact, x < 10). Therefore, if x ∈ Y , then x ≤ 5 (and hence x < 10) and x ≥ 0. In other words, x ∈ X. Therefore, x ∈ Y ⇒ x ∈ X and so Y ‘ X. Theorem 2.2 (Transitivity of ⊆) Let X, Y , and Z be sets. If X ⊆ Y and Y ⊆ Z, then X ⊆ Z. Proof: Suppose X ⊆ Y and Y ⊆ Z. It follows that for all x ∈ X, x ∈ Y . And since Y ⊆ Z, if x ∈ Y then x ∈ Z. Since x∎∈ X implies that x ∈ Z, X ⊆ Z. 2 Note that it is possible to write X ≠ Y and X ≠ ∅ as simply X ∉ {Y;∅}. Here {Y;∅} is the set containing the sets Y and the empty set. 3The de▯nition of transitivity is formally de▯ned in Section ??. 4 For any given set X, the collection of all subsets of X is referred to as the power set of X denoted P(X). In other words, P(X) = {Y ∶ Y ⊆ X}. It follows from Theorem 2.1 that ∅ ∈ P(X) and X ∈ P(X). It is perhaps worth pointing out the somewhat obvious but often overlooked fact that the power set of X contains sets as elements. That is, every element of P(X) is a set itself. Hence, if x ∈ X, x ∉ P(X). Rather, {x} ∈ P(X) since {x} ⊆ X. Clearly, the distinction to be made here is that x ∈ X whereas {x} ⊆ X. Example 2.4 Suppose X = {1;2;3}. Then: P(X) = {∅;X;{1;2};{1;3};{2;3};{1};{2;};{3}} Example 2.5 Suppose X = {1;2;{3;4}}. Then: P(X) = {∅;X;{1;2};{1;{3;4}};{2;{3;4}};{1};{2};{{3;4}}} Note that in Example 2.5, the element {{3;4}} in the power set of X is a set containing as an element, the set {3;4}. Hence, {3;4} ∉ P(X) whereas {{3;4}} ∈ P(X). This follows since {3;4} ⊈ X rather {3;4} ∈ X. Theorem 2.3 Let X and Y be sets. X ⊆ Y if and only if P(X) ⊆ P(Y ). Proof: Note that since this is a biconditional statement we need to prove the two statements (i) if X ⊆ Y then P(X) ⊆ P(Y ), and (ii) if P(X) ⊆ P(Y ) then X ⊆ Y . (i) Suppose X ⊆ Y and Z ∈ P(X). Since Z ∈ P(X), this implies that Z ⊆ X. By Theorem 2.2, we have Z ⊆ Y . Hence, Z ∈ P(Y ). Therefore, P(X) ⊆ P(Y ). (ii) Suppose P(X) ⊆ P(Y ). It follows from Theorem 2.1 that X ⊆ X and hence X ∈ P(X). Since P(X) ⊆ P(Y ), we have X ∈ P(Y ). By de▯nition, this implies that X ⊆ Y . ∎ 3 Operations on Sets Here, we discuss the most elementary operations on sets. For simplicity in exposition su▯cient for the purpose of introduction, we will only be concerned with operations between two sets. The extension to include operations over multiple sets will be discussed in Section 4. An operation between two objects 5 is referred to as a binary operation. The fundamental binary operations on sets consists of the intersection and the union. The intersection of two sets X and Y is the set of elements which belong to both X and Y denoted X ∩ Y (read \X intersect Y "). Symbolically, the intersection is de▯ned as X ∩ Y = {x ∶ x ∈ X ∧ x ∈ Y }. Intuitively, the inter- section comprises of the following; an element x belongs to the intersection of sets X and Y (i.e., x ∈ X ∩ Y ) if and only if x belongs to X (i.e., x ∈ X) and x belongs to Y (i.e., x ∈ Y ). For any two sets X and Y , if X ∩ Y = ∅, then X and Y are said to be disjoint. Example 3.1 Let X and Y be two sets. (i) If X = {1;2;3} and Y = {2;3;4}, then X ∩ Y = {2;3} since both 2 and 3 are elements common to both X and Y . (ii) If X = {1;2;3} and Y = {4;5;6}, then X ∩ Y = ∅. This follows since there are no common elements between X and Y . Hence, X and Y are disjoint. Theorem 3.1 Let X, Y , and Z be sets. We have; (i) (Commutativity) X∩Y = Y ∩X, (ii) (Associativity) (X∩Y )∩Z = X∩(Y ∩Z), (iii) X∩Y = X if and only if X ⊆ Y , and (iv) ƒX, X ∩ ∅ = ∅. The proof of these properties regarding the intersection operation are obvious and hence omitted. All readers, to this point, should be able to construct such proofs without aid. The union of two sets X and Y is the set of all elements which belong to X or Y (or both) denoted X ∪ Y (read \X union Y "). The union may be represented symbolically as X∪Y = {x ∶ x ∈ X∨x ∈ Y }. In words, The union of the sets X and Y consists of every element that either belongs to X, or to Y . Using Example 3.1, if X = {1;2;3} and Y = {2;3;4} then X ∪Y
More Less

Related notes for ECON 2P30

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.