Paul Nicholls Stuff

22May/080

Lets Talk About Sets

A set is a collection of distinct objects considered as a whole.

[Wikipedia - http://en.wikipedia.org/wiki/Set ]

A set can be thought of as a collection of objects - or elements - and these objects can be anything, data - numerical - or indeed other sets. Elements in a set are in no particular order, and elements in a set must by definition be unique.

Introducing Sets

We can use a system called set builder notation to describe a set:

<br /> \mbox{Set, } S = \left\{ x \in \mbox{ Parent Set, } P \left| \mbox{ conditions } \right. \right\}<br />


For example, the following is a valid set notation for a set of the integer values from 1 to 9.

<br /> A = \left\{ x \in \mathbb{Z}^+ \left| x\mbox{ is odd } \wedge < 10 \right. \right\}<br />

Subsets

A subset is one or more element selected from a set. For an element to be a member of a subset, it must also have been a member of the parent set.

If A and B are sets, then A will be a subset of B if every element of A is also an element of B (denoted as A \subseteq B . Equivalently we can say that B is a superset of A, if B contains all the elements of A (denoted as B \supseteq A ).

<br /> \forall _x \left( {x \in A \to x \in B} \right)<br />

Proper Subset

A proper subset is one or more (but not all of the distinct) elements selected from a set. If A and B are sets, then A will be a proper subset of B if every element of A is also an element of B, but also there is one or more elements in B which are not part of A. This is denoted as A \subset B. Equivalently, B is a proper superset of A if B contains all the elements of A and more - B \supset A

<br /> \forall _x \left( {x \in A \to x \in B} \right) \wedge \exists _x \left( {x \in B \wedge x \notin A} \right)<br />

Cardinality

The cardinality of a set is how many members it contains, as shown in the examples below:

<br /> \left| \phi \right| = 0 \\<br /> \left| {\left\{ {1,2,3,4} \right\}} \right| = 4 \\<br /> \left| {\left\{ {\left\{ {1,2} \right\},\left\{ {3,5} \right\}} \right\}} \right| = 2<br />

Powerset

The powerset of a set, S is denoted as \mathcal{P}(S) is a set of all the subsets of that set. This is best explained in the example shown below:

<br /> S=\left\{ x,y,z\right\}\\<br /> \mathcal{P}(S)=\left\{ {\phi ,\left\{ x \right\},\left\{ y \right\},\left\{ z \right\},\left\{ {x,y} \right\},\left\{ {x,z} \right\},\left\{ {z,y} \right\},\left\{ {x,y,z} \right\}} \right\}<br />

Where the set s has a cardinality of n, the powerset will have a cardinality:

\left|\mathcal{P}(S)\right|=2^n

Truth Set

The truth set is the set of values for which a predicate logic statement holds true. For example, the truth set of \left\{ x \in \mathbb{Z}^+ \left| x^2 < 4 \right. \right\} is {1}.

Tuples

A tuple is a set of objects, but one in which the order of the elements is significant. For example, the set {1, 2, 3} is equal to the set {2, 1, 3} since the order of elements in a set is not important. In a tuple however, {1,2,3} would not equal {2, 1, 3}. In order for one tuple A to be equal to another B all of the elements of A a_i where _i is an index, must equal all the elements of B, b_i.

Set Operators

Cartesian Product

Where A and B are sets, the Cartesian product of the two sets is a set containing all possible pairings of elements from each of the two sets.

<br /> A = \left\{ {1,2} \right\} \\<br /> B = \left\{ {a,b,c} \right\} \\<br /> A \times B = \left\{ {\{ 1,a\} ,\{ 1,b\} ,\{ 1,c\} ,\{ 2,a\} ,\{ 2,b\} ,\{ 2,c\} } \right\}<br />

Union

The union of two sets, P and Q is a set containing all the unique items of P and Q.

A \cup B = \left\{ x \left| x \in A \vee x \in B \right. \right\}

Intersection

The intersection of two sets, P and Q is a set containing all the elements which exist in both A and B.

A \cap B = \left\{ x \left| x \in A \wedge x \in B \right. \right\}

Difference

The difference between two sets A and B is a set containing all the elements which exist only in A, not in B.

A - B = A \backslash B = \left\{ x \left| x \in A \wedge \neg\left( x \in B \right) \right. \right\}

Complement
The complement of a set is a set of all the possible elements which are not contained within the set. So if the domain is \mathbb{Z} and we have a set P with members in the domain, then \overline P = \mathbb{Z}-P

Venn Diagrams

A Venn Diagram can be used to demonstrate sets and set operators. In the example below, A and B are sets are in domain of real numbers - \mathbb{R} , and from the diagram there are a number of conclusions we can draw...

<br /> X=A \cap B \\<br /> U= \mathbb{R} - \overline{A\cup B} \\<br /> \left| A \cup B \right| = \left|A\right| + \left|B\right| - \left|A \cap B \right|<br />

Rules involving Sets

  • De-Morgan's theory applies to sets, this is discussed in more detail [Here]
  • Order of processing operations is not important, \left( {A \cup B} \right) \cup C = A \cup \left( {B \cup C} \right)
  • Identity Law: A \cup \phi = A
References:
  • Nick Holliman - Formal Aspects Set Theory - Lecture 3
  • Nick Holliman - Formal Aspects Set Theory - Lecture 4
  • Nick Holliman - Formal Aspects Set Theory - Lecture 5
  • Nick Holliman - Formal Aspects Set Theory - Lecture 6
  • Nick Holliman - Formal Aspects Set Theory - Lecture 7
  • Discrete Mathematics and its Applications - Kenneth H Rosen - Sixth Edition
Tagged as: , , Leave a comment
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

(required)

No trackbacks yet.

» «

Lifestream

Links

Blog Tags

awesome bands Binary Boolean charity CSYS CSYSII durham Events FA FA-ADM FA-ST friends fun Hardware indecisive Internet itunes2msn jubilee life Logic Machine Architecture Memory Mildert News music Networks Operating Systems parties philosophy politics rant resources rmgs school Set Theory software Storage TC TC-MC tech uni urmant vbe software win work