Ch2 Basic Structures

本篇笔记介绍了集合的基本概念，包括集合的定义、表示方法、集合之间的关系、集合的操作以及函数的基本性质。我们探讨了集合的基数、可数性以及康托定理等重要主题。通过这些内容，读者将能够理解离散数学中集合和函数的基本结构和性质。（由 gpt-4o-mini 生成摘要）

Word Table

符号(notation)
省略号(ellipse)
括号(brace)

1. 集合 Sets

1.1. 引言 Introduction

集合(set)：A set is an unordered collection of objects.

The objects in a set are call the 元素(elements)，or members, of the set.
A set is said to 包含(contain) its elements.
- $a \in A$ ： $a$ is the member of the set $A$ .
- $a \not\in A$ ： $a$ is not the member of the set $A$ .
空集(empty set)： $\varnothing$ .

集合的表示方式：The descriptions of a set

Roster method: listing all its members between braces, e.g. $S=\{1,3,5,7,9\}$ .
Brace notation with ellipses: e.g. $S=\{1,2,\ldots,99\}$ .
Specification using set builder: $S=\{x\mid P(x)\}$ , which means $S$ contains all the elements from $U$ (全集(universal set)) which have the property $P$ .
维恩图(Venn diagrams)

罗素悖论 Russell Paradox

Suppose there is a town with just one male barber; and that every man in the town keeps himself clean-shaven: some by shaving themselves, some by attending the barber. The barber obeys the following rule: he shaves all and only those men in town who do not shave themselves. Does the barber shave himself?

1.2. 集合之间的关系 Relations between Sets

1.2.1. Subset

$A\subseteq B$ : $A$ is a 子集(subset) of the set $B$ .

A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B)

1.2.2. Equal

$A=B$ : $A$ is 等于(equal) to $B$ .

A=B \Leftrightarrow A \subseteq B \land B \subseteq A

1.2.3. Proper Subset

$A\subset B$ : A is a 真子集(proper subset) of the set $B$ .

A \subset B \Leftrightarrow A \subseteq B \land A \neq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B) \land \exists (x \in B \land x\not\in A)

1.2.4. The Size of Sets

Let $S$ be a set. If there are exactly $n$ distinct elements in $S$ where $n$ is a nonnegative integer, we say that $S$ is a 有限集(finite set) and that $n$ is the cardinality of $S$ .

1.2.5. Power Sets

Given a set S, the 幂集(power set) of S is the set of all subsets of the set S. $\mathcal{P}(x)$ denotes the power set of $S$ .

证明：

\mathcal{P}(A) \in \mathcal{P}(B) \Rightarrow A\in B

1.2.6. Cartesian Products

The 有序 $n$ 元组(ordered $n$ -tuple) $(a_1,a_2,\cdots ,a_n)$ is the ordered collection that has $a_1$ as its first element, $a_2$ as its second element, … , and $a_n$ as its nth element.

$A_1,A_2,\cdots,A_n$ 的卡特兰积(cartesian product) 定义为

A_1 \times A_2 \times \cdots A_n = \{(a_1,a_2,\cdots,a_n) \mid a_i \in A_i \quad\text{for }i=1,2,\cdots n\}

If $|A|=m,\ |B|=n$ , then $|A\times B|=|B\times A|=mn$ .
$A\times B\neq B\times A$
$A\times \varnothing = \varnothing \times A= \varnothing$

1.2.7. Truth Sets of Quantifiers

Given a predicate $P$ and a domain $D$ . The 真集(truth set) of $P$ is $P$ is the set of elements $x$ in $D$ for which $P(x)$ is true. Namely, the power set of $P$ is $\{x \in D\mid P(x)\}$

1.3. 集合操作 Set Operations

1.3.1. Union

$A\cup B = \{x \mid x \in A \lor x \in B\}$

1.3.2. Intersection

$A\cap B = \{x \mid x \in A \land x\in B\}$

1.3.3. Difference

$A-B = \{x \mid x\in A \land x \not\in B\}$ : The difference of $A$ and $B$ .

1.3.4. Complement

$\overline{A} = \{x \mid x \not\in A \land x\in U\}$ : $\overline{A}$ is the 补集(complement) of the set $A$ .

1.3.5. Symmetric difference

A\oplus B = (A\cup B) - (A\cap B)

按出现与否统计的话就类似于异或操作。

1.4. 集合恒等式 Set Indentities

更多集合恒等式(set indentities) 可以参考逻辑恒等式。

证明集合相等的一些方法 Ways to Prove Set Identities

将证明恒等式转化为证两次子集。Show that $A\subseteq B$ and that $B\subseteq A$ .
转化为 set builder 的形式，然后用逻辑恒等式证明。Use logical equivalences to prove equivalent set definitions.
类似于真值表的做法。Use a membership table.
从已有的恒等式中推演。Use previously proven identities.

2. 函数 Functions

2.1. 引言 Introduction

Let $A$ and $B$ be nonempty sets. A 函数(function) (mapping or transformations) $f$ from $A$ to $B$ :

f:A\rightarrow B

\forall a (a \in A \rightarrow \exists ! b (b \in B \land f(a) = b))

$A$ is called the 定义域(domain) of $f$
$B$ is called the 值域(codomain) of $f$

If $f(a) = b$ ,

$b$ is called the image of $a$ under $f$ .
$a$ is called a preimage of $b$ .

Let $f$ be a function from the set $A$ to the set $B$ . The 图(graph) of the function $f$ is the set of ordered pairs

\{(a,b) \mid a \in A \land f(a) = b\}

2.2. 单射与满射 One-to-One and Onto Functions

A function f is 单射函数(one-to-one function = injection) (denoted 1-1), or 单射的(injective) if

\forall a \forall b (f(a) = f(b) \rightarrow a = b)

A function $f$ from $A$ to $B$ is called 满射函数(onto function = surjection), or 满射的(surjective) if

\forall b \in B \exists a \in A (f(a) = b)

The function f is a 一一对应的(one-to-one correspondence), or a 双射(bijection), if it is both one-to-one and onto.

Showing that

f

is one-to-one or onto

2.3. 反函数 Inverse Functions

Let $f$ be a bijection from $A$ to $B$ . Then the 反函数(inverse function) of $f$ , denoted as $f^{-1}$ , is the function from $B$ to $A$ defined as

f^{-1} (y) = x \text{ iff } f(x) = y

函数 $f$ 的反函数存在当且仅当函数 $f$ 是双射函数。Function $f$ is 可逆的(invertible) if and only if $f$ is bijective. No inverse function exists unless $f$ is a bijection.

2.4. 函数的复合 Compositions of Functions

Let $g$ be a function from the set $A$ to the set $B$ and let $f$ be a function form the set $B$ to the set $C$ . The composition of the functions $f$ and $g$ denoted by $f \circ g$ is defined by:

f \circ g (a) = f(g(a))

$f\circ g$ can’t be defined unless the range of $g$ is a subset of the domain of $f$ .

2.5. 高斯函数 Floor and Ceiling Functions

关于高斯函数的实用性质 Useful Properties of the Floor and Ceiling Functions

3. 数列 Sequence

3.1. 引言 Introduction

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

A 等比数列(geometric progression) is a sequence of the form

a,\ ar,\ ar^2,\ \ldots,\ ar^n

where the initial term $a$ and the 公比(common ratio) $r$ are real numbers.

An 等差数列(arithmetic progression) is a sequence of the form

a,\ a+d,\ a+2d\, \ldots,\ a+nd

where the initial term $a$ and the 公差(common difference) $d$ are real numbers.

3.2. 和式 Summations

\sum_{s\in S} f(s)

$S$ : the subset of the domain of the function $f$

Some Useful Summation Formulae

4. 集合的基数 Cardinality of Sets

4.1. 引言 Introduction

The cardinality of a set $A$ is equal to the cardinality of a set $B$ , denoted $| A | = | B |$ , iff there exists a bijection from $A$ to $B$ .
If there is an injection from $A$ to $B$ , the cardinality of $A$ is less than or the same as the cardinality of $B$ and we write $|A| \le |B|$ . When $|A| \le |B|$ and $A$ and $B$ have different cardinality, we say that the cardinality of $A$ is less than the cardinality of $B$ and write $|A|<|B|$ .

所以说，比较集合的基数(cardinality of set) 的大小最关键的步骤就在于找到一个集合 $S$ 到另一个集合 $T$ 的单射，如果这样的单射能够找到，就有 $|S|\le |T|$ 。

4.2. 可数的 Countable

A set that is either 有限的(finite) or has the same cardinality as the set of positive integers called 可数的(countable).
A set that is not countable is called 不可数的(uncountable).
When an infinite set $S$ is countable, we denote the cardinality of $S$ by $\aleph_0$ (阿列夫零(aleph null)).
If $|A| = | \mathbb{Z}_+ |$ , the set $A$ is 可数无穷(countable infinite).

证明：正有理数集

\mathbb{Q}_+

是可数的。

(1) $|\mathbb{Q}_+| \le |S|$ ： $x=p/ q \rightarrow (p,q)$

(2) $|S| = |\mathbb{Z}_+|$ ：沿着对角线取——TBD

(3) $|\mathbb{Z}_+| \le |\mathbb{Q}_+|$ ： $x\rightarrow x/1$

证明：

0

到

1

之间的实数集是不可数的。

证明：

[0,1]

和

(0,1)

是等势的。

证明：

\mathbb N

的所有有限子集是可数的。

先直接给出一种数数方法：数集合的二进制表示。

再给出一个证明：

4.3. 康托定理 Cantor's Theorem

Theorem: 康托定理(Cantor's Theorem)

The cardinality of the powerset of an arbitrary set has a greater cardinality than the original arbitrary set.

实际上有： $|\mathcal P(\aleph_k)| = |\aleph_{k+1}|$ 。

TABLE OF CONTENTS

1. 集合 Sets

1.1. 引言 Introduction

1.2. 集合之间的关系 Relations between Sets

1.3. 集合操作 Set Operations

1.4. 集合恒等式 Set Indentities

2. 函数 Functions

2.1. 引言 Introduction

2.2. 单射与满射 One-to-One and Onto Functions

2.3. 反函数 Inverse Functions

2.4. 函数的复合 Compositions of Functions

2.5. 高斯函数 Floor and Ceiling Functions

3. 数列 Sequence

3.1. 引言 Introduction

3.2. 和式 Summations

4. 集合的基数 Cardinality of Sets

4.1. 引言 Introduction

4.2. 可数的 Countable

4.3. 康托定理 Cantor's Theorem

1. 集合 Sets

1.1. 引言 Introduction

1.2. 集合之间的关系 Relations between Sets

1.2.1. Subset

1.2.2. Equal

1.2.3. Proper Subset

1.2.4. The Size of Sets

1.2.5. Power Sets

1.2.6. Cartesian Products

1.2.7. Truth Sets of Quantifiers

1.3. 集合操作 Set Operations

1.3.1. Union

1.3.2. Intersection

1.3.3. Difference

1.3.4. Complement

1.3.5. Symmetric difference

1.4. 集合恒等式 Set Indentities

2. 函数 Functions

2.1. 引言 Introduction

2.2. 单射与满射 One-to-One and Onto Functions

2.3. 反函数 Inverse Functions

2.4. 函数的复合 Compositions of Functions

2.5. 高斯函数 Floor and Ceiling Functions

3. 数列 Sequence

3.1. 引言 Introduction

3.2. 和式 Summations

4. 集合的基数 Cardinality of Sets

4.1. 引言 Introduction

4.2. 可数的 Countable

4.3. 康托定理 Cantor's Theorem

评论