date: 2024-10-04
title: 02-TOC-Math
status: DONE
author:
  - AllenYGY
tags:
  - NOTE
  - TOC
  - Math
publish: True

TOC-Math

“No one shall expel us from the paradise which Cantor has created for us.” ---David Hilbert, 1926

Sets

Def: A set (naively) is a collection of objects such that

no order and no duplication

An object is in a set is denoted as .

To represent a set, you need to

Put all members in a pair of curly brackets ;
Enumerate all members, e.g. ; or
Give a member representative and followed by the characteristic of members using a predicate,
- e.g. .

Def: Empty set

is an empty set, denoted by .

"" is a concatenation (always false), Or equivalently,

Def: Empty set

is an empty set if .

Universal set

Def: Universal set

A universal set is a set that contains all elements under a certain context.

A universal set is usually denoted in the blackboard bold font. For example,

: the set of natural numbers;
: the set of integers;
: the set of rational numbers;
: the set of real numbers;
: the set of complex numbers;
: the universal set without a specification.
: the set of prime numbers.

Def: subset

Set is a subset of set if , denoted as .

Def: Power set

Let A be a set. is the power set of A.

Let .

Set operator

Suppose and are two sets.

Def: Complement

A complement is the set .

Def: Intersection

A intersection is the set .

Def: Union

A union is the set .

Def: Setminus

A setminus is the set .

Relation

Suppose and are two sets.

Def: Cartesian product

The cartesian product of and is the set:

Each object is a pair or generally a 2-tuple.

Def: Relation

A relation between and is a subset of .

If , we say is related to , denoted by .

A relation is on the set if .

Let be a relation on a set . is:

reflexive if ;
symmetric if ;
anti-symmetric if ;
transitive if .

Function

Def: Function

A relation between and is a function if:

is the domain.
is the co-domain.
means uniquely exists.
Such a function is denoted as .

Def: Image and pre-image

If is an object of the function , we denote and say:

is the image of ;
is the pre-image of .

To denote a function:

Surely, one can enumerate all pairs in the function.
But usually, people present the expression.
For example, such that .

For the same example, one can also write .

Please distinguish “” and “”:

“” is from domain to co-domain.
“” is from pre-image to image.

Def: A function

Injection: If
- 不同x对应不同y
Surjection: If
- 任何y都有对应的x
Bijection: If is both injection and surjection.

For example, let .

is an injection but not a surjection.
is a surjection but not an injection.
is a bijection.

Graph

Formal Language

To precisely describe mathematics, algorithm, computation, and other procedures, formal languages are used. A language is a set of strings over an alphabet. Formally,

Def: Language

A language is a set of strings over a specific alphabet.

Def: alphabet

An alphabet is a nonempty finite set.

For example,

Strings

Def: string

A string over an alphabet is a finite sequence of symbols from that alphabet.

Def: length

If is a string over the alphabet , the length of is the number of symbols in , denoted by .

Def: Empty string

The empty string is the string of length 0, denoted by .

Let be a string of length n, where each .

Def: Reverse

The reverse of a string is the string , denoted by .

Def: Substring

The string is a substring of if consecutively appears in .

Def: Concatenation

The concatenation of two strings and is the string of length .

For example, .
Sometimes, the operator “” is omitted.

Language

A language is a set of strings over a specific alphabet.

Proof

In this lecture, we only emphasize several proving techniques.

Constructive proof
Prove by contradiction
Induction
Diagonal argument

Constructive proof

Used to prove a predicate with existential quantifiers, like .
First, construct an object .
Second, prove is true.

Prove by contradiction

Used to prove a proposition .
First, assume is false.
Then, derive a contradiction.
Last, claim is true.

Induction

To prove a predicate with universal quantifiers, one can use induction.
Induction has two variants: simple and strong. But, they are equivalent.
To prove :

Simple Induction:

Prove as a base case.
Prove as an induction.
In the second step, is the inductive hypothesis.

Strong Induction:

Prove as a base case.
Prove .
We assume are all true in the strong induction.

Cardinality

Def: Cardinality

The cardinality of a set is the number of objects in , denoted as .

Def: Cardinality

The set and the set are of the same cardinality if there is a bijection .

Examples:

and are of the same cardinality because we can define a bijection such that .
The set of even numbers and the set of integers are also of the same cardinality because of the bijection .

Note that the cardinality can be finite and infinite.

Countable

Def: Countable

A set is countable if it is finite or its cardinality is same as the set of natural number .

Countable means that:

For every number in the natural number (no matter how large the number is),
if we count from 0,
we can eventually reach the number within a finite time.

In fact, the counting procedure constructs a bijection, mapping a natural number to the counted element.

We denote the cardinality of by

To proof an infinite set is countable, you need t construct a bijection

Diagonal Proof

Georg Cantor developed a method to prove a set is uncountable.

For example:

Theorem

The set of all real numbers in the open interval is uncountable.

The intuition of the proof (by contradiction) is as follows:

Assume is countable, then we can "count" the numbers one by one.
Then, we can list all the numbers that we count in a table.
Construct a real number in but cannot be reached in the table.

Thus, the set of reals in is uncountable.

Suppose we denote a real number as . Then, we build the table in Step 2 of the proof.

Index		Digits
0
1
2

Next, we define a real number such that:

We can see is not in the list:

and are different at digit 0.
and are different at digit 1.

Thus, is not counted, and the set of reals in is uncountable.

Here we list some facts about infinite sets:

The set of real numbers has cardinality .
The power set of also has cardinality .
has cardinality .
You can make such constructions by taking power sets.

Hypothesis (Continuum Hypothesis - CH)

There is no set of cardinality strictly between and .

So far, people only know:

Theorem (Cohen 1964)

CH is unprovable under ZFC.