离散数学之集合与函数

集合

定义：

Set A is a collection of objects (or elements)

$a\in A$: a is an elements of A or a is a member of A
$a\notin A:$ a is not an element of A
$A={a_1,a_2,\cdots,a_n}$: A contains $a_1,a_2,\cdots,a_n$
Order of elements is meaningless（无序性）
It does not matter how often the same element is listed

集合等价

集合A和集合B是相等的，当且仅当它们囊括了相等的元素。

If $A={9,2,7,-3}$ and $B={7,9,2,-3}$, then $A=B$

if $A={9,2,-3,9,7,3}$ and $B={7,9,2,-3}$ ,then $A=B$ (因为A中实际上只有9，7，3，-3四个元素)

应用

Bag of words model: documents, reviews, tweets, news, etc;
Transactions: shopping list, app downloading, book reading, video watching, music listening, etc;
Records in a DB, data item in a data streaming, etc;
Neighbors of a vertex in a graph;

”Standard” sets

自然数：$N={0,1,2,3…}$
整数：$Z={…,-2,-1,0,1,2}$
正整数：$Z^+ = {1,2,3,4…}$
实数：$R={47.3,-12,-0.3,…}$
有理数：$Q={1.5,2.6,-3.8,15}$

集合的展现

Tabular form 表列式

$A={1,2,3,4,5}$

$B={-2,0,2}$

Descriptive form

A = set of rst ve natural numbers;
B = set of positive odd integers;

Set builder form

$Q={a/b: a\in Z\land b\in Z\land b\neq 0 }$

$B={y:P(y)}$,where $P(Y):y\in E\land 0 <y\leq 50$;

Remarks

$A = \empty$ empty set, or null set
Universal set U: contains all the objects under consideration
$A=\{\{a,b\},\{b,c,d\}\}$

Venn diagrams

In general, a universal set is represented by a rectangle.

子集

Set A is a subset of B is every element of A is also an element of B, denote as $A\subseteq B$

$A\subseteq B = \forall x(x\in A\rightarrow x\in B)$
对每一个集合 S，我们有 (1) $\empty \subseteq S$ (2) $S\subseteq S$
When we wish to emphasize that set A is a subset of set B but that $A\neq B$ ,we write $A\subset B$ and say that A is a proper subset of |B, i.e., $\forall x(x\in A\rightarrow x\in B)\land\exists(x\in B\land x\notin A)$
两个有用的结论： (1)$A=B\Leftrightarrow (A\subseteq B)\land (B\subseteq A)$ (2) $(A\subseteq B)\land(B\subseteq C)\Rightarrow (A\subseteq C)$
给定一个集合S，那S的幂集就是S所有的子集，我们记为 $P(s)$. 那么幂集的大小为 $2^{|S|}$, |S| 是 S 的size。

Cartesian product

给定两个集合 A和B。那么A和B的笛卡尔集，记为 $A\times B$ , 运算方法为 $A\times B = {(a,b):a\in A\land b\in B}$ , 其中 (a,b) 是有序对

Let A = {1,2} and B={a,b,c} the Cartesian product $A\times B = {(1,a),(1,b),(1,c),(2,a),(2,b),(2,c) }$
The Cartesian product of $A_1,A_2,…,A_n$ is denoted as $A_1\times A_2\times \dots \times A_n$

$A_1\times A_2\times \dots \times A_n = {(a_1,a_2,\cdots,a_n):\forall i~~a_i\in A_i }$

A subset R of the Cartesian product $A\times B$ is called a relation from A to B

集合操作

Union ： $A\cup B={x:x\in A\lor x\in B}$;
Intersection : $A\cap B = {x:x\in A\land x\in B}$
Difference: $A-B = {x:x\in A\land x\notin B}$ (sometimes denoted as A\B)
Complement: $\overline A = U-A = {x\in U: x\notin A}$
$A-B=A\cap \overline B$
$|A\cup B| = |A|+|B|-|A\cap B|$

Logical equivalence

Generalized unions and intersections

union

$A1\cup A_2\cup \cdots \cup A_n = \bigcup{i=1}^n A_i$

$A1\cup A_2\cup \cdots \cup A_n\cup\dots = \bigcup{i=1}^\infty A_i$

Intersection

$A1\cap A_2\cap \cdots \cap A_n = \cap{i=1}^n A_i$

$A1\cap A_2\cap \cdots \cap A_n\cap\cdots = \bigcap{i=1}^n A_i$

Set covering problem

Sequence

Denition

A sequence is a function from a subset of the set of integers (usually either the set {0,1,2,…} or the set {1,2,3,…}) to a set S. We use the notation an to denote the image of integer n. We call an a term of the sequence.

Some usefull sequences

Progression 数列

Geometric progression 等比数列

A geometric progression is a sequence of form $a,ar,ar^2,\cdots,ar^n,\cdots$ where initial term a and common ratio r are real numbers.

Arithmetic progression 等差数列

An arithmetic progression is a sequence of form $a,a+d,a+2d,\cdots ,a+nd,\cdots$ where initial term a and common difference d are real numbers.

Examples

The sequences ${b_n}$ is a form of$ bn = (-1)^n$. The list of terms $b_0,b_1,b_2,b_3,\cdots$ begins with $1,-1,1,-1,\cdots$
The sequences ${s_n}$ is a form of $sn = -1 + 4n$. The list of terms $s_0,s_1,s_2,s_3,\cdots$ begins with $-1,3,7,11,\cdots$ .

Recurrence relation 递推关系

A recurrence relation for the sequence fang is an equation that expresses an in terms of one or more of the previous terms of the sequence, namely, $a0,a_1,\cdots,a{n-1}$, for all integers n with $n\geq n_0$, where $n_0$ is a nonnegative integer. A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

Example

Let ${an}$ be a sequence that satises the recurrence relation $a_n = a{n-1} + 3$ for $1,2,3,\cdots,$ and suppose that $a_0=2$. What are a1, a2, and a3?
Let ${an}$ be a sequence that satises the recurrence relation $a_n = a{n-1}-a_{n-2}$ for $n=2,3,4,\cdots$, and suppose that $a_0 = 3$ and $a_1 = 5$. What are $a_2$ and $a_3$?

Fibonacci sequence

Fibonacci sequence, $f0,f_1,f_2.\cdots,$ is dened by initial conditions $f_0 = 0,f_1 = 1$ and recurrence relation $f_n = f{n-1}+f_{n-2}$ for $n=2,3,4,\cdots$

Determine whether sequence ${an}$, where $a_n = 3n$ for every nonnegative integer n, is a solution of recurrence relation $a_n = 2a{n-1}-a_{n-2}$ for $n=2,3,4,\cdots$ Answer the same question where $a_n = 2^n$ and where $a_n = 5$.

Summations

Some useful summation formula

Cardinality集的势

集合的势是用来度量集合规模大小的属性的。

如果存在着从集合A到集合B的双射，那么称集合A与集合B等势。例：集合N={0,1,2…}，N2={0,2,4，…}定义映射：f：N→N2 ，f（n）=2n，f是从N到 N2的双射，从而N和N2 是等势的。

有很多集合都和全体正整数的集合等势，从而它们彼此也等势，称所有这样的集合为“可数无穷的（countably infinite）”。有很多无穷集合比全体正整数的集合的势更大，称所有这样的集合为不可数无穷的（uncountably infinite）。但是，不存在无穷集合的势比全体正整数的集合的势更小

Sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.

If there is a one-to-one function from A to B, the cardinality of A is less than or the same as the cardinality of B and we write $|A|\leq|B|$,
Moreover, when $|A|\leq|B|$, and A and B have different cardinality, we say that the cardinality of A is less than the cardinality of B and we write $|A|<|B|$

Countable sets

A set that is either finite or has the same cardinality as $Z^+$ is called countable. If an finite set S is countable, then |S| = $\aleph_0$

Example

Show that the set of odd positive integers is a countable set.

Hilberts Grand Hotel

Grand Hotel with $\aleph_0$ rooms How can we accommodate a new guest arriving at the
fully occupied Grand Hotel without removing any of the current guests?

Solution
Because the rooms of the Grand Hotel are countable, we can list them as Room 1, Room 2, Room 3, and so on. When a new guest arrives, we move the guest in Room 1 to Room 2, the guest in Room 2 to Room 3, and in general, the guest in Room n to Room n + 1, for all positive integers n. This frees up Room 1, which we assign to the new guest, and all the current guests still have rooms.

Integer Set

Show that the set of all integers is countable.

Positive rational numbers

Show that all positive rational numbers is countable.

An uncountable set

Real numbers

Show that the set of real numbers is an uncountable set.

Results about cardinality

函数

Function

Definition

Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one element of B to each element of A. We write $f (a) = b$ if b is the unique element of B assigned by function f to element a of A. If f is a function from A to B, we write $f: A\rightarrow B$

Domain(定义域) and codomain(陪域)

If f is a function from A to B, we say that A is the domain of f and B is the codomain of f . If f (a) = b, we say that b is the image of a and a is a preimage of b. The range, or image, of f is the set of all images of elements of A. Also, if f is a function from A to B, we say that f maps A to B.

Let g be the function that assigns a grade to a student in our discrete mathematics class. Note that g(Adams) = A, for instance.

The domain of g is set {Adams, Chou, Goodfriend, Rodriguez, Stevens}, and the
codomain is set {A, B, C ,D,F}.

The range of g is set {A, B, C, F}, because each grade except D is assigned to some students.

Add and product

Definition

Let $f_1$ and $f_2$ be functions from A to R. Then $f_1+f_2$ and $f_1f_2$ are also functions from A to R defined for all $x\in A$ by

$(f_1+f_2)(x) = f_1(x)+f_2(x)$

$(f_1f_2)(x) = f_1(x)f_2(x)$

Example

Let $f_1$ and $f_2$ be functions from R to R such that $f_1(x) = (x+1)^2$ and $f_2(x) = -(x-1)^2$ Thus we have

$(f_1+f_2)(x) = f_1(x)+f_2(x)= (x+1)^2-(x-1)^2 = 4x$

$(f_1f_2)(x) = f_1(x)f_2(x) = -(x+1)^2(x-1)^2 = -(x^2-1)^2$

Projection 函数的投影

One-to-one and onto functions

单射（one to one或injective）

没有两个x有相同的y

满射(onto function surjection):

每一个y都必有至少一个x与之对应

双射(又叫一一对应,bijection):

同时满足单射与满射，也就是常见的函数映射

那么通俗的说，单射就是只能一对一，不能多对一，满射就是不论一对一，还是多对一，在映射f:X→Y中，Y中任一元素y都是X中某元素的像，也就是Y中所有元素在X中都能找到原像，至于找到的只有一个原像,那就是双射，但有的可以找到一个以上的那就不是双射，即双射就是既是单射又是满射。

离散数学之集合与函数

集合

定义：

集合等价

应用

集合的展现

Tabular form 表列式

Descriptive form

Set builder form

Remarks

Venn diagrams

子集

Cartesian product

集合操作

Logical equivalence

Generalized unions and intersections

union

Intersection

Set covering problem

Sequence

De nition

Some usefull sequences

Progression 数列

Geometric progression 等比数列

Arithmetic progression 等差数列

Examples

Recurrence relation 递推关系

Example

Fibonacci sequence

Summations

Cardinality集的势

Countable sets

Example

Hilberts Grand Hotel

Integer Set

Positive rational numbers

An uncountable set

Real numbers

Results about cardinality

函数

Function

Definition

Domain(定义域) and codomain(陪域)

Add and product

Projection 函数的投影

One-to-one and onto functions

单射（one to one或injective）

满射(onto function surjection):

双射(又叫一一对应,bijection):

Inverse function 反函数

Composition of functions 复合函数

Inverse of composition of functions

Some important functions: Floor and ceiling functions

Useful properties of floor and ceiling functions

Some important functions: Indicator function

Some important functions: Sigmoid functions

Denition