Scribd
Upload
112 views4 pages

Main PDF

This document summarizes key concepts related to sets, relations, functions, orderings, natural numbers, and ordinal numbers. It introduces fundamental definitions such as sets, properties of sets, axioms of set theory, fields of relations, linear orderings, chains, successor and inductive sets in the context of natural numbers, well-orderings, finite vs countable vs uncountable sets, cardinal numbers, transitive and ordinal numbers, and operations on ordinals like addition. Theorems are also presented on the induction principle for natural numbers and properties of ordinal numbers.

Uploaded by

Tytus Metrycki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
112 views4 pages

Main PDF

This document summarizes key concepts related to sets, relations, functions, orderings, natural numbers, and ordinal numbers. It introduces fundamental definitions such as sets, properties of sets, axioms of set theory, fields of relations, linear orderings, chains, successor and inductive sets in the context of natural numbers, well-orderings, finite vs countable vs uncountable sets, cardinal numbers, transitive and ordinal numbers, and operations on ordinals like addition. Theorems are also presented on the induction principle for natural numbers and properties of ordinal numbers.

Uploaded by

Tytus Metrycki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Notes on sets

1 Sets
1.1 Introduction to Sets
1.2 Properties
1.3 The axioms
The axiom of Existence There exists a set which has no elements

The Axiom of Extensionality If for every element, the element is


in X iff its in Y , the X = Y .
The Axiom Schema of Comprehension Let P (x) be a property of
x. For any set A, there is a set B such that x ∈ B iff x ∈ A ∧ P (x).

The Axiom of Pair If A, B are sets so is {A, B}.


S
The Axiom of Union For any set S, S is a set.
The Axiom of Power Set If S is a set then PS is also a set.
The axiom of infinity An inductive set exists.

Note that we could replace the axiom of existence by Weak axiom of


existence and define the emptyset using schema of Comprehension.

2 Relations, Functions, and Orderings


Definition 1. Field of R
If R is a relation we define

field(R) := dom R ∪ range(R)

Definition 2. Linear/total ordering


An ordering ≤ or < is called linear if any two elements of an underlying
set are comparable.

Definition 3. Chain
Let B ⊆ A where A is ordered by ≤. B is a chain in A if any two
elements of B are comparable.

3 Natural numbers
Definition 4. The successor of a set
For any set x we define:

S(x) := x ∪ {x}

1
Definition 5. Inductive set
We call a set I inductive if
1. ∅ ∈ I
2. If n ∈ I then S(n) ∈ I.
Definition 6. Natural numbers
We define natural numbers as intersection of all inductive sets.
Definition 7. Relation < on N
We define:
n < m ⇐⇒ n ∈ m
Theorem 1. Induction principle
Let P (x) be a property. Assume that
1. P (0) holds, and:
2. For all n ∈ N, P (n) =⇒ P (n + 1)
Then P holds for all natural numbers.
Proof. We have:
A := {n ∈ N : P (n)}
which is inductive, thus:
N⊆A

Theorem 2. Induction principle II


If P (k) holds for all k < n, then ∀ n ∈ N : P (n).
Proof. Consider a property Q(x) := ∀ k : k < x =⇒ P (x).

1. Clearly Q(0) holds.

2. If Q(n) holds then P (n) holds, but then Q(n + 1) holds.

Definition 8. Well-ordering
We call a linear ordering a well-ordering if every non-empty subset has
a least element.

4 Finite, Countable, and Uncountable Sets


Important observation, for any finite ordered set (A, <), if card(A) =
card(B) then (A, <) ∼
= (B, <).

2
5 Cardinal Numbers
Bla, bla 2ℵ0 , bla

6 Ordinal Numbers
Definition 9. Transitive set
A set T is transitive if every element of T is a subset of T .
Definition 10. Ordinal number
A set α is an ordinal number if:

1. α is transitive
2. α is well-ordered by α
Theorem 3. If α is an ordinal then S(α) is also an ordinal.
Proof. First transitivity:
x ∈ S(α)
gives two possible cases:

1. x ∈ α then x ⊆ α and thus x ⊆ S(α)


2. x = α then clearly x ⊆ S(α)
If we have non-empty subset B, then either {α} = B, and we have
obvious smallest element or B \ {α} ⊆ α, thus by the fact that α is
well-ordered, there exists the smallest element.

Theorem 4. Every natural number is an ordinal


Proof. Previous theorem.
Definition 11. Order on ordinals
If α, β are ordinal, we define:

α < β ⇐⇒ α ∈ β

Definition 12. Addition on ordinals


Let α be ordinal, then:

α+0=α
β + S(α) = S(β + α) For all α
β + α = sup{β + γ : γ < α} for all limit α 6= 0

You might also like