Elements of a Set

• Sets are comprised of members, which are often called elements.

• If a particular value (\(k\)) is an element of set \(A\), then we would write this as \[k \in A \]

• If a single value \(k\) is not an element of set \(A\), then we write \[k \notin A \]

Proper Subsets

Given two sets \(A\) and \(B\), the set \(A\) is a proper subset of set \(B\) if every element of \(A\) is also an element of \(B\), but there are elements of set \(B\) that are not in set \(A\).

We write this mathematically as \[A \subset B \]

Definition of a set

A set is defined completely by its elements. Formally, sets X and Y are the same set if they have the same elements; that is, if every element of X is also an element of Y, and vice versa. For example, suppose we define:

\[ F = \{x | \mbox{(x is an integer)} \mbox{ and } 0 < x < 4)\} \]

The equivalence of empty sets has a consequence for some theories of the metaphysics of properties that define the property of being x as simply the set of all x, then if the two properties are uninstantiated or coextensive they are equivalent - under this theory, because there are no unicorns and there are no pixies, the property of being a unicorn and being a pixie are the same - but if there were a unicorns and pixies, we could tell them apart. (See Universals for more on this.)

Sets containing Sets

Sets can of course be elements of other sets; for example we can form the set \(G = \{A,B,C,D,E\}\), whose five elements are the sets we considered earlier. Then, for instance, \(A\in G\). (Note that this is very different from saying \(A\subseteq G\))

Elements of a Set

• Sets are comprised of members, which are often called {elements}.

• If a particular value (\(k\)) is an element of set \(A\), then we would write this as \[k \in A \]

• If a single value \(k\) is not an element of set \(A\), then we write \[k \notin A \]

Subsets

Given two sets \(A\) and \(B\), the set \(A\) is a {subset} of set \(B\) if every element of \(A\) is also an element of \(B\).

We write this mathematically as \[A \subseteq B \]

Sets are denoted with curly braces, even if they contain only one element.

Subsets

Suppose we have the set \(A\) comprised of the following elements \[ A =\{3,5,7,9\}\] The value \(5\) is an element of \(A\) \[ 5 \in A \]

The single element set ${5} $ is a subset of \(A\). \[ \{5\} \subseteq A\]

Elements and subsets

The \(\in\) sign indicates set membership. If x is an element (or “member”) of a set X, we write $ X$; e.g. \(3\in A\). (We may also say X contains x" andA contains 3”)

A very important notion is that of a subset. X is a subset of Y, written \(X \subseteq Y\) (sometimes simply as\(X \subset Y\)), if every element of X is also an element of Y. From before \(C\subseteq A \subseteq E\).

Proper Subset

The term “proper subset” can be defined as “subset of but not equal to”. A Set X is a proper subset of set Y (Written as X⊂YX⊂Y) if every element of X is an element of set Y and \(|X|<|Y|\).

Sets containing Sets

Sets can of course be elements of other sets; for example we can form the set \(G = \{A,B,C,D,E\}\), whose five elements are the sets we considered earlier. Then, for instance, \(A\in G\). (Note that this is very different from saying \(A\subseteq G\))

%The tilde (~) is as usual used for negation; e.g. \(\tilde(A\in B)\).

Equivalent Sets

If both of the following two statements are {true}, \[\mbox{1) } A \subseteq B \] \[\mbox{2) } B \subseteq A \]

then \(A\) and \(B\) are {equivalent sets}.

Non-Comparable Sets}

If both of the following two statements are {false}, \[\mbox{1) } A \subseteq B \] \[\mbox{2) } B \subseteq A \]

then \(A\) and \(B\) are said to be said to be {noncomparable sets}.

Shade in the following areas on Venn diagrams.

((a) \(A^\prime\; \cup\; B\)

((b) \(A \cap\; B^\prime\;\)

((c) \((A \cap\; B)^\prime\;\)

((d) \(A^\prime\; \cup\; B^\prime\;\)

((e) \((A \cup\; B)^\prime\;\)

((f) \(A^\prime\; \cap\; B^\prime\;\)

} \[(a) \;\; A^\prime \; \cup\; B\] %– % } %Question 2 \[(b) \;\; A \cap\; B^\prime\;\] %– % } %Question 3 \[(c) \;\; (A \cap \; B)^\prime\;\] %– % } %Question 4 \[(d) \;\; A^\prime\; \cup\; B^\prime; \] %– % } %Question 5 \[(e) \;\; (A \cup\; B)^\prime;\] %– % } %Question 6 \[(f) \;\; A^\prime\; \cap\; B^\prime\;\]

Specifying Sets

NOTATIONS FOR A SET:

A set can be represented by two methods: 1.ROSTER METHOD 2.BUILDER METHOD

ROSTER METHOD:

In this method the elements of a set are separated by commas and are enclosed within curly brackets { }. For example:

• A = {1, 2, 3, 4, 5, 6} is a set of numbers.

• \(B = \{Albert, Brianna, Carmel, David, Edward\}\) is a set of names.

• \(C = \{a, e, i, o, u\}\) is a set of vowels.

• \(D = \{apple, banana, guava, orange, pear\}\) is a set of fruits.

Listing the elements in this way is called Roster method. In this method, it is not necessary for the elements to be listed in a particular order. The elements of the set can be written just plainly, separated by commas and in any order.

BUILDER METHOD:

This method is also called Property method. In Builder method, a set is represented by stating all the properties which are satisfied by the elements of that particular set only.

For example:

If A is a set of elements less than 0, then in Builder method it will be written as

A = {x: x < 0}, this statement is read as “the set of all x such that x is less than 0”

If A is a set of all real numbers less than 7, then in Builder method it is written as \(A = {x R: x < 7}\)

Similarly,

• A = {2i: i is an integer} is a set of all even integers.

• \(A = {x R: x ? 2}\) is a set of all real numbers except 2.

• \(A = \{x R: x > 3 and x < 7\}\) is a set of real numbers greater than 3 but less than 7.

• A = {x Z: x > 6} is a set of integers greater than 6.

• \(A = {x Z: 2x + 1}\) is a set of all odd integers.

Set difference

• The difference X minus Y, written X-Y or \(X\|Y\), contains all those elements in X that are not also in Y.
• For example, \(E-A\) contains all integers greater than 3. A-B is just A; red, green and blue were not elements of A, so no difference is made by excluding them.

Set Difference

• The Set Difference of A with regard to B are list of elements of A not contained by B.

• The complements are denoted \(\mathcal{A-B}\) and \(\mathcal{B-A}\) \[ \mathcal{A-B} = \{1,3,5,7\}, \]

\[ \mathcal{B-A} = \{4,6,8\}, \]

Set Difference/ Relative Complement

The set difference of sets A and B (denoted by \(A–B\)) is the set of elements which are only in A but not in B. Hence, \(A-B={x|x \in A AND x \notin B}\). Example: If \(A={10,11,12,13}\) and \(B={13,14,15}\), then \((A-B)={10,11,12}\) and \((B-A)={14,15}\). Here, we can see (A-B)?(B-A)(A-B)?(B-A) Set Difference

Intersection

• Intersection of two sets describes the elements that are members of both the specified Sets

• The intersection is denoted \(\mathcal{A\cap B}\) \[ \mathcal{A\cap B} = \{2\}\]

• only one element is a member of both A and B.

---

Set Difference

• The Set Difference of A with regard to B are list of elements of A not contained by B.

• The complements are denoted \(\mathcal{A-B}\) and \(\mathcal{B-A}\) \[ \mathcal{A-B} = \{1,3,5,7\}, \]

\[ \mathcal{B-A} = \{4,6,8\}, \]

*{Exercise}

Membership Tables

Perhaps not a direct answer to your question, but we have \((A\cup B)\setminus C = (A\cup B)\cap C^c = (A\cap C^c)\cup (B\cap C^c) = (A\setminus C)\cup (B\setminus C)\)

So, the two are indeed equivalent.

For a truth table:

\[\begin{array}{c|c|c|c|c|c|c|c} A & B & C & A\cup B & (A\cup B)\setminus C & A\setminus C & B\setminus C & (A\setminus C)\cup (B\setminus C)\\ \hline \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 1 & 0 & 1 & 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 0 & 1 & 1 & 1 & 0 & \color{red}{1}\\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0\\ \hline 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \end{array}\]

\[ \begin{array}{|c||c|c|c|c|c|c|} \hline x & 1 & 3 & 9 & 27 & 81 & 243 \\ \hline \phantom{p} g(x) \phantom{p}&0 & 1 & 2 & 3 & 4 & 5 \\ \hline \phantom{p} h(x) \phantom{p}& 1.00 & 1.44 & 2.08 & 3.00 & 4.33 & 6.24 \\ \hline \end{array} \]

The Universal Set and the Empty Set

• The first is the {}, typically denoted \(U\). This set is all of the elements that we may choose from.

This set may be different from one setting to the next.

• For example one universal set may be the set of all real numbers, denoted \(\mathbb{R}\), whereas for another problem the universal set may be the whole numbers \(\{0, 1, 2,\ldots\}\).

• The other set that requires consideration is called the .

The empty set is the unique set is the set with no elements. We write this as \(\{ \}\) and denote this set by \(\emptyset\).

Finite Set

A set which contains a definite number of elements is called a finite set.

\[S=\{x|x \in N and 70 >x>50\}\]

Infinite Set

A set which contains infinite number of elements is called an infinite set.

\[S={x|x\in N and x>10}\]

Subset

A set X is a subset of set Y (Written as \(X \subseteq Y\)) if every element of X is an element of set Y.

Example 1 − Let, \(X={1,2,3,4,5,6}\) and Y={1,2}Y={1,2}. Here set Y is a subset of set X as all the elements of set Y is in set X.

Hence, we can write \(Y\subseteq X\).

Example 2 − Let, \(X={1,2,3}\) and \(Y={1,2,3}\). Here set Y is a subset (Not a proper subset) of set X as all the elements of set Y is in set X. Hence, we can write \(Y\subseteqX\).

Example

Let, \(X={1,2,3,4,5,6}\) and \(Y={1,2}\). Here set \(Y \subset X\) since all elements in \(Y\) are contained in \(X\) too and \(X\) has at least one element is more than set YY.

Universal Set

It is a collection of all elements in a particular context or application. All the sets in that context or application are essentially subsets of this universal set. Universal sets are represented as \(U\).

Example

We may define \(U\) as the set of all animals on earth. In this case, set of all mammals is a subset of \(U\), set of all fishes is a subset of \(U\), set of all insects is a subset of \(U\), and so on.

Empty Set or Null Set

An empty set contains no elements. It is denoted by \(\varnothing\). As the number of elements in an empty set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.

Example

\[S={x|x\in N \mbox{ and }7<x<8}=\varnothing\]

Another set which has a special letter to denote it is the set containing no elements. This is called the empty or null set and denoted by the symbol (D. Example 2.6 The set of integers m such that m2 = 5 is the empty set.

Singleton Set or Unit Set

Singleton set or unit set contains only one element. A singleton set is denoted by {s}{s}.

Example

\(S={x|x\in N, 7<x<9} = {8}\)

Equal Set

If two sets contain the same elements they are said to be equal.

Example

If A={1,2,6}A={1,2,6} and B={6,1,2}B={6,1,2}, they are equal as every element of set A is an element of set B and every element of set B is an element of set A.

Equivalent Set

If the cardinalities of two sets are same, they are called equivalent sets.

Example

If A={1,2,6}A={1,2,6} and B={16,17,22}B={16,17,22}, they are equivalent as cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3|A|=|B|=3

Overlapping Set

Two sets that have at least one common element are called overlapping sets.

In case of overlapping sets −

\[n(A\cupB)=n(A)+n(B)−n(A\cap B)\] \[n(A\cupB)=n(A−B)+n(B−A)+n(A\cap B)\] \[n(A)=n(A−B)+n(A\cap B)\] \[n(B)=n(B−A)+n(A\cap B)\]

Example

Let, \(A={1,2,6}\) and \(B={6,12,42}\). There is a common element ‘6’, hence these sets are overlapping sets.

Complement and universal set

The universal set (if it exists), usually denoted U, is a set of which everything conceivable is a member. In pure set theory, normally sets are the only objects considered (unlike here, where we have also considered numbers, colours and books, for example); in this case U would be the set of all sets. (Non-set objects, where they are allowed, are called ‘urelemente’ and are discussed below.)

In the presence of a universal set we can define X′, the complement of X, to be \(U−X\). X′ contains everything in the universe apart from the elements of X. We could alternatively have defined it as

\[X′ = \{x | \tilde (x\in X)\}\] and U as the complement of the empty set.

{Equal and Equivalent Sets}

Difference between equal sets and equivalent sets

• Consider the sets {A} and {B} \[ \boldsymbol{A} = \{ 1,2,3,4,5,6 \} \] \[ \boldsymbol{B} = \{1,2,3,4,5,6 \} \]

• {A} and {B} are sets because their elements are precisely the .

Equal and Equivalent Sets

Difference between equal sets and equivalent sets

• Consider the sets {C} and {D} \[ \boldsymbol{C} = \{a,b,c,d,e,f\} \] \[ \boldsymbol{D} = \{3,4,5,6,7,8\} \]

• {C} and {D} are sets because the cardinality of both the sets is the same (i.e. 6.)

• However {C} and {D} are not equal, as they are comprised of different elements.

• Necessarily all equal sets are equivalent sets.

• But are equivalent sets equal sets?

• No, because equivalent sets are sets that have the cardinality but equal sets are sets that all their elements are precisely the .

Example:

• {X}={p,q,r} and {Y}={1,2,3} are equivalent sets
• {E} ={m,n,o,p} and {F}={m,n,o,p} are equal and equivalent sets

Partitioning of a Set

Partition of a set, say S, is a collection of n disjoint subsets, say \(P1,P2 \ldots Pn\) that satisfies the following three conditions :

• \(Pi\) does not contain the empty set.

\([Pi \neq {\varnothing} for all 0<i\leq n]\) * The union of the subsets must equal the entire original set.

\[P1 \cup P2 \cup \ldots \cup Pn=S\] * The Intersection of any two distinct sets is empty.

\[Pa \cap Pb={\varnothing}, for a\neq b where n\geq a,b\geq 0\]

Example

Let \(S={a,b,c,d,e,f,g,h}\)

• One probable partitioning is \({a},{b,c,d},{e,f,g,h}\)
• Another probable partitioning is \({a,b},{c,d},{e,f,g,h}\)

Power Set

Power set of a set S is the set of all subsets of S including the empty set. The cardinality of a power set of a set S of cardinality n is \(2^n\). Power set is denoted as \(P(S)\).

Example

For a set \(S={a,b,c,d}\) let us calculate the subsets

• Subsets with 0 elements : \(\{ \varnothing\}\) (the empty set)
• Subsets with 1 element : {a},{b},{c},{d}
• Subsets with 2 elements : {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}
• Subsets with 3 elements : {a,b,c},{a,b,d},{a,c,d},{b,c,d}
• Subsets with 4 elements : {a,b,c,d}

Hence, \[P(S)= {{\varnothing},{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c},{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}}\] \[|P(S)|=2^4=16\] Note: The power set of an empty set is also an empty set.

\(|P({\varnothing})|=2^0=1\)

Power set

The power set of X, \(P(X)\), is the set whose elements are all the subsets of X. Thus \[P(A) = \{ \{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}.\] The power set of the empty set \(P(\{\})\) = \(\{\{\}\}\).

Note that in both cases the cardinality of the power set is strictly greater than that of base set: No one-to-one correspondence exists between the set and its power set.

Power Sets

• Consider the set A where $ A = {w,x,y,z}$

• There are 4 elements in set A.

• The power set of A contains 16 element data sets.

\[ \mathcal{P}(A) = \{\{ x \}, \{ y \} \{\{ x,y \}, \{ w,y \}\} \]

• (i.e. 1 null set, 4 single element sets, 6 two -elements sets, 4 three element set and 1 four element set.)

Exercise

For the set \(Y = \{u,v,w,x\}\) , answer the questions from the previous exercise

Set theory and Boolean algebra

In set theory and Boolean algebra, De Morgan’s Laws are often stated as “Union and intersection interchange under complementation” which can be formally expressed as:

\[\overline{A \cup B}\equiv\overline{A} \cap \overline{B}\] \[\overline{A \cap B}\equiv\overline{A} \cup \overline{B}\] where:

• \(\overline{A}\) is the negation of A, the overline being written above the terms to be negated

• \(\cap\) is the intersection operator (AND)

• \(\cup\) is the union operator (OR)

• In propositional logic and boolean algebra, De Morgan’s laws are a pair of transformation rules that are both valid rules of inference.

• The rules allow the expression of conjunctions and disjunctions purely in terms of each other via negation.

The rules can be verbalized as:

• The negation of a conjunction is the disjunction of the negations.
• The negation of a disjunction is the conjunction of the negations.

or informally as:

and also,

``not (A or B)” is the same as “(not A) and (not B)”

The rules can be expressed in formal language with two propositions P and Q as: \[ \neg(P\land Q)\iff(\neg P)\lor(\neg Q)\] \[\neg(P\lor Q)\iff(\neg P)\land(\neg Q)\] where:

• \(\neg\) is the negation operator (NOT)
• $$ is the conjunction operator (AND)
• \(\vee\) is the disjunction operator (OR)
• \(\leftarrow \rightarrow\) is a metalogical symbol meaning “can be replaced in a logical proof with”

Question 1

Describe the following set by the rules of inclusion method.

1. \(\{12,13,14,15,16,17\}\)

2. \(\{0,5,-5,10,-10,15,-15,.....\}\)

3. \(\{6,8,10,12,14,16,18\}\)

Question 2

Describe the following set by the listing method the set of positive multiples of 3 which are less than 20.

Question 3

Describe the following set by the listing method \[ \{ 2r+1 : r \in Z^{+} and r \leq 5 \} \]

Question 4

For each of the following sets, write out the set using the listing method. Also write down the cardinality of each set.

1. ${ 10^m : -2 m , m } $

2. $ { : 1 < n < 4, n } $

For each of the following sets, write out the set using the listing method. Also write down the cardinality of each set.

1. ${ s : s $ is an negative integer $ -10 s }$

2. ${ t : t $ is an even number $ 1 t }$

3. ${ u : u $ is a prime number $ 1 u }$

4. ${ v : v $ is a multiple of 3 $ 1 v }$

Question 4

Let \(A = \{2n+1 : n \in Z^{+}\}\) be a set of numbers. Describe the set \(A\) by the listing method.

Question 5

U = {natural numbers}; \(A = \{2, 4, 6, 8, 10\}\); \(B = \{1, 3, 6, 7, 8\}\). State whether each of the following is true or false:

1. \(A \subset U\)

2. \(B \subseteq A\)

3. \(\emptyset \subset U\)

Question 6

For each of the following sets, write out the set using the listing method. Also write down the cardinality of each set.

1. \(\{ s : \mbox{ s is an odd integer and } 2 \leq s \leq 10 \}\)

2. \(\{ 2m : m \in Z \mbox{ and }5 \leq m \leq 10 \}\)

3. \(\{ 2^t : t \in Z \mbox{ and } 0 \leq t \leq 5 \}\)

Question 1

Let \(A\) and \(B\) be subsets of universal set \(U\). Use the membership rule to prove that \[(A^\prime \cap B)^\prime = A \cup B^\prime\] Shade the region corresponding to this set on a Venn Diagram

• Given the universal set \[\mathcal{U} = {1,2,3,4,5,6,7,8,9}\] and the subsets \(A=\{1,3,5,7\}\) \(B = \{6,7,8,9\}\) list the set \(A^\prime \cap B)^\prime\)
• Shade in the following areas on Venn diagrams.

1. \(A^\prime\; \cup\; B\)

2. \(A \cap\; B^\prime\;\)

3. \((A \cap\; B)^\prime\;\)

4. \(A^\prime\; \cup\; B^\prime\;\)

5. \((A \cup\; B)^\prime\;\)

6. \(A^\prime\; \cap\; B^\prime\;\)

The following sets have been defined using the Building Method of notation. Re-write them by listing of the elements.

• \(\{p | p\) is a capital city, p is in Europe\(\}\)

• \(\{x | x = 2n - 5,\) x and n are natural numbers\(\}\)

• \(\{y | 2y^2 = 50,\) y is an integer\(\}\)

• \(\{z | z = n^3,\) z and n are natural numbers\(\}\)

Consider the universal set \(U\) such that \[U=\{1,2,3,4,5,6,7,8,9\} \] and the sets \[A=\{2,5,7,9\} \] \[B=\{2,4,6,8,9\} \]

1. \(A-B\)

2. \(A \otimes B\)

3. \(A \cap B\)

4. \(A \cup B\)

5. \(A^{c} \cap B^{c}\)

6. \(A^{c} \cup B^{c}\)

• Let A, B be subsets of the universal set \(\mathcal{U}\).

Use membership tables to prove De Morgan’s Laws.

*{2008 Zone A question 2a}

\(B = \{3n-1 :n \in Z^{+} \}\) Describe the set B using the listing method

• Let \(n=1\). Consequently \(3(1)-1 =2\)
• Let \(n=2\). Likewise \(3(2)-1 =5\)
• Let \(n=3\). $3(3)-1 = 8 $
• The repeated differences are 3. The next few values are 11, 14 and 17
• So by the listing method \(B= \{2,5,8,11,14,17,\ldots\}\)

\(A = \{3,5,7,9,ldots \}\)

---

Describe the set A using the rules of inclusion method

• The repeated differences are 2.
• We can say the rule has the form \(2n+k\)
• For the first value n=1. Therefore \(2+k=3\)
• Checking this , for the second value , n=2. Therefore \(4+k=5\)
• Clearly k = 1.
• \(A = \{2n+1 :n \in Z^{+} \}\)
• So by the listing method \(B= \{2,5,8,11,14,17,\ldots\}\)

Set Specification

*** 2008 Zone A question 2a***

\(B = \{3n-1 :n \in Z^{+} \}\) Describe the set B using the listing method

• Let \(n=1\). Consequently \(3(1)-1 =2\)
• Let \(n=2\). Likewise \(3(2)-1 =5\)
• Let \(n=3\). $3(3)-1 = 8 $
• The repeated differences are 3. The next few values are 11, 14 and 17
• So by the listing method \(B= \{2,5,8,11,14,17,\ldots\}\)

\(A = \{3,5,7,9,ldots \}\)

---

Describe the set A using the rules of inclusion method

• The repeated differences are 2.
• We can say the rule has the form \(2n+k\)
• For the first value n=1. Therefore \(2+k=3\)
• Checking this , for the second value , n=2. Therefore \(4+k=5\)
• Clearly k = 1.
• \(A = \{2n+1 :n \in Z^{+} \}\)
• So by the listing method \(B= \{2,5,8,11,14,17,\ldots\}\)