output.to from Sideway
Number Theory

Draft for Information Only

# Content

``` Set of Numbers  Collection of  Numbers  Set  Representation of Set   Roster or Tabular Form    Statement Form    Rule, Specification, Comprehension, Intension or Set Builder Form   Properties of Sets   Well-Definedness   Empty Set    Simple Set   Equality   Subset    Power Set    Universal Set    Cardinality    Set Partition   Relationships of Subsets     Theorem    Theorem    Theorem    Theorem   Set Operations   Union    Intersection    Difference    Complement   Properties of Set Operations     Identity Laws    Domination Laws    Idempotent Laws   Commutative Laws   Associative Laws   Distributive Laws   absorptive Laws   Complement Properties   Difference Properties   De Morgan's Lawsorgan's Laws   Subset Properties Ordered Set  n-Tuple  Cartesian Product```

## Set of Numbers

In general, number theory is the study of numbers, and in particular the study of the set of positive whole numbers. The concept of set  is one of the fundamental concept used in number theory to study the properties of number.

## Collection of  Numbers

Positive integers can be further grouped into different types of collections according to the area of interest.

• odd: 1,3,5, 7,9.11,13,...

• even: 2,4,6,8,10,12,14...

• prime: 2,3,5,7,11,13,17,19,23,29,31,...

• composite: 4,6,8,9,10,12,14,15,16,18,20...

• square: 1,4,9,16,25,36...

• cube: 1,8,27,64,125,216,...

• triangular: 1,3,610,15,21,28,36,45,...

• perfect: 6,28,496,8128,33550336,...

• Fibonacci: 1,1,2,3,5,8,13,21

• 0 (modulo 2): 2,4,6,8,10,12,14...

• 1 (modulo 2): 1,3,5, 7,9.11,13,...

### Set

Set is a general term given to name an unordered collection of objects with no rigorous definition on the concept of the set.  Although some special name are given to those sets with some typical properties, these objects are just defined as "belongs to", "is in", or "is a member of" a set. This approach is called "intuitive" or "naive" set theory as opposed to more rigorous "axiomatic" set theory.

Sometimes collection and aggregate have the same meaning with set. The objects in the set are called elements or members of a set. For example, a set with three elements a, b, and c; S= {a,b,c} then a is an element of set S; a∈S and d is not in set S; d∉S.

### Representation of Set

A set is a collection of distinct objects. A set can be considered as a single object if the set is well-defiend. For example, natural numbers are defined as all counting numbers, the set N used to represent the collection of all counting number is well-defined, N={1,2,3,4,...}. Elements are embreeded between two braces extensionally. A set can also be defined by specifying the properties intensionally. For example, S={x∈N:x>2} or {x∈N|x≠1,2}={x|x>2}={x:x≠1,2} since set N is intended and S⊆N

The three ways to represent a set are

• ### Roster or Tabular Form

Elements of a set are listed within a pair of braces {} and are usually separated by commas. For example, the set of natural numbers is N={1, 2, 3, 4, ...} in which elements in the list must not be repeated while order of elements in the list is immaterial. A listing form is unworkable for most sets whose elements cannot be listed easily.

• ### Statement Form

Elements of a set is expressed in term of a well-defined description for the whole set of elements and is given within a pair of braces {}. For example, the set of natural numbers is N={all positive integers}. Form is unworkable for most sets whose elements cannot be listed easily. A concise form is workable for most sets whose elements cannot be listed easily

• ### Rule, Specification, Comprehension, Intension or Set Builder Form

Elements of a set is defined in term of a well-defined rule, formula, or statement for an element of the set  and is given within a pair of braces {}. For example, the set of natural numbers is N={x:x is a positive integer}, N={x|x is a positive integer} where "x" is the representation of an element and ":" or "|" stand for "such that" . A precise form, or called set abstraction, is workable for sets whose elements can be defined precisely.

Besides of using a pair of braces, the notation for intervals of real numbers can also be used to represent some precise form of set abstraction for a set of real numbers in short.

[a,b]={x∈R:a≤x≤b}

[a,b)={x∈R:a≤x<b}

(a,b]={x∈R:a<x≤b}

(a,b)={x∈R:a<x<b}

• ### Well-Definedness

In order to use a set for representing a group of objects, the set of object in the set should be well-defined that it is always possible to determine whether a particular object belongs to the set or not. One typical example is the collections of self-referential objects. For example, S={x:x∉S}. The self-referential collections of objects is usually refered as Russell Paradox or Russell Antinomy.

• ### Empty Set

An empty set, ∅ or {} is a set has zero element in the set if ∀a[a∉∅].  ∅ and {∅} are two differents sets because set {∅} has one element namely ∅ in it.

• ### Simple Set

Besides the empty set, there are some simple set with a few elements in the set. A singleton set, or unit set, is a set has exactly one element in the set. For example, {a}, {∅}, and {{a} }. {∅} and ∅ are two differents sets because set {∅} has one element namely ∅ in it while ∅ has no element in it. A doubleton set, or unordered-pair, is a set has exactly two elements in the set. A tripleton set, or unordered triple, is a set has only three elements in the set. A quadrupleton set is a set has four elements in the set.

• ### Equality

Two sets are equal if and only if elements in two sets are the same. For example,  sets S and T are equal, S=T if and only if ∀a[a∈T↔a∈S].

• ### Subset

Elements in a set can also be grouped into a set. The set formed from a set is called a subset of a set. In other words, every element of the formed set is also in the original set. For example, a set T is a subset of a set S, T⊆S, if and only if  ∀a[a∈T→a∈S]. If T⊆S, and S⊆T, then two set must be equal, T=S since T⊆S, and S⊆T imply  ∀a[a∈T↔a∈S]. And if T≠S and T⊆S , then  T is a called a proper subset of S, T⊂S. A set has no element is the same meaning that the set has zero element in the set and therefore all sets have a subset without any element, ∅.

• ### Power Set

A power set, P(S), is the set of all subsets of a given set S, is also denoted by 2S. For example, P(∅)={∅} and P({∅})={∅,{∅}}.

• ### Universal Set

An universal set, U, is the set has all elements in the universe of discourse or in the domain, that is  ∀a[a∈U].

• ### Cardinality

The cardinality or size of a set, S, which is a finite set, is the number or size of elements contained in it and is denoted by |S|. For example, S={4,5,7,9}, |S|=4.  The cardinality of a set of integers, infinite set, is represented by ω and are said to be countably infinite, countable, or enumerable, if there is a bijection between the set and N, because their elements can be counted or place in correspondence with the integers. For example, |{all even numbers}|=ω. If the set is an infinite set and there is no such bijection, the set is said to be uncountably infinite.

• ### Set Partition

A set partition is the set of nonempty disjoint subset collection of a given set S with the union of all subset elements is S. For example, 𝒫(S)={S1, S2, S3,  ..., Si, ...}. where

• Si∉∅

• Si∩Sj=∅ for all i≠ j

• S=S1∪S2∪⋯∪Si∪⋯       , that is a∈S if  and only if a∈Si for some i.

## Relationships of Subsets

• ### Theorem

For an arbitrary set S,  S⊆U.

• ### Theorem

For an arbitrary set S,  ∅⊆S.

• ### Theorem

For an arbitrary set S,  S⊆S.

• ### Theorem

For an arbitrary set S of order |S|, the order of a power set or the number of subset of S is 2|S|.

### Set Operations

Although a set is usually defined by a definition, a set can also be produced by set operations.

• ### Union

The union of two sets, S and T is the set of all elements which are in set S, or in set T, or in both sets S and T and is denoted by S∪T. For example, S∪T={a:a∈S or a∈T}={a|a∈S ∨ a∈T}.

• ### Intersection

The intersection of two sets, S and T is the set of all elements which are common to both sets and is denoted by S∩T. For example, S∩T={a:a∈S and a∈T}={a|a∈S ∧ a∈T}. If S∩T=∅ then sets S and T are disjoint.

• ### Difference

The difference of a set S from a set T is the set of all elements which are elements that present in set S but the corresponding elements are not in set B and is denoted by S−T. For example, S-T={a:a∈S and a∉T}. In general, S−T and T−S are two different sets.

• ### Complement

The complement of a set S is usually defined as the difference of the universal set U from the set S in which the set of all elements which are elements present in set U but the corresponding elements are not in set S and is denoted by S or S'. For example, S={a:a∈U and a∉S}. If T⊆S, then the complement of T in S is defined as the difference of the set S from the set T. In other words, all elements of the complement of T are also member of set S but not a member of the set T. For example, S\T={a:a∈S and a∉T}.

## Properties of Set Operations

• A∪∅=A

• A∩U=A

• A∪U=U

• A∩∅=∅

• A∪A=A

• A∩A=A

• A∪B=B∪A

• A∩B=B∩A

• ### Associative Laws

• (A∪B)∪C=A∪(B∪C)

• (A∩B)∩C=A∩(B∩C)

• ### Distributive Laws

• A∪(B∩C)=(A∪B)∩(A∪C)

• A∩(B∪C)=(A∩B)∪(A∩C)

• A∪(A∩B)=A

• A∩(A∪B)=A

• ### Complement Properties

• A
=A

• B=A if and only if A∪B =U and A∩B=∅

• ### Difference Properties

• A∪(B−A)=(A∪B)

• A∩(B−A)=∅

• (A∪B)−((A−B)∪(B−A))=A∩B

• (A−C)∪(B−C)=(A∪B)−C

• (A−C)∩(B−C)=(A∩B)−C

• A∪(B−C)=(A∪B)−(C−A)

• A∩(B−C)=(A∩B)−(C−A)

• ### De Morgan's Lawsorgan's Laws

• A−(B∪C)=(A−B)∩(A−C), or B∪C=BC with respect to an implicit universe

• A−(B∩C)=(A−B)∪(A−C), or r B∩C=BC with respect to an implicit universe

• ### Subset Properties

• if A⊆B, then A∪B=B and A∩B=A

• A⊆A∪B

• A∩B⊆A

• if A⊆B and C⊆D, then A∪C⊆B∪D and A∩C⊆B∩D

## Ordered Set

Since the order of elements in a collection is sometime important also, a set of unordered element collection can not be used.

## n-Tuple

n-Tuple is a list or an ordered set of n elements. Sometimes n-tuple is also called ordered n-tuple. For example, (a1,a2,...,an) where a1 is the first element, a2 is the second element, and an is the nth element.

Therefore, two ordered n-tuples are equal if and only if two corresponding elements are equal. For example, (a1,a2,...,an) and (b1,b2,...,bn) are equal if and if ai=bi for i=1, 2,...,n.

## Cartesian Product

A Cartesian product is a mathematical operation. A Cartesian product of two ordered sets is the set of all ordered pairs from the corresponding elements of the two ordered sets. For example, A⨯B={(a,b)|a∈A^b∈B}.

Simiarly, the Cartesian product of the sets A1, A2, ..., An, is denoted by

A1⨯A2⨯...⨯An. And the Cartsian product is the set of ordered n-tuples (a1,a2,...,an) from the corresponding elements of the n ordered sets. For example, A1⨯A2⨯...⨯An={(a1,a2,...,an)|ai∈Ai for i=1, 2, ..., n}.

References

1. Paulo Ribenboim, 2000, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, New York
2. Kenneth H. Rosen, 2012, Discrete Mathematics and Its_Applications, McGraw-Hill, New York

ID: 131100005 Last Updated: 2018/6/3 Revision: 3 Ref:

Home (5)

Management

HBR (3)

Information

Recreation

Hobbies (7)

Culture

Chinese (1097)

English (336)

Reference (66)

Computer

Hardware (149)

Software

Application (187)

Digitization (24)

Numeric (19)

Programming

Web (644)

CSS (SC)

ASP.NET (SC)

HTML

Knowledge Base

Common Color (SC)

Html 401 Special (SC)

OS (389)

MS Windows

Windows10 (SC)

.NET Framework (SC)

DeskTop (7)

Knowledge

Mathematics

Formulas (8)

Number Theory (206)

Algebra (20)

Trigonometry (18)

Geometry (18)

Calculus (67)

Complex Analysis (21)

Engineering

Tables (8)

Mechanical

Mechanics (1)

Rigid Bodies

Statics (92)

Dynamics (37)

Fluid (5)

Control

Acoustics (19)

Biology (1)

Geography (1)