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}
Properties of Sets
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
Identity Laws
A∪∅=A
A∩U=A
Domination Laws
A∪U=U
A∩∅=∅
Idempotent Laws
A∪A=A
A∩A=A
Commutative Laws
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)
absorptive Laws
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=B∩C with
respect to an implicit universe
A−(B∩C)=(A−B)∪(A−C),
or r B∩C=B∪C 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}.