# Set Theory

Naive set theory considers elementary properties of the union and intersection operators -- Venn diagrams, the DeMorgan laws, elementary counting techniques such as the inclusion-exclusion principle, partially ordered sets, and so on. This is perhaps as much of set theory as the typical mathematician uses. Indeed, one may "construct" the natural numbers, real numbers, and so on in this framework.

We begin by introducing the notion of the *ordered pair*. If *a* and *b* are sets, then the *unordered pair* {*a*, *b*} is a set whose elements are exactly *a* and *b*. The â€œorderâ€ in which *a* and *b* are put together plays no role; {*a*, *b*} = {*b*, *a*}. For many applications, we need to pair *a* and *b* in a way making possible to â€œread offâ€ which set comes â€œfirstâ€ and which comes â€œsecond.â€ We denote this *ordered pair* of *a* and *b* by (*a*, *b*); *a* is the *first coordinate* of the pair (*a*, *b*), *b* is the *second coordinate*.

As any object of our study, the ordered pair has to be a set. It should be defined in such a way that two ordered pairs are equal if and only if their first coordinates are equal and their second coordinates are equal. This guarantees in particular that (*a*, *b*) â‰ (*b*,*a*) if *a* â‰ *b*.

Definition.(a,b) = {{a}, {a,b}}.

### 2. __Relations__

A binary relation is determined by specifying all ordered pairs of objects in that relation; it does not matter by what property the set of these ordered pairs is described. We are led to the following definition.

Definition.A setRis abinary relationif all elements ofRare ordered pairs, i.e., if for anyzâˆˆRthere existxandysuch thatz= (x,y).

It is customary to write *xRy* instead of (*x*, *y*) âˆˆ *R*. We say that *x is in relation R with y* if *xRy* holds.

The set of all *x* which are in relation *R* with some *y* is called the *domain* of *R* and denoted by â€œdom *R*.â€ So dom *R* = {*x* | there exists *y* such that *xRy*}. dom *R* is the set of all first coordinates of ordered pairs in *R*.

The set of all *y* such that, for some *x*, *x* is in relation *R* with *y* is called the *range* of *R*, denoted by â€œran *R*.â€ So ran *R* = {*y* | there exists *x* such that *xRy*}.

### 3. __Functions__

Function, as understood in mathematics, is a procedure, a rule, assigning to any object *a* from the domain of the function a unique object *b*, the value of the function at *a*. A function, therefore, represents a special type of relation, a relation where every object *a* from the domain is related to precisely one object in the range, namely, to the value of the function at *a*.

### 4. __Natural Numbers__

In order to develop mathematics within the framework of the axiomatic set theory, it is necessary to define natural numbers. We all know natural numbers intuitively: 0, 1, 2, 3, ..., 17, â€¦, 324, etc., and we can easily give examples of sets having zero, one, two, or three elements.

To define number 0, we choose a representative of all sets having no elements. But this is easy, since there is only one such set. We define 0 = Ã˜. Let us proceed to sets having one element (singletons): {Ã˜}, {{Ã˜}}, {{Ã˜, {Ã˜}}}; in general, {*x*}. How should we choose a representative? Since we already defined one particular object, namely 0, a natural choice is {0}. So we define

1 = {0} = {Ã˜}.

Next we consider sets with two elements: {Ã˜, {Ã˜}}, {{Ã˜}, {Ã˜, {Ã˜}}}, {{Ã˜}, {{Ã˜}}}, etc. By now, we have defined 0 and 1, and 0 â‰ 1. We single out a particular two-element set, the set whose elements are the previously defined numbers 0 and 1:

2 = {0,1} = {Ã˜, {Ã˜}}.

### 5. __Cardinality of Sets__

From the point of view of pure set theory, the most basic question about a set is: How many elements does it have? It is a fundamental observation that we can define the statement â€œsets *A* and *B* have the same number of elementsâ€ without knowing anything about numbers.

Definition.SetsAandBhavethe same cardinalityif there is a one-to-one functionfwith domainAand rangeB. We denote this by |A| = |B|.

Definition.The cardinality ofAis less than or equal to the cardinality ofB(notation: |A| â‰¤ |B|) if there is a one-to-one mapping ofAintoB.For example the cardinality of the set

{is3, 1, 2}3.

### 6. __Finite Sets__

Finite sets can be defined as those sets whose size is a natural number.

Definition.A setSisfiniteif it has the same cardinality as some natural numbernâˆˆ N. We then define |S| =nand say thatShas n elements. A set isinfiniteif it is not finite.

### 7. __Countable Sets__

Definition.A setSiscountableif |S| = |N|. A setSisat most countableif |S| â‰¤ |N|.

Thus a set *S* is countable if there is a one-to-one mapping of N onto *S*, that is, if *S* is the range of an infinite one-to-one sequence.

### 8. __Uncountable Sets____ :__

All infinite sets whose cardinalities we have determined up to this point turned out to be countable. Naturally, a question arises whether perhaps all infinite sets are countable. If it were so, this book might end with the preceding section. It was a great discovery of Georg Cantor that uncountable sets, in fact, exist. This discovery provided an impetus for the development of set theory and became a source of its depth and richness.

**9**.__Null Set:__

In mathematical sets, the null set, also called the empty set, is the set that does not contain anything. It is symbolized for { }. There is only one null set. This is because there is logically only one way that a set can contain nothing.

The null set makes it possible to explicitly define the results of operations on certain sets that would otherwise not be explicitly definable. The intersection of two disjoint sets (two sets that contain no elements in common) is the null set. For example:

{1, 3, 5, 7, 9...} Ã‡{2, 4, 6, 8, and 10...} = f

**10. Equality of sets:** Two sets are

**equal**if and only if they have the same elements.

More formally, for any sets

**and**

*A***, A**

*B***=**if and only if

*B***all the elements of A present in B.**

Thus for example **{ 1, 2, 3} = {3, 2, 1}**, that is the order of elements does not matter, and

**{**, that is duplications do not make any difference for sets.

*1, 2, 3*} = {*3, 2, 1, 1*} **11. Subset:** A set

**is a subset of a set**

*A***if and only if everything in**

*B***is also in**

*A***.**

*B*More formally, for any sets

**and**

*A***, A is a**

*B***subset**of

**, and denoted by**

*B*

*A***Ã**, if and only if

*B***all the elements of A are present in B**

If

*A***Ã**, and

*B*

*A***Â¹**, then

*B***is said to be a**

*A***proper subset**of

**and it is denoted by**

*B*

*A***ÃŒ**

*B*.For example **{ 1, 2} **

**Ã{**Also

*3, 2, 1*}.**{**

*1, 2*}**ÃŒ{**

*3, 2, 1*}.** 12. Universal set:**

__A set, which has all the elements in the universe of discourse, is called a universal set.__

Three subset relationships involving empty set and universal set are listed below as theorems without proof.

**Note** that the set ** A** in the next four theorems are arbitrary. So

**can be an empty set or universal set.**

*A***Theorem 1:** For an arbitrary set ** A**:

**Ã**

*A*

*U*.**Theorem 2:** For an arbitrary set ** A**: fÃ

*A*.**Theorem 3:** For an arbitrary set *A*** A** Ã

*A*.** 13.Power set:** The set of all subsets of a set ** A** is called the

**power set**of

**and denoted by**

*A***or**

*2*^{A}

**j(**

*A*) .For example for ** A = {1, 2}**,

**j (**

*A*) = {f, {*1*}, {*2*}, {*1, 2*} } .** Theorem 4:** For an arbitrary set ** A**, the number of subsets of

**is**

*A*

*2*.^{|A|}