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

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

• the natural numbers are written $\mathbb {N}$

{0,1,2,...}

• the integers are written $\mathbb {Z}$

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

• the rational numbers are written $\mathbb {Q}$

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

• the real numbers are written $\mathbb {R}$

{0,$-{\sqrt {2}}$,${\sqrt {2}}$,$\pi$,...}

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 $\mathbb {N}$ (NB following Wikipedia conventions).

Notations

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

Containment relations

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

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

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:

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

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

The concept of the subset

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

$B\subseteq A$

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

$B\subset A$

Note that if $B\subset A$, then $B\subseteq A$

Intersections and unions

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

Intersection

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 $A\cap B$ is the set {1,3}.

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

Unions

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 $A\cup B$ is the set {0,1,2,3,4,5,6,7,8,9}.

Set comprehensions

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;

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

where rule can be something like x², or x=3x.

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

$\{x\in \mathbb {N} |x\mod 2=0\}$

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

$\{x\in \mathbb {C} |ax^{2}+bx+c=0\}$

Universal sets and complements

Universal sets

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 ${\mathcal {E}}$, however it may be simpler to denote this as E.

Complements

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:

$\{x\in {\mathcal {E}}|x\not \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 (Answers follow to even numbered questions)

1. Is $3/4\in \mathbb {Q}$?
2. Is ${\sqrt {2}}\in \mathbb {Q}$?
3. Is $\{x\in \mathbb {N} |2x\}=\{x\in \mathbb {N} |{x \over 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} \subset \mathbb {Z}$
   2. $\mathbb {Q} \subset \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. $\mathbb {R} \subset \mathbb {Q}$
   2. $\mathbb {Z} \subset \mathbb {R}$
6. Is $\{1,2,3\}\subset \{1,2,3,4\}$?
7. Is $\{1,2,3,5\}\subseteq \{1,2,3,4\}$?
8. Write the 5 elements of
   $\{x\in \mathbb {Z} |x-3\mod 2=0\}$
9. Write the elements of
   $\{x\in \mathbb {C} |x^{2}+4x-3=0\}$
10. Find a universal set such that these sets are subsets thereof: $\{x\in \mathbb {Z^{+}} |a=x^{2}and\ {\sqrt {a}}\in \mathbb {N} \},\{x\in \mathbb {N} |x/3\}$
11. Given ${\mathcal {E}}=\{0,1,2,3,4,5,6,7,8,9\}$, find A' given $A={1,4,7,9}$

Answers

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. ${\mathcal {E}}=\mathbb {Q}$

Further ideas

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

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

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

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

Problem set

Based on the above information, write the answers to the following questions. (Answers follow to even numbered 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

2. 2³=8
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)'\cap B'\cap A$

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