| Line 29: | Line 29: | ||
• <math>\mathbb{Z}_{n}</math> : the set of modulo <math>n</math> | • <math>\mathbb{Z}_{n}</math> : the set of modulo <math>n</math> | ||
| + | |||
| + | ='''Logarithm'''= | ||
| + | |||
| + | • <math>\log</math> : base 2 | ||
| + | |||
| + | • <math>\ln</math> : base <math>e</math> | ||
| + | |||
| + | ='''Partition'''= | ||
| + | |||
| + | • A set <math>\mathcal{A}=\left\{ A_{1},A_{2},\cdots,A_{k}\right\}</math> of disjoint subsets of a set <math>A</math> is a partition of <math>A</math> if <math>A=\bigcup_{i=1}^{k}A_{i}</math> and <math>A_{i}\neq\varnothing</math> for every <math>i</math> . | ||
| + | |||
| + | • Another partition <math>\left\{ A'_{1},A'_{2},\cdots,A'_{l}\right\}</math> of <math>A</math> refines the partition <math>\mathcal{A}</math> if <math>A'_{i}</math> is contained in some <math>A_{j}</math> . | ||
| + | |||
| + | '''<math>k</math> -sets and <math>k</math> -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. | ||
Revision as of 12:27, 16 November 2010
Contents
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.
