# Discrete Mathematics/Naive set theory

When we talk of **set theory**, we generally talk about *collections* of certain mathematical objects. In this sense, a *set* can be likened to a bag, holding a finite (or conceivably infinite) amount of things. Sets can be sets of sets as well (bags with bags in them). However, a set cannot contain duplicates -- a set can contain only one copy of a particular item.

When we look at sets of certain types of numbers, for example, the natural numbers, or the rational numbers, for instance, we may want to speak only of these sets. These collections of numbers are, of course, very important, so we write special symbols to signify them.

We write sets in curly brackets -- { and }. We write all of the *elements*, or what the set contains, in the brackets, separated by commas. We generally denote sets using capital letters.

For example, we write the set containing the number 0 and the number 1 as {0,1}. If we wish to give it a name, we can say B={0,1}.

## Special sets[edit]

The aforementioned collections of numbers, the naturals, rationals, etc. are notated as the following:

- the
*natural*numbers are written

- {0,1,2,...}

- the
*integers*are written

- {0,1,-1,2,-2,...}

- the
*rational*numbers are written

- {0,1,1/2,1/3,...,2,2/3,2/4,...}

- the
*real*numbers are written

- {0,,,,...}

Here we will generally write these in standard face bold instead of the doublestruck bold you see above. So we write here **N** instead of (NB following Wikipedia conventions).

## Notations[edit]

We can write some special relations involving sets using some symbols.

### Containment relations[edit]

To say that an element is in a set, for example, 3 is in the set {1,2,3}, we write:

We can also express this relationship in another way: we say that 3 is a *member* of the set {1,2,3}. Also, we can say the set {1,2,3} *contains* 3, but this usage is not recommended as it is also used to refer to subsets (see following).

We can say that two sets are equal if they contain exactly the same elements. For example, the sets {2,3,1} and {3,1,2} both contain the numbers 1, 2 and 3. We write:

We write the set with *no* elements as , or {}. Here, we use the notation {} for the *empty set* (NB following Wikipedia conventions).

### The concept of the subset[edit]

A very important concept in set theory and other mathematical areas is the concept of the **subset**.

Say we have two sets A={0,1,2,3,4,5,6,7,8,9}, and B={0,1,2,3,4,5}.
Now, B *contains some elements* of A, but not all. We express this relationship between the sets A and B by saying B is a *subset* of A.
We write this

If B is a subset of A, but A is not a subset of B, B is said to be a *proper subset* of A.
We write this

Note that if , then

### Intersections and unions[edit]

There are two notable and fundamental special operations on sets, the *intersection* and the *union*. These are somewhat analogous to multiplication and addition.

#### Intersection[edit]

The intersection of two sets A and B are the elements *common* to both sets.
For example, if A={1,3,5,7,9} and B={0,1,3}, their intersection, written is the set {1,3}.

If the intersection of any two sets are empty, we say these sets are *disjoint*.

#### Unions[edit]

The union of two sets A and B are the *all* elements in *both* sets. For example if A={1,3,5,7,9} and B={0,2,4,6,8}. We say the union, written is the set {0,1,2,3,4,5,6,7,8,9}.

### Set comprehensions[edit]

When we write 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 the elements can be too unwieldy. 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;

where rule can be something like *x*^{2}, or *x*=3*x*.

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

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

### Universal sets and complements[edit]

#### Universal sets[edit]

When we do work with sets, it is useful to think of a larger set in which to work with. 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 a *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[edit]

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, that is the complement of A is:

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

### Problem set[edit]

Based on the above information, write the answers to the following questions (Answers follow to even numbered questions)

- Is ?
- Is ?
- Is ?
- True or false? If false, give an example of an element in the first set which is not in the second.
- True or false? If false, give an example of an element in the first set which is not in the second.
- Is ?
- Is ?
- Write the 5 elements of
- Write the elements of
- Find a universal set such that these sets are subsets thereof:
- Given , find A' given

#### Answers[edit]

2. No, the square root of 2 is *irrational*, not a rational number

4.1. Yes

4.2. No

6. Yes.

8. 5 elements could be {3,5,7,9,11}.

10.

## Further ideas[edit]

These mentioned concepts are not the only ones we can give to set theory. Key ideas that are not necessarily given much detail in this elementary course in set theory but later in abstract algebra and other fields, so it is important to take a grasp on these ideas now.

These may be skipped.

### Power set[edit]

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

**all**sets.

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

### Cardinality[edit]

The *cardinality* of a set, denoted |S| is the amount 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[edit]

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

#### Problem set[edit]

Based on the above information, write the answers to the following questions. (Answers follow to even numbered questions)

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

#### Answers[edit]

2. 2^{3}=8

4. {{},{1}}

## Set identities[edit]

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:

how can we simplify this?

Several of the following set identities are similar to those in standard mathematics

**This is incomplete and a draft, additional information is to be added**