Revision as of 12:28, 16 November 2010

1.1 Basic Mathematics

1.1.1 Mathematical notation

• ≈ : approximately equal

• ~ : CST ·

Supremum and infimum vs. maximum and minimum

The concept of supremum, or least upper bound, is as follows: Let $ S={a[n]} $, the sequence with terms $ a[0],a[1],\cdots $ over all the nonnegative integers. $ S $ has a supremum, called $ \sup S $ , if for every $ n , a[n]\leq\sup S $ (i.e. no a[n] exceeds $ \sup S $ ), and furthermore, $ \sup S $ is the least value with this property; that is, if $ a[n]\leq b $ for all $ n $, then $ \sup S\leq b $ for all such $ b $ . This is why the supremum is also called the least upper bound, for a bound is a number which a function, sequence, or set, never exceeds. Similarly, one can define the infimum $ \inf S $ , or greatest lower bound.

• Consider the set $ \left\{ x:\;0<x<1\right\} $ . There is no maximum or minimum, however $ 0 $ is the infimum and $ 1 $ is the supremum.

• Consider the set $ S={a[n]},\; a[n]=1/n $ where $ n $ is a positive integer.

– $ \sup S=1 $ , since $ 1/n>1/(n+1) $ for all such $ n $ , and so the largest term is the first. The maximum is also $ 1 $.

– $ \inf S=0 $ . However, the minimum does not exist.

Well-known sets

• $ \mathbb{N} $ : the set of natural numbers. It is countably infinite.

– $ \mathbb{N}_{0}=\left\{ 0,1,\cdots\right\} $

– $ \mathbb{N}^{*}=\mathbb{N}_{1}=\left\{ 1,2,\cdots\right\} $

• $ \mathbb{Z}_{n} $ : the set of modulo $ n $

Logarithm

• $ \log $ : base 2

• $ \ln $ : base $ e $

Partition

• A set $ \mathcal{A}=\left\{ A_{1},A_{2},\cdots,A_{k}\right\} $ of disjoint subsets of a set $ A $ is a partition of $ A $ if $ A=\bigcup_{i=1}^{k}A_{i} $ and $ A_{i}\neq\varnothing $ for every $ i $ .

• Another partition $ \left\{ A'_{1},A'_{2},\cdots,A'_{l}\right\} $ of $ A $ refines the partition $ \mathcal{A} $ if $ A'_{i} $ is contained in some $ A_{j} $ .

$ k $ -sets and $ k $ -subsets

• $ \left[A\right]^{k} $ is the set of all k -element subsets of A .

• Sets with k elements will be called k -sets.

• Similarly, subsets with k elements are k -subsets.