Ch2 Basic Structures

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

集合 Sets

引言 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)

集合之间的关系 Relations between Sets

Subset

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

Equal

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

Proper Subset

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

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$.

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$.

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) 定义为

• 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$

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)\}$

集合操作 Set Operations

Union

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

Intersection

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

Difference

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

Complement

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

Symmetric difference

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

集合恒等式 Set Indentities

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

函数 Functions

引言 Introduction

Let $A$ and $B$ be nonempty sets. A 函数(function) (mapping or transformations) $f$ from $A$ to $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

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

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

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

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

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

函数的复合 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$ can’t be defined unless the range of $g$ is a subset of the domain of $f$.

高斯函数 Floor and Ceiling Functions

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

数列 Sequence

引言 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

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

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

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

和式 Summations

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

Some Useful Summation Formulae

集合的基数 Cardinality of Sets

引言 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|$。

可数的 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).

证明：$0$ 到 $1$ 之间的实数集是不可数的。

证明：$[0,1]$ 和 $(0,1)$ 是等势的。

证明：$\mathbb N$ 的所有有限子集是可数的。

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

再给出一个证明：

康托定理 Cantor’s Theorem