Discrete mathematics/Set theory

[[../Introduction/]] Template:Wikipedia

A set is a collection of objects. We can define a set by explicit enumeration of the objects that compose the set or by comprehension, stating a criterion for selection of eligible elements.

Enumeration definition of a set: $\{1,2,3,4\}\text{, }\{3,2,4,1\}\text{, or }\{1,2,2,2,3,4\}$ Because those all point to the same objects, they are the same set. Notice, sets only record what is pointed at, not how many times it is pointed at or in what order.

Comprehension definition of a set: The set of all even numbers:

$\{x\in \mathbb{N}|xmod2=0\}$

Set relations

We can make logic statements about the relationship between elements and a given set.

• An element belongs to a set;

  $4\in \{1,2,3,4\}$

We can also make statements about the relations between two given sets.

• Two sets are equal; they both contain exactly the same objects

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

• Set A is a superset of another set B. Set A contains all objects of set B. The definition is loose because A may contain more elements than B. It requires another relation, that of a strict superset.

  $\{1,2,3,4\}\supseteq \{1,2,3\}\text{ and }\{1,2,3,4\}\supseteq \{1,2,3,4\}$

• Set A is a strict superset of Set B. Set A contains all elements of set B and even more.

  set A = $\{1,2,3,4\}$

  set B = $\{1,2,3\}$

  $\{1,2,3,4\}\supset \{1,2,3\}$

• The subset and strict subset relations are the converses, in meaning and direction, of the superset and strict superset relations

  $\{1,2,3,4\}\subseteq \{1,2,3,4\}\text{ and }\{1,2,3\}\subset \{1,2,3,4\}$

The ⊂ symbol looks and acts similarly to the < symbol. The ∈ symbol looks like the first letter of "Element of a set" and has a middle line that ruins its similarity to the < symbol. Take care to avoid confusing the two.

Set operations

There are several ways to combine two sets into a third :

• We might unite the sets, pointing at all the things in both

  $\{1,2,3,4\}\cup \{2,4,6,8\}=\{1,2,3,4,6,8\}$

• We might intersect the sets, pointing at the few things that are common to both

  $\{1,2,3,4\}\cap \{2,4,6,8\}=\{2,4\}$

• We might find what is different about the first set, pointing out its unique qualities

  $\{1,2,3,4\}𝓃\{2,4,6,8\}=\{1,3\}\text{ or }\{1,2,3,4\}-\{2,4,6,8\}=\{1,3\}$

The ∪ symbol looks like the first letter of "Union" and like a cup that will hold a lot of items. The ∩ symbol looks like a spilled cup that won't hold a lot of items, or possibly the letter N, for intersection. Take care not to confuse the two.

Sets with their own symbols

Several sets are used so often, they are given special symbols.

• The empty set allows us to say we aren't pointing at anything; as useful to sets as zero is to numbers

  $\mathrm{\varnothing }=\{\}$

• The natural numbers

  $\mathbb{N}=\{1,2,3,\dots \}$

• The integers

  $\mathbb{Z}=\mathbb{N}\cup \{\dots ,-2,-1,0\}$

• The rational numbers

  $\mathbb{Q}=\mathbb{Z}\cup \{\dots ,-1/3,-1/2,1/2,1/3,\dots ,2/3,2/5,\dots \}$

• The real numbers

  $ℝ=\mathbb{Q}\cup \{\dots ,-\pi ,-\sqrt{2},\sqrt{2},\pi ,\dots \}$

• The complex numbers

  $ℂ=ℝ\cup \{i,1+i,1-i,\sqrt{2}+\pi i,\dots \}$

Except when a mathematical statement is on a line of its own, we will use bold (N) instead of blackboard bold ($\mathbb{N}$).

Set comprehension

When we write down a set, we can do so by writing all the elements in that set as above. However if we wish to write an infinite set, then writing out every single element of course becomes a problem. We can solve this problem by writing sets in set comprehension notation. We do this by writing these sets including a rule and by a relationship to an index set, say I. That is;

$S=\{x\in I|R\}$

where R is something like x²=0, or x=3t for an integer t. Such a rule is technically known as a boolean predicate on x, and we can read the whole mathematical statement as S is the set of all x's in I such that x squared equals zero.

For example, this set forms the set of all even numbers:

$\{x\in \mathbb{N}|xmod2=0\}$

This set forms the set of all solutions to the general quadratic:

$\{x\in ℂ|a{x}^2+bx+c=0\}$

Note that :

$\{x\in \mathbb{N}|a{x}^2+bx+c=0\}$

is a completely different set!

Venn Diagrams

A graphical representation of sets where some properties may be easily seen from the graphical overlays of 2 Dimensional shapes corresponding to sets and relationships between sets.

Intersection

Union

Subset

No overlap or the empty set is result of Set A Union Set B.

Universal sets and complements

Universal sets

When we do work with sets, it is useful to think of another, larger set, which we call the universal set or universe, and then work in that set. For example, if we are talking about sets {-1,0,1} and {-3,-1,1,3}, we may want to work in Z in this circumstance. When we talk about working in such a larger set, such as Z in that instance, we say that Z is the universal set, and we take all sets to be subsets of this universal set.

We write the universal set to be $ℰ$; however, it may be simpler to denote this as E.

Complements[1]

Given a set A in a larger universal set E, we define the complement of A to be all elements in E that are not in A. In other words, the complement of A is:

$\{x\in ℰ|x\in ̸A\}$

We write the complement as A' or A^c. In this document, we will use A'.

Problem set

Based on the above information, write the answers to the following questions:

1. Is $3/4\in \mathbb{Q}$?
2. Is $\sqrt{2}\in \mathbb{Q}$?
3. Is $\{2x|x\in \mathbb{N}\}=\{x|\frac{x}{2}\in \mathbb{N}\}$?
4. True or false? If false, give an example of an element in the first set which is not in the second.
   1. $\mathbb{N}\subseteq \mathbb{Z}$
   2. $\mathbb{Q}\subseteq \mathbb{Z}$
5. True or false? If false, give an example of an element in the first set which is not in the second.
   1. $ℝ\subseteq \mathbb{Q}$
   2. $\mathbb{Z}\subseteq ℝ$
6. Is $\{1,2,3\}\subset \{1,2,3,4\}$?
7. Is $\{1,2,3,5\}\subseteq \{1,2,3,4\}$?
8. Write 5 elements that could be in
   $\{x\in \mathbb{Z}|x-3\equiv 0(mod2)\}$
9. Write the elements of
   $\{x\in ℂ|x^2+4x-3=0\}$
10. Find a universal set such that these sets are subsets thereof: $\{x\in {\mathbb{Z}}^{\mathbb{+}}|a=x^2\text{and}\sqrt{a}\in \mathbb{N}\},\{x\in \mathbb{N}|x/3\}$
11. Given $ℰ=\{0,1,2,3,4,5,6,7,8,9\}$, find A' given $A=\{1,4,7,9\}$

Answers

1. Yes
2. No, the square root of 2 is irrational, not a rational number
3. Yes
4. 1. True
   2. False. For example, 1/2 is in Q but not Z.
5. 1. False, example: $\pi$
   2. True
6. Yes.
7. No.
8. 5 elements could be {3,5,7,9,11}.
9. { 0.64575, -4.6458}
10. $ℰ=\mathbb{Q}$
11. A' = {0,2,3,5,6,8}

Further ideas

These concepts are not the only ones in set theory. There are many more key ideas that are not given in much detail in this elementary course, but are important later in abstract algebra and other fields.It is useful to get a feeling for these ideas now.

These may be skipped.

Power set

The power set of some set S, denoted P(S), is the set of all subsets of S (including S itself). NB: The empty set is a subset of all sets.

For example, P({0,1})={{},{0},{1},{0,1}}

Cardinality

The cardinality of a set S, denoted |S|, is simply the number of elements a set has. So |{a,b,c,d}|=4, and so on. The cardinality of a set need not be finite: some sets have infinite cardinality.

The cardinality of the power set

If P(S)=T, then |T|=2^|S|.

This is because T contains sets representing all possible combinations of existence or nonexistence of the elements of P, meaning that each element can be in two states: in the subset, or not in the subset. Since the number of possible combinations of different states of objects is the multiple of all the number of possible states of each object, and since each element in P can have exactly two states for each subset of P(in the subset or not in the subset), it is therefore inferable that the number of subsets for P is 2^|S|.

Problem set

Based on the above information, write the answers to the following questions.

1. |{1,2,3,4,5,6,7,8,9,0}|
2. |P({1,2,3})|
3. P({0,1,2})
4. P({1})

Answers

1. 10

2. 2³=8

3. {{},{0},{1},{2},{0,1},{0,1,2},{0,2},{1,2}}

4. {{},{1}}

Set identities

When we spoke of the two fundamental operators on sets before, that of the union and the intersection, we have a set of rules which we can use to simplify expressions involving sets. For example, given:

$(A\cup B{)}^{\prime }\cap B^{\prime }\cap A$

how can we simplify this?

Several of the following set identities are similar to those in standard mathematics, such as associativity, distributivity, and so on.

Commutativity

$A\cup B=B\cup A$

$A\cap B=B\cap A$

Associativity

$A\cup (B\cup C)=(A\cup B)\cup C$

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

Distributivity

$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

Identity

$A\cup \{\}=A$

$A\cap ℰ=A$

Idempotency

$A\cup A=A$

$A\cap A=A$

Domination

$A\cap \{\}=\{\}$

$A\cup ℰ=ℰ$

Double complements

$(A^{\prime }{)}^{\prime }=A$

Complement intersections and unions

$A\cup A^{\prime }=ℰ$

$A\cap A^{\prime }=\{\}$

De Morgan's Laws

$(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$

$(A\cap B{)}^{\prime }=A^{\prime }\cup B^{\prime }$

These are laws rather than axioms because we can prove them from the other axioms.

Remember from above that two sets A and B are equal if $A\subseteq B$ and $B\subseteq A$. Let's prove them one by one.

1) $(A\cup B{)}^{\prime }\subseteq A^{\prime }\cap B^{\prime }$

Let's pick an element at random $x\in (A\cup B{)}^{\prime }$. We don't know anything about x, it could be a number, a function, or indeed an elephant. All we do know about x, is that

$x\in (A\cup B{)}^{\prime }$

so

$x\notin (A\cup B)$

because that's what complement means. Therefore

$x\notin A$ and $x\notin B$

by pulling apart the union. Applying complements again we get

$x\in A^{\prime }$ and $x\in B^{\prime }$

Finally, if something is in 2 sets, it must be in their intersection, so

$x\in A^{\prime }\cap B^{\prime }$

So, any element we pick at random from :$(A\cup B{)}^{\prime }$ is definitely in, $A^{\prime }\cap B^{\prime }$, so by definition

$(A\cup B{)}^{\prime }\subseteq A^{\prime }\cap B^{\prime }$

2) :$A^{\prime }\cap B^{\prime }\subseteq (A\cup B{)}^{\prime }$

This follows a very similar way. Firstly, we pick an element at random from the first set, $x\in A^{\prime }\cap B^{\prime }$

Using what we know about intersections, that means

$x\in A^{\prime }$ and $x\in B^{\prime }$

Now, using what we know about complements,

$x\notin A$ and $x\notin B$

If something is in neither A nor B, it can't be in their union, so

$x\notin A\cup B$

And finally

$x\in (A\cup B{)}^{\prime }$

So, now we've got both $(A\cup B{)}^{\prime }\subseteq A^{\prime }\cap B^{\prime }$ and $A^{\prime }\cap B^{\prime }\subseteq (A\cup B{)}^{\prime }$. After all our hard work and effort, we've finally proven the first of De Morgan's Laws:

$(A\cup B{)}^{\prime }=A^{\prime }\cap B^{\prime }$

The other half can be proven by the reader as an exercise.

Dualization

Notice that in the above rules, you will probably not have to remember all of the table. In fact, you will probably remember half of this table and change $\cup$ to $\cap$, and vice versa in some instances.

This is an important quality, and we say that each rule for unions is a dual of the rule for intersections. This is an important mnemonic in remembering the set identities.

In fact, we have just given the axioms of a Boolean algebra. See [[../Boolean algebra/]] for more.

Problem set

Based on the above information, simplify the set expressions in the following questions:

1. $(A\cup B{)}^{\prime }\cap C$
2. $((A\cup B)\cap (A\cup C))\cap ℰ$
3. $A\cup (B\cap (C^{\prime }\cup B^{\prime }))$
4. $(A^{\prime }\cup B{)}^{\prime }$

Answers

1. $A^{\prime }\cap B^{\prime }\cap C$

2. $A\cup (B\cap C)$

3. $A\cup (B\cap C^{\prime })$

4. $A\cap B^{\prime }$

Further operations on sets

The difference of 2 sets

The set $A\setminus B$, read as A minus B, contains all the elements of the set A that are not elements of set B. In other words:

$A\setminus B=A\cap B^{\prime }$

This can be handy in defining infinite sets, for instance the set of all non-zero integers can be written as $\mathbb{Z}\setminus \{0\}$. It should be obvious that $A\setminus B\ne B\setminus A$ and $A\setminus A=\{\}$

Concise notation for more than 2 sets

If we have the sets $A_1,A_2,\dots ,A_n$, we can talk about the generalized union -- or intersection -- of these sets, ie $A_1\cup A_2\cup A_3\dots \cup A_n$, which we write concisely

$\bigcup _{x=1}^n{A}_x$.

Similarly for intersections, we write:

$\bigcap _{x=1}^n{A}_x$.`

Cartesian product

The Cartesian product is an important concept when considering functions in the next section. Let us go over a key concept first.

n-tuples

An n-tuple is similar to a set, however the order the elements appear in is important. We write ordered sets with round brackets -- ( and ) instead of { and } to signify that the elements are ordered. Think of points in the plane -- written with round brackets. We know that the point (1,0) is not (0,1), but if we write it using set brackets, they will be. For example;

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

but

$(1,2,3)\ne (3,1,2)$

The Cartesian Product

The Cartesian Product of two sets is the set of all tuples made from elements of two sets. We write the Cartesian Product of two sets A and B as A × B. It is defined as:

$A\times B=\{(a,b)|a\in A\text{and}b\in B\}$

It may be clearer to understand from examples;

$\{0,1\}\times \{2,3\}=\{(0,2),(0,3),(1,2),(1,3)\}$

$\{a,b\}\times \{c,d\}=\{(a,c),(a,d),(b,c),(b,d)\}$

$\{0,1,2\}\times \{4,6\}=\{(0,4),(0,6),(1,4),(1,6),(2,4),(2,6)\}$

It is clear that, the cardinality of the Cartesian product of two sets A and B is:

$|A\times B|=|A||B|$

A Cartesian Product of two sets A and B can be produced by making tuples of each element of A with each element of B; this can be visualized as a grid (which Cartesian implies) or table: if, e.g., A = { 0, 1 } and B = { 2, 3 }, the grid is

×		A
		0	1
B	2	(0,2)	(1,2)
	3	(0,3)	(1,3)

A Cartesian product can also be produced in most programming languages with two nested for loops, or from a relational database by selecting from two tables without specifying a where clause.

Problem set

Based on the above information, answer the following questions:

1. {2,3,4}×{1,3,4}
2. {0,1}×{0,1}
3. |{1,2,3}×{0}|
4. |{1,1}×{2,3,4}|

Answers

1. {(2,1),(2,3),(2,4),(3,1),(3,3),(3,4),(4,1),(4,3),(4,4)}

2. {(0,0),(0,1),(1,0),(1,1)}

3. 3

4. 3

Russell's paradox

Let us consider a set

$A=\{X|X\text{set and}X\in ̸X\}$

The elements of A are themselves sets; A then is the set of sets that don't contain themselves as members.

What happens if we ask ourselves whether A is in A?

If we assume A is a member of A, because of the set rule we have that A is not in A, so,

If we assume A is not a member of A, because of the set rule, A is in A.

This is clearly contradictory! This paradox is known as Russell's paradox, and poses a problem to the set theory we have defined here.

This is where the differences between naive and [[../Axiomatic set theory/]] come in. Axiomatic set theory does not have this problem.

---

Previous topic:[[../Introduction/]]|Contents:Discrete mathematics|Next topic:[[../Functions and relations/]]