Set Theory#

Definitions#

Domain of Discourse#

Definition: The domain of discourse is subject matter we are treating.

Elements#

Symbolic Expression

$x,y,x$ (lowercase letters)

$x_1, x_2, ... , x_n$ (lowercase letters with subscripts)

Definition

The individuals, or objects, in the domain of discourse; The “things” being counted.

Sets#

Symbolic Expression

$A,B,C$ (upper case letters)

$A_1, A_2, ... , A_n$ (uppercase letters with subscripts)

Definition

Groups of elements that share a common property.

Note

Sets are sometimes referred to as classes or collections.

Cardinality#

Symbolic Expression: $n(A)$
Definition: The number of distinct elements in a set.

Universal Set#

Symbolic Expression: $S$
Definition: The universal set S is set of all elements in the domain of discourse.

Null Set#

Symbolic Expression: $\varnothing$
Definition: The unique set which contains nothing, i.e. no elements.

Natural Numbers#

Symbolic Expresison: $\mathbb{N}$
Definition: The set of all counting numbers starting at $1, 2, 3, ...$

Real Numbers#

Symbolic Expression: $\mathbb{R}$
Definition: The set of all decimal numbers, $1, 1.01, 1.001, ...$

Notation#

List Notation#

$A = \{ a, b, c, ... \}$

In list notation, all of the elements that belong to A are explicitly written between a pair of brackets with commas separating each element.

Quantifier Notation#

$A = \{ \forall x: F(x) \}$

In quantifier notation, all of the elements that belong to A are implicitly written between a pair of brackets with a formula that specifies the conditions for membership.

Quantifier notation is sometimes referred to as set builder notation.

Corollaries#

$n(\varnothing)=0$

The number of elements in the null set (the cardinality of the null set) is 0.

$\forall x: x \notin \varnothing$

Nothing belongs to the null set

$\forall x: x \in S$

Everything belongs to the unverisal set

Venn Diagrams#

A Venn Diagram is a visual representation of sets and the relations between them. The universal set is represent as rectangle and sets are represented as circles within this rectangle. The simplest Venn Diagram is a graphic of a single set A shown against the universal set S,

You will sometimes set Venn Diagrams with the elements of the sets written in, as in the following picture,

../../_images/sets_simple_with_elements.jpg

Venn Diagrams are useful for visualizing Relations. For this reason, we will see more complex examples of Venn Diagrams in the next section.

Relations#

Subset#

A is a subset of B if all of A’s elements are contained in B.

To say the same thing in a different way, if the element x belongs to A, then the element x also belongs to B

$\forall x : x \in A \implies x \in B$

The relation of subset can be seen in the following Venn Diagram,

This diagram represents the relationship $A \subseteq B$ .

Proper Subset#

A is a subset of B and $A \neq B$ . To say the same thing in a different way, A is wholly contained in B.

$\forall x: x \in A \implies x \in B \text{ and } A \neq B$

An equivalent way of defining a proper subset is given by,

$\forall x: x \in A \implies x \in B \text{ and } n(A) < n(B)$

This is an equivalent formulation because saying cthe cardinality of A is less than the cardinality of B and all members of A are members of B” is logically equivalent to saying “A is not identical to B and all members of A are members of B”.

Equivalence#

Two sets A and B are equivalent if the number of elements in A is equal to the number of elements B, i.e.,

$n(A) = n(B) \implies A \equiv B$

Equality#

Two sets A and B are equal if they contain the same elements. In other words, two sets are equal if they are the same set.

$\forall x: x \in A \implies x \in B \text{ and } x \in B \implies x \in A$

An equivalent way of defining the equality of sets is given by,

$A \subseteq B \text { and } B \subseteq A$

In other words, if A is wholly contained in B and B is wholly contained in A, then the only way this can occur is if $A = B$ .

Equality is a stricter condition than equivalence. Two sets that are equal are equivalent, but two sets that equivalent are not necessarily equal. Consider the sets,

$A = \{ \text{dog}, \text{cat} \}$

$B = \{ \text{Vietnam War}, \text{Russo-Japanese War} \}$

Both of these sets are equivalent because $n(A) = n(B) = 2$ , but they are not equal. If we add C to the mix,

$C = \{ \text{cat}, \text{dog} \}$

Then not only do we have $n(A) = n(C) = 2$ , but we also have $C = A$ , since they both contain the same elements.

In order words, from equality we can infer equivalence, but from equivalence, we cannot infer equality.

$A = B \implies A \equiv B$

$A \equiv B \not \Rightarrow A = B$

Operations#

Complement#

The set containing elements that do not belong to the set A.

$A^c = \{ \forall x: x \notin A \}$

The complement can be visualized with the following Venn Diagram,

Tip

The complement of a set corresponds to the English word “not”.

Example

Let S be the set of animals and let A be the set of dogs. Then $A^c$ is the set of animals that are not dogs.

Note

The complement is always taken relative to the universal set. In other words, you cannot find the complement if you do not have the universal set.

Example

$S = \{ \text{ red }, \text{ blue }, \text{ green } \}$

$A = \{ \text{ blue } \}$

$A^c = \{ \text{ red }, \text{ green } \}$

Union#

The set containing elements that belong to either the set A or the set B.

$A \cup B = \{ \forall x: x \in A \text{ or } x \in B \}$

We have to be careful with Venn Diagrams that represent unions, because the two sets A and B might have elements in common, or they may not have elements in common.

The first case, where the two sets have no elements in common is shown below,

The union would be represented by both circles. Notice the circles do not touch. Sets that have no elements in common are called disjoint.

The second case, where the two sets have elements in common is shown in the next diagram,

../../_images/sets_union_overlapping.jpg

The union would be represented by the entire area of both circles. Notice the circles share some elements in this case. Sets that have elements in common, but are not subsets in either direction (i.e. neither $A \subseteq B$ nor $B \subseteq A$ ), are called overlapping.

Tip

The union of two sets corresponds to the English “or”.

Example

Let A be the set of calculators. Let B represent the set of pencils. Then $A \cup B$ represents the set of calculators or pencils.

Example

$A = \{ a, b, c \}$

$B = \{ b, c, d \}$

$A \cup B = \{ a, b, c, d \}$

Intersection#

The set containing elements that to both the set A and the set B.

$A \cap B = \{ \forall x: x \in A \text{ and } x \in B \}$

As in the union, there are two cases we need to consider when representing the interesection of two sets with a Venn Diagram. Either the sets have elements in common, or they do not.

The first case, where the two sets have elements in common is shown in the next diagram,

The intersection is represented by where the circles meet. In the case of overlapping sets, this is non-empty,

$A \cap B \neq \varnothing$

The second case, where the two sets have no elements in common is shown below,

The intersection is represented by where the circles meet. In the case of disjoint sets, the circles do not meet. Thus,

$A \cap B = \varnothing$

Tip

The intersection of two sets corresponds to the English “and”.

Example

Let A be the set of United States Senators. Let B the set of people over the age of 70. Then, $A \cap B$ represents the set of people who are both United States Senators and over the age of 70.

**Example **

$A = \{ a, b, c \}$

$B = \{ b, c, d \}$

$A \cap B = \{ b, c \}$

Difference#

TODO

The operation of subtracting a set $B$ from a set $A$ is equivalent to taking the intersection the sets $A$ and $B^c$ ,

$A - B = A \cap B^c$

Theorems#

All of the theorems of Set Theory can be proven in one of two ways:

By drawing a Venn Diagram of the sets in question and working out the relations between them graphically.
Writing example sets in List Notation and then applying the definitions of Operations to both sides of the equation.

Note

Most of the set theorems can be phrased in terms of sets, or in terms of cardinalities. We can do this because all of the following theorems are theorems about equality of sets. Recall that from equality we can infer equivalence,

$A = B \implies A \equiv B$

This will be important when we apply these ideas to Probability. For this reason, we will give two versions of each theorem, when possible. One version will be phrased in terms of sets and the other version will be phrased in terms of cardinalities.

Basic Theorems#

Zero Property of Intersections#

The intersection of any set A with the empty set is the empty set.

Note

Notice the resemblance to zero property of multiplication,

$a \cdot 0 = 0$

Zero Property of Unions#

The union of any set A with the empty set is itself.

Note

Notice the resembalnce to the identity property of addition,

$a + 0 = a$

Identity Property of Intersections#

The intersection of any set A with the universal set is itself.

Note

Notice the resemblance to the identity property of multiplication,

$a \cdot 1 = a$

Identity Property of Unions#

The union of any set A with the universal set is the universal set.

Note

This theorem does not have an analogous algebraic property. This is where set theory starts to diverge from ordinary algebra.

Theorem 5#

Symbolic Expression: $A \cup A = A$

The union of any set A with itself is itself.

Theorem 6#

Symbolic Expression: $A \cap A = A$

The intersection of any set A with itself is itself.

Subset Theorems#

Theorem 1#

Symbolic Expression: $A \cap B \subseteq A$

Or equivalently,

$n(A \cap B) <= n(A)$

The intersection of A and B is a subset of A.

Theorem 2#

Symbolic Expression: $A \subseteq A \cup B$

Or equivalently,

$n(A) <= n(A \cup B)$

A is a subset of the union of A and B.

Theorem 3#

Symbolic Expression: $A \cap B \subseteq A \cup B$

Or equivalently,

$n(A \cap B) <= n(A \cup B)$

The intersection of two sets A and B is a subset of the union of those same two sets.

Theorem 4#

Symbolic Expression: $A \subseteq B \implies A \cap B = A$

Or equivalently,

$A \subseteq B \implies n(A \cap B) = n(A)$

If A is a subset of B, then the intersection of A and B is equal to A.

The hypothesis of this theorem, that A is a subset of B, cannot be written simply in terms of cardinalities. To see why, consider the sets,

$A = \{ \text{red}, \text{blue}, \text{yellow} \}$

$B = \{ \text{red}, \text{blue} \}$

$C = \{ \text{orange}, \text{black} \}$

Here we have,

$B \subseteq A$

From this and the theorem taken together, we are able to infer the intersection of B and A is B,

$B \cap A = \{ \text{red}, \text{blue} \} = B$

If we try to apply the same logic to C and A, we run into a problem. Namely,

$C \nsubseteq A$

However, we do have,

$n(C) <= n(A)$

But this doesn’t help us, because from it, we cannot infer,

$n(C \cap A) = n(C)$

In fact, not only can we not infer it, it’s not true. In this example,

$C \cap A = \varnothing$

So,

$n(C \cap A) = 0$

Whereas,

$n(A) = 3 \neq 0$

The lesson here is: the relation of “less than or equal to” between cardinalities does not equate to the relation of “subset of” between two sets. While the concepts are related, this theorem illustrates they must regarded as separate ideas.

Theorem 5#

$A \subseteq B \implies A \cup B = B$

If A is a subset of B, then the union of A and B is equal to B

Law of Syllogism#

$A \subseteq B \text{ and } B \subset C \implies A \subseteq C$

If A is a subset of B and B is a subset of C, then A is a subset of C.

Note

Refer to the Knowledge section for more details on syllogisms.

Complement Theorems#

Law of Double Negation#

$(A^c)^c = A$

The complement of a set A’s complement is the set a.

Tip

If a crayon isn’t not red, then it is red.

Example

$S = \{ 1, 2, 3 \}$

$A = \{ 1, 2 \}$

$A^c = \{ 3 \}$

$(A^c)^c = \{ 1, 2 \}$

Law Of Excluded Middle#

The union of a set A with its complement is the universal set.

Example

$S = \{ \text{ heads }, \text{ tails } \}$

$A = \{ \text{ heads } \}$

$A^c = \{ \text{ tails } \}$

$A \cup A^c = \{ \text{ heads }, \text{ tails } \} = S$

Law of Non-Contradiction#

The intersection of a set A its complement is the empty set.

Example

$S = \{ \text{jack}, \text{queen}, \text{king}, \text{ace} \}$

$A = \{ \text{jack}, \text{queen}, \text{king} \}$

$A^c = \{ \text{ace} \}$

$A \cap A^c = \{ \} = \varnothing$

Counting Theorems#

Law of Unions#

The number of elements in A or B is equal to the number of elements in A plus the number of elements in B, minus the elements A and B have in common.

This is another theorem most easily understood by considering the following venn diagram,

The area encompassed by both circles is the union $A \cup B$ . The overlap in the circles is intersection $A \cap B$ .

Consider how we count up elements in A or B. We first count up the elements in A, including the elemetns in the overlap. We then count up the elements in B, which includes the overlap again. In other words, by calculating $n(A) + n(B)$ , we have counted up the elements in $A \cap B$ twice. To fix this overcount, we need to subtract the number elements of in $A \cap B$ . Whence we arrive at the theorem.

Example

$A = \{ \text{ google }, \text{ facebook }, \text{ apple } \}$

$n(A) = 3$

$B = \{ \text{ banana }, \text{ apple } \}$

$n(B) = 2$

Note, when the elements of A are totaled, apple is counted once. When the elements of B are totaled, the element apple is counted again. We have thus doubled-counted this element, which is exactly the intersection $A \cap B$ ,

$A \cap B = \{ text{ apple } \}$

$n(A \cap B) = 1$

$A \cup B = \{ \text{ google }, \text{ facebook }, \text{ apple }, \text{ banana } \}$

$n(A \cup B) = 4$

$n(A) + n(B) - n(A \cap B) = 2 + 3 - 1 = 4$

Law of Complements#

The number of elements in any set A plus the number of elements in its complement is equal to the number of elements in the univeral set.

This theorem follows from the venn diagram of a set with its complement,

It can proved formally as follows,

Proof

By Complement Theorem 3,

$A \cap A^c = \varnothing$

By definition,

$n(\varnothing) = 0$

So, it follows,

$n(A \cap A ^c) = 0$

By Counting Theoreom 1,

$n(A \cup A^c) = n(A) + n(A^c) - n(A \cap A^c)$

But, as noted, the last term on the righthand side of this equation is 0, so

$n(A \cup A^c) = n(A) + n(A^c)$

On the other hand, by Complement Theorem 2,

$A \cup A^c = S$

So, it follows,

$n(A \cup A^c) = n(S)$

Putting it altogether,

$n(S) = n(A) + n(A^c)$

Aristotle’s Square of Opposition#

The square of opposition is a famous logical device for remembering how different propositions involving sets are related to one another. To be more specific, the square of opposition shows how negation affects sets. Before we show you the square of opposition, let us take a look at the logic behidn it.

In ordinary first-order logic, the negation of proposition simply means negating its truth value. For example, the negation of the proposition,

p = it is raining

Can be found by inserting the word “not”,

~ p = it is not raining

However, when we are talking about sets, it is more complicated, because we must quantify over which elements in the set proposition is true.

Derivation#

Consider the algebraic proposition,

$2 \cdot x = x + x$

This type of statement is obviously true no matter what we insert for x. Whatever number we plug into the equation, a true statement will always result. Symbolically, we can express this idea with the $\forall$ symbol,

$\forall x \in \mathbb{R}: 2 \cdot x = x + x$

We read this is as, “for all x, doubling x is equal to adding x twice”.

Contrast this against the proposition,

$2x + 1 = 5$

We are not free to plug just any value of x into this equation. Only a particular value of x will satisfy it, i.e. make it true (in this case $x = 2$ ). Anything else we plug into the equation will result in a contradiction, a statement that is obviously not true (try plugging in $x = 3$ and see what you get). We can express this idea with the $\exists$ symbol,

$exists x \in \mathbb{R}: 2x + 1 = 5$

We read this as, “there exists an x such that $2x +1 = 5$ ” or “some x satisifies $2x + 1 = 5$ .

When dealing with sets, we have two types of propositions to consider, universal propositions, denoted by the $\forall$ symbol, and existential propositions, denoted by the $\exists$ symbol.

Then, in order to understand negation with respect to sets, we must answer to questions:

How do we negate a universal proposition?

How do we negate an existential proposition?

In order to answer these question, we have to break each case into two further cases: the positive case and the negative case.

For universal propositions: In the positive case, we take a universal proposition that asserts something of all elements in a set. In the negative case, we take a universal proposition that denies something of all elements in a set.

For existential propositions: In the positive case, we take an exisential proposition that asserts something of some element in a set. In the negative case, we take an existential proposition that denies something of some element in a set.

Universal Positive Case#

Consider the proposition

All dogs are brown.

In order to show this proposition is false, it would be sufficient to show at least one dog existed that was not brown. For, if all dogs are brown, then it cannot be the case there is one dog that is not brown. Therefore, the negation of this proposition is,

Some dog is not brown.

To express this symbollically, let D represent the set of dogs and let B represent the set of brown things. Then the first proposition can be represented as,

$\forall x \in D: x \in B$

Note

This is equivalent to saying,

$D \subseteq B$

In order to negate this, we must show there is some element in D that is not in B. In other words, we switch the $\forall$ to a $\exists$ and negate the proposition being quantified,

$\exists x \in D: x \notin B$

Thus, we arrive at the formal definition of the negativion of a universal affirmative proposition,

$( \text{ not } \forall x \in A: x \in B) \equiv (\exists x \in A: x \notin B)$

Universal Negative Case#

Consider the proposition,

Some cars are fast.

In order to negative this we must show all cars are not*fast. It is *not sufficient to show only some cars are not fast, because there may exist cars in the some we have not considered that may yet be fast, which would coincide with the truth of the original proposition. Therefore, the negation of this proposition is,

All cars are not fast.

To express this symbollically, let C be the set of all cars and let F be the set of all fast things. Then, the original proposition can be written with the $\exists$ symbol,

$\exists x \in C: x \in F$

To negate this, we switch the $\exists$ to a $\forall$ and negate the quantified proposition,

$\forall x \in C: x \notin F$

Thus, we arrive at the formal definition of the negation of a universal negative proposition,

$(\exists x \in C: x \in F) \equiv (\text {not} \forall x \in C: \notin F)$

Existential Positive Case#

TODO

Existential Negative Case#

TODO

Square of Opposition#

Finally, we come to the square of opposition, a visual device for remembering everything that has been covered in this section.

The square of opposition is constructed by first drawing a table,

	existential	universal
positive
negative

In the entries of this table, you draw Venn Diagrams that represent the intersection of the row and column. Putting the results together, we get the following picture,

Notice the diagonals of the picture, the line that connects the top left to the bottom right and the line that connects the top right to the bottom left, form the contradictory pairs of propositions, namely,

$\text{universal positive} \nrightarrow \text{existential negative}$

$\text{universal negative} \nrightarrow \text{existential positive}$

Set Theory

Contents

Set Theory#

Definitions#

Domain of Discourse#

Elements#

Sets#

Cardinality#

Universal Set#

Null Set#

Natural Numbers#

Real Numbers#

Notation#

List Notation#

Quantifier Notation#

Corollaries#

Venn Diagrams#

Relations#

Subset#

Proper Subset#

Equivalence#

Equality#

Operations#

Complement#

Union#

Intersection#

Difference#

Theorems#

Basic Theorems#

Zero Property of Intersections#

Zero Property of Unions#

Identity Property of Intersections#

Identity Property of Unions#

Theorem 5#

Theorem 6#

Subset Theorems#

Theorem 1#

Theorem 2#

Theorem 3#

Theorem 4#

Theorem 5#

Law of Syllogism#

Complement Theorems#

Law of Double Negation#

Law Of Excluded Middle#

Law of Non-Contradiction#

Counting Theorems#

Law of Unions#

Law of Complements#

Aristotle’s Square of Opposition#

Derivation#

Universal Positive Case#

Universal Negative Case#

Existential Positive Case#

Existential Negative Case#

Square of Opposition#