:(i) Order of elements is immaterial. Thus {1,2} = {2,1} :(ii) Repetition of elements is irrelevent, so that {1,2,2,1,1} = {1,2} |
:(i) Order of elements is immaterial. Thus {1,2} = {2,1} :(ii) Repetition of elements is irrelevent, so that {1,2,2,1,1} = {1,2} |
We use the notation {x : P} to denote the set containing all objects x such that the condition P holds. For example, : {x : x is real} : denotes the set of real numbers, : {x : x has blonde hair} : denotes the set of all objects which have blonde hair, and : {x : x is a dog} : denotes the set of all dogs. In informal contexts we might also denote this last set by {dogs}. :Sets are frequently named by upper-case letters. Thus we might write :A = {x: x is an even integer} :to mean that A is the set of even integers. |
We use the notation {x : P} to denote the set containing all objects x such that the condition P holds. For example, : {x : x is real} denotes the set of real numbers, : {x : x has blonde hair} denotes the set of all objects which have blonde hair, and : {x : x is a dog} denotes the set of all dogs. In informal contexts we might also denote this last set by {dogs}. Sets are frequently named by upper-case letters. Thus we might write :A = {x: x is an even integer} to mean that A is the set of even integers. |
:A = {x : x is real} :B = {x : x is an integer} :C = {x : x is an odd integer} :D = {x : x is or was a US President} |
:A = {x : x is real} :B = {x : x is an integer} :C = {x : x is an odd integer} :D = {x : x is or was a US President} |
:{x in X : P(x)} |
:{x in X : P(x)} |
:{x : x is in X and P(x)} |
:{x : x is in X and P(x)} |
:A' = {x in U: x is not in A} |
:A' = {x in U: x is not in A} |
:C' = {x in B : x is not an odd integer} = {x : x is an even integer} |
:C' = {x in B : x is not an odd integer} = {x : x is an even integer} |
:B' = {x : x is real and not an integer} |
:B' = {x : x is real and not an integer} |
:A \/ B = {x : x is in A or x is in B or both} :A /\ B = {x : x is in A and x is in B} = {x in A : x is in B} = {x in B : x is in A} |
:A \/ B = {x : x is in A or x is in B or both} :A /\ B = {x : x is in A and x is in B} = {x in A : x is in B} = {x in B : x is in A} |
:A = {x in U : x is left handed} :B = {x in U : x has blonde hair} |
:A = {x in U : x is left handed} :B = {x in U : x has blonde hair} |
:E = {x : x is a human being} :F = {x : x is over 200 years old} |
:E = {x : x is a human being} :F = {x : x is over 200 years old} |
:(a) A /\ B = B /\ A :(b) A \/ B = B \/ A :(c) ( A /\ B) /\ C = A /\ ( B /\ C) :(d) ( A \/ B) \/ C = A \/ ( B \/ C) :(e) A is a subset of B if and only if A \/ B = B :(f) A is a subset of B if and only if A /\ B = A :(g) A /\ B is a subset of A, which is a subset of A \/ B :(h) A /\ O = O :(i) A \/ O = A :(j) If A and B are subsets of a universal set U, then A is a subset of B if and only if B' is a subset of A' |
:(a) A /\ B = B /\ A :(b) A \/ B = B \/ A :(c) (A /\ B) /\ C = A /\ (B /\ C) :(d) (A \/ B) \/ C = A \/ (B \/ C) :(e) A is a subset of B if and only if A \/ B = B :(f) A is a subset of B if and only if A /\ B = A :(g) A /\ B is a subset of A, which is a subset of A \/ B :(h) A /\ O = O :(i) A \/ O = A :(j) If A and B are subsets of a universal set U, then A is a subset of B if and only if B' is a subset of A' |
:(a) A /\ ( B \/ C) = ( A /\ B) \/ ( A /\ C) :(b) A \/ ( B /\ C) = ( A \/ B) /\ ( A \/ C) |
:(a) A /\ ( B \/ C) = (A /\ B) \/ (A /\ C) :(b) A \/ ( B /\ C) = (A \/ B) /\ (A \/ C) |
:(i) Pick any element x of the left-hand side (LHS). Then, by definition of /\, x is in A and x is in B \/ C; that is x is in A and either x is in B or x is in C. In the first case, x is in both A and B, so is in A /\ B and a fortiori in ( A /\ B) \/ ( A /\ C). In the second case x is in both A and C and so is again in ( A /\ B) \/ ( A /\ C). Thus in either case x is in ( A /\ B) \/ ( A /\ C). we have shown that every element of the LHS is automatically in the RHS. But this is precisely what we mean by saying that the LHS is a subset of the RHS. :(ii) Pick any element x of the RHS. Then x is in ( A /\ B) or x is in ( A /\ C); in the first case x is in A and x is in B; in the second, x is in A and x is in C. In either case x is in A. Also x in the first case x is in B and hence in B \/ C; in the second case x is in C and thus in B \/ C. We have proved that whatever x is, if it is a member of the RHS then it is in both A and B \/ C and hence by definition is in A /\ ( B \/ C). We have proved that the RHS is a subset of the LHS. |
:(i) Pick any element x of the left-hand side (LHS). Then, by definition of /\, x is in A and x is in B \/ C; that is x is in A and either x is in B or x is in C. In the first case, x is in both A and B, so is in A /\ B and a fortiori in (A /\ B) \/ (A /\ C). In the second case x is in both A and C and so is again in (A /\ B) \/ (A /\ C). Thus in either case x is in (A /\ B) \/ (A /\ C). we have shown that every element of the LHS is automatically in the RHS. But this is precisely what we mean by saying that the LHS is a subset of the RHS. :(ii) Pick any element x of the RHS. Then x is in (A /\ B) or x is in (A /\ C); in the first case x is in A and x is in B; in the second, x is in A and x is in C. In either case x is in A. Also x in the first case x is in B and hence in B \/ C; in the second case x is in C and thus in B \/ C. We have proved that whatever x is, if it is a member of the RHS then it is in both A and B \/ C and hence by definition is in A /\ (B \/ C). We have proved that the RHS is a subset of the LHS. |
:Z = {x : x is not a member of itself} |
:Z = {x : x is not a member of itself} |
:A * B = { (a , b) : a is in A and b is in B } That is, A * B is the set of all ordered pairs whose first component is an element of A and whose second component is an element of B. |
We can extend this definition to a set A * B * C of ordered triples, and more generally to sets of ordered n-tuples for any positive integer n. It is even possible to define infinite Cartesian products, but to do this we need a more recondite definition of the product. |
:A * B = { (a , b) : a is in A and b is in B } That is, A * B is the set of all ordered pairs whose first component is an element of A and whose second component is an element of B. We can extend this definition to a set A * B * C of ordered triples, and more generally to sets of ordered n-tuples for any positive integer n. It is even possible to define infinite Cartesian products, but to do this we need a more recondite definition of the product. |
Instead, we shall begin by defining sets informally and investigating a few of their properties. It is hoped that readers will then be in a better position to read, for example, the link above.
Firstly, we shall take the idea of membership as a primitive notion. That is, we shall assume that we know intuitively what it means to say that one object is a member (or element) of another. We then define a set to be an object which contains certain other objects ( we sometimes describe an object which is not a set as an individual). The simplest way to describe a set is to list its elements between curly braces. Thus {1,2} denotes the set whose only elements are 1 and 2.
We define two sets to be equal when they have precisely the same elements. Thus a set is completely determined by its elements.
Note the following points:
We use the notation {x : P} to denote the set containing all objects x such that the condition P holds. For example,
Sets are frequently named by upper-case letters. Thus we might write
Subsets: Given two sets A and B we say that A is a subset of B (or that A is contained in B, or that B contains A) if every element of A is automatically an element of B.
As an illustration, define
Given a set X, we may consider the subset of X consisting of all elements of X for which some further property holds. We write
Universal Sets and Complements: In certain contexts we may consider all of our sets as being subsets of some given universal set. For instance, if we are investigating properties of real numbers (and sets of reals) then we may take R, the set of all reals, as our universal set. It is important to realise that a universal set is only temporarily defined: there is no such thing as a "universal" universal set, "the set of everything" (see below).
Intersection and Union: Given two sets A and B we may construct their union. This is the set consisting of all objects which are elements of A or of B or of both. Their intersection is the set of all objects which are in both A and B. Symbolically, these are respectively
But now let the universal set U be the set of living things,
We list without proof a few other simple properties of sets.
We can also prove the so-called distributive laws
By Proposition 2, (i) and (ii) together prove that LHS = RHS, as required.
Paradoxes: We referred earlier to the need for a formal, axiomatic approach. What problems arise in the treatment we have given? The problems relate to the formation of sets. One's first intuition might be that we can form any sets we want,but this view leads to inconsistencies. For any set we can ask whether x is a member of itself. Define
Cartesian Product: We resume the formal development. Given objects a, b the ordered pair containing a and b is denoted (a, b). For the time being we shall take this as a primitive notion ( but see also here). That is we shall assume that (a , b) has the property that if (a , b) = (x , y) then a = x and b = y. The objects a and b are called respectively the first and second components of (a , b). Now, given two sets A and B, we define their Cartesian Product to be
We can extend this definition to a set A * B * C of ordered triples, and more generally to sets of ordered n-tuples for any positive integer n. It is even possible to define infinite Cartesian products, but to do this we need a more recondite definition of the product.
Cartesian products play an important role in analytic geometry. If R denotes the set of all real numbers, then R2 represents the Euclidean plane and R3 represents three-dimensional Euclidean space.