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 is
  • 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
00.10.20.30.40.50.60.70.80.91−1-0.8-0.6-0.4-0.200.20.40.60.81

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:

  1. Assume is countable, then we can "count" the numbers one by one.
  2. Then, we can list all the numbers that we count in a table.
  3. 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.