Discrete Math - Other Set Theory Basics

The power set of set S is the set of all ways of selecting members from set S. This can be done in many ways. Example, say that S={0,1,2}, how do we determine p(S)?

Table 18

One thing to note from the example above is that the empty set is always going to be an element of the power set. Instead of using a truth table (however), we can also use a tree. This is done by adding an extra element to each stage of the tree. For instance, if A={a,b}, then what is p(A)?

Figure 36
One way to represent the sum of a set of numbers is to state it in predicate logic. This is the following: $ ∀xPx= ∑_(x∈P)x,I(P)=in set P $. An ordered pair is the following: (x,y)={{x},{x,y}}. An ordered tuple is the following: (x,y,z)={{x},{x,y},{x,y,z}}. A cartesian product is a set of ordered tuples founded by multiplying sets, it can be denoted: A×B={(a,b)|a∈A,b∈B}. Example: Say X={0,1,2},and Y={A,B}

1. X×Y={(0,A),(0,B),(1,A),(1,B),(2,A),(2,B)}
2. Y×X={(A,0),(A,1),(A,2),(B,0),(B,1),(B,2)}

You can also find this in matrix form.

There is a specific cartesian product called the cartesian plane:

R×R={(x,y)|x∈R,y∈R}

The cardinality of a set is how many elements are in it. For instance, the cardinality of A={1,2} is |A|=2. The cardinality of a powerset is 2^n, where n is the cardinality of the number of elements in the original set. For instance, |p(A)|=4.