# 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 | edit source]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 | edit source]We can write some special relations involving sets using some symbols.

### Containment relations

[edit | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]#### Universal sets

[edit | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]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 | edit source]If P(S)=T, then |T|=2^{|S|}.

#### Problem set

[edit | edit source]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 | edit source]2. 2^{3}=8

4. {{},{1}}

## Set identities

[edit | edit source]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**