Mathematical Proof/Introduction to Set Theory

Objects known as sets are often used in mathematics, and there exists set theory which studies them. Although set theory can be discussed formally There are various types of axiomatic set theory, in which Zermelo-Fraenkel set theory is the most well-known one., it is not necessary for us to have such a formal discussion in this book, and we may not be interested in and understand the formal discussion in this stage. Even if we do not discuss set theory formally, it is important for us to understand some basic concepts about sets, which will be covered in this chapter. What is a set means A set may be viewed as a collection of well-defined, distinct objects (the objects can also be sets). Because of the vagueness of the term "well-defined", we do not regard this as the definition of set. Instead, we regard set as a primitive notion (i.e., concepts not defined in terms of previously-defined concepts). Other examples of primitive notions in mathematics include point and line. We have mentioned that a set is a collection of well-defined, distinct objects. Objects in a set are called elements of the set. We write to mean that the element belongs to the set . If does not belong to , we write . Consider the set of all even numbers . Elements of include (but are not limited to) -2, 0, and 4, i.e., . The elements of the English alphabet (a set) are English letters. Ways of describing a set There are multiple ways to describe a set precisely (in the sense that element(s) belonging to the set is (are) known precisely). If a set consists of a small number of elements, then the listing method may be quite efficient. In the listing method, elements of a set are listed within a pair of braces ({}). In particular, just changing the listing order of elements does not change the set represented. For example, and are both representing the same set whose elements are 1 and 2. If the elements listed in the pair of braces are the same, the notations created by the listing method with different listing orders refer to the same set. Also, repeatedly listing a specific element in a set does not change the set represented. For example, and are both representing the same set whose elements are 1 and 2. In particular, if a set contains no elements, it can be denoted by based on the listing method or . This kind of set is called an empty set. Another way to describe a set is using words. For example, consider the set of prime numbers less than 10. If we use the listing method instead, the set is represented by . The third way to describe a set is advantageous when a set contains many elements. This method is called set-builder notation. There are three parts within a pair of braces in this notation. They are illustrated below with descriptions: As one may expect, two sets are equal if and only if they contain the same elements. Equivalently, two sets and are equal if and only if each element of is also an element of and each element of is also an element of . This can be regarded as an axiom . Indeed, this is the axiom of extension in the Zermelo-Fraenkel set theory. or a definition. If two sets and are equal, we write . If not, we write . In this book, when we are solving an equation, we are only considering its real solution(s) unless stated otherwise. . . . Assume and are different elements. Is each of the following statements true or false? {The set contains no elements. |type="()"} - True. + False. || This set contains one element, namely the empty set . { |type="()"} + True. || These two sets have no elements, thus containing the "same" elements. - False. { is a set. |type="()"} + True. || Even if the element "1" is listed two times, it still represents a set (which can also be denoted by ). - False. {. |type="()"} - True. + False. || Solving , we get , but both of them are not between 0 and 2 exclusively, so no satisfies the given property. As a result, the set on the RHS should be empty. } {. |type="()"} + True. || First, . Since the set is an element of the set on RHS, this is true. - False. {. |type="()"} - True. + False. || First, . But set doesn't contains , it only contains , which is not the same. Set cardinality If a set contains finite number of elements, it is called a finite set, and it is called an infinite set otherwise. If a set is finite, then its cardinality is its number of elements. For infinite sets, it is harder and more complicated to define their cardinalities, and so we will do this in the later chapter about set cardinalities. For each set , its cardinality is denoted by . Let . Then, . Let . Then, (not 3 since the element is listed repeatedly). Let . Then, since there is no solution for (for real number ), and thus is an empty set. Let . Solving , we have . Hence, and thus For sets with exactly one element, they are called singleton. In this case, is a singleton.. There are some special infinite sets for which notations are given, as follows: is the set of all natural numbers (0 is not regarded as a natural number in this book). is the set of all integers. is the set of all rational numbers. (nonstandard notation) is the set of all irrational numbers. is the set of all real numbers. is the set of all complex numbers. In particular, we can use set-builder notation to express , as follows: . Use set-builder notation to express without using "" in the expression. Solution We can express like this: (). Subsets (Subset) A set is a subset of a set (denoted by ) if each element of is also an element of . If is not a subset of , we denote it as . Recall that two sets and are equal if and only if each element of belongs to and each element of belongs to . Using the notion of subsets, we can write if and only if and . . (e.g. but ) (e.g. but ) For each set , , i.e. each set is a subset of itself. This is because each element of set is an element of . For each set , . If we want to prove this directly, there are some difficulties since does not contain any element. So, what is meant by "each element of "? Under this situation, it may be better to prove by contradiction (a proof technique covered in the later chapter about methods of proof). First, we suppose on the contrary that . By the negation of the definition, there is at least one element of that is not an element of , which is false. This yields a contradiction, and thus the hypothesis is false (explanation will be provided later), i.e. is false. (Proper subset) A set is a proper subset of a set (denoted by ) if is a subset of and . Similarly, if is not a proper subset of , we write . For each nonempty set , since (shown previously) and if is a nonempty set. . . and . Let . {Which of the following set(s) is a subset of ? |type="[]"} + || This set is . + || Empty set is a subset of every set. - - {Select the set(s) of which the set is a subset. |type="[]"} + || This set is . - || It is a subset of but is not a subset of . - + || Each element belonging to (the element "1") belongs to this set. {Select the set(s) of which the set is an element. |type="[]"} - - + || is an element of this set. + || is an element of this set. We call some commonly encountered subsets of intervals. For each real number such that , (open intervals) (half-open (or half-closed) intervals) (half-open (or half-closed) intervals) (closed intervals) There are also some infinite intervals: Note: is a shorthand of ( is a set). . . since the element "1" of the set on LHS does not belong to the set on RHS. . The set of (real) solutions of is . The set of (real) solutions of is . (Note: we cannot express this set as since it is required that for an interval .) The set of (real) solutions of is . {Which of the following is (are) valid interval(s)? |type="[]"} - + - || . - || This interval should be denoted by . Universal set and Venn diagram (Universal set) A universal set, denoted by , is a set containing all elements considered in a certain investigation. If we are studying real numbers, the universal set is . (Complement) The complement of a set that is a subset of the universal set , denoted by , is the set . Let and . Then, . (Note: also.) For each universal set , (since each element of does not belong to There are no elements belonging to .) and (since there are no elements of that does not belong to ). Let and . Then, since each element of does not belong to . Let the universal set be . {What is ? |type="()"} - + - - {What is ? |type="()"} + - - - {If the universal set is instead, . Which of the following can be (there may be more than one answer)? |type="[]"} - || If , then . + - || If , then . - || If , then . - || If , then . A Venn diagram is a diagram showing all possible logical relationships between a finite number of sets. The universal set is usually represented by a region enclosed by a rectangle, while the sets are usually represents by regions enclosed by circles. The following is a Venn diagram. center In this diagram, if the white region represents set and the region enclosed by the rectangle represents the universal set, then the red region is the set . However, the following is not a Venn diagram. center This is because there are not regions in which only the yellow and blue region intersect, and only the red and green region intersect, respectively. So, not all logical relationships between the sets are shown. To show all logical relationships between four sets, the following Venn diagram can be used. center Set operations Similar to the arithmetic operations for real numbers which combine two numbers into one, the set operations combine two sets into one. Union of sets (Union of sets) thumbnail|A Venn diagram for union of two sets. The union of a set and a set , denoted by , is the set . The "or" here is inclusive, i.e. if an element belongs to both and , it also belongs to . . . . . Let and be sets. Then, (commutative law) (associative law) and (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram. Because of the associative law, we can write union of three (or more) sets without brackets. We will have similar results for intersection of sets, and so we can also write intersection of three (or more) sets without brackets. Intersection of sets (Intersection of sets) thumbnail|A Venn diagram for intersection of two sets. The intersection of a set and a set , denoted by , is the set . If , we say that and are disjoint. Let and be sets. Then, (commutative law) (associative law) and (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram. (Distributive laws) Let and be sets. Then, (the "" is "distributed" to and respectively) Relative complement (Relative complement) thumbnail|A venn diagram for relative complement. If the region enclosed by the left and right circle represents and respectively, then the red region represents . The relative complement of a set in a set , denoted by , is the set . if is the universal set. So, the complement of a set is also the relative complement of in . The notation is read "B with A taken away". We can see from the definition that . . . . . {What is ? |type="()"} - - + || Since no numbers belong to and do not belong to , it is an empty set. - - {What is ? |type="()"} + - - - {What is ? |type="()"} + - || This set is . - || This is an empty set. - || This set is . {Which of the following set(s) is (are) the set of all positive numbers? |type="[]"} - || This set contains "0" as an element, which is not a positive number. + + - - || This set is . + {What is ? |type="()"} + || The set is . Since in the universal set, each element does not belong to the empty set, but no elements belong to the empty set. So, no elements belong to and does not belong to the empty set. - The universal set. - Let and be sets. Then, . . . if and only if . . . (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram. (De Morgan's Laws) Let and be sets. Then, (Formal) proof will be discussed later. For now, you may verify these results using Venn diagram. Suppose the universal set is , and . Since , . On the other hand, since and , . {What is ? |type="()"} - - - + || Since , . || Alternatively, since we already know what is and , by De Morgan's Laws, Symmetric difference (Symmetric difference) thumbnail|A Venn diagram illustrating symmetric difference. The symmetric difference of sets and , denoted by , is the set . . Let and be sets. Then, (associative law) (commutative law) {What is ? |type="()"} + || By the above proposition (the first or second point), we have - - - {What is ? |type="()"} + || First, since each element of does not belong to . || Second, since each element of does not belong to . || Thus, the answer is the union of and , i.e. . - - - - - - {Does We need not to write brackets for LHS because of the associative law.? (Try to determine it using Venn diagrams. No mathematical proof is required at the moment.) |type="()"} - Yes. + No. || Indeed, . || thumbnail|A Venn diagram illustrating . || 40px 40px 40px Power set (Power set) The power set of a set , denoted by , is the set of all subsets of . In set-builder notation, . Since for each set , is an element of each power set. Also, since for each set , is an element of the power set . . Its cardinality is 1. If , then . Its cardinality is 2. If , then . Its cardinality is 4. . Its cardinality is 8. (Cardinality of power set of a finite set) Let be a finite set with cardinality . Then, . Assume is a finite set with cardinality . Since each element of the power set is a subset of , it suffices to prove that there are subsets of . In the following, we consider subsets of with different number of elements separately, and count the number of subsets of each of the different types using combinatorics. For the subset with zero element, it is the empty set, and thus there is only one such subset. For the subsets with one element, there are subsets. For the subsets with two elements, there are subsets. ... For the subsets with elements, there are subsets. For the subset with elements, it is the set , and thus there is only one such subset. So, the total number of subsets of is by binomial theorem. The proof method employed here is called direct proof, which is probably the most "natural" method, and most commonly used. We will discuss methods of proof in a later chapter. There are alternative ways to prove this theorem. In each of the following questions, choose the power set of the set given in the question. { |type="()"} - - + || and . - { |type="()"} + - - - { |type="()"} + - - - { |type="()"} - - - + || . Even if is repeated two times in the set, there is only one "" is the power set. It is given that . In each of the following questions, choose the cardinality of the set given in the question. { |type="()"} - 4 - 8 + 16 || Its cardinality is . - 32 { |type="()"} - 0 - 1 + 2 || Its cardinality is . - 4 { |type="()"} + 1 || The set contains only one element, namely the power set . - 2 - 4 - 8 { |type="()"} - 1 + 2 || Since the set has only one element, namely , the cardinality is . - 4 - 8 { |type="()"} + 1 || Since , the given set is . Its cardinality is 1. - 2 || , which is of cardinality 0, while , which is of cardinality 1. - 4 - 8 Cartesian product (Cartesian product) The Cartesian product of sets and , denoted by , is . is the ordered pair (i.e. a pair of things for which order is important). The ordered pair is used to specify points on the plane, and the ordered pair is called coordinates. In particular, we have if . (notation) We use to denote for each set . We can observe that . Let and . Then, . . We can see from the above example that the Cartesian product is not commutative, i.e. it is not necessary for . Let . {What is (there may be more than one answer)? |type="[]"} - - + || Since no elements belong to the empty set, there is not any ordered pair in this set, i.e. this set has no elements. + || Indeed, for each set , . + || This equals the empty set. {What is ? |type="()"} - || Some ordered pairs that should be included in this set are missed. We need to include all ordered pairs satisfying the conditions mentioned in the definition. + - - Similarly, we can define the Cartesian product of three or more sets. (Cartesian product of three or more sets) Let be an integer greater than 2. The Cartesian product of sets is . (notation) We use to denote , where .