# 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

editThe 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

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

### Containment relations

editTo 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

editA 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

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

#### Intersection

editThe 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

editThe 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

editWhen 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

editWhen 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

editGiven 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

editBased 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

edit2. 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

editThese 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

editThe *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

editThe *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

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

#### Problem set

editBased 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

edit2. 2^{3}=8

4. {{},{1}}

## Set identities

editWhen 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**