Ernest Schimmerling ; Basic and Intermediate Logic ; Chapter 1

© 2013, 2014 Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Chapter 1 : Course background

This should not be the first course in which the emphasis is pure mathematics theory and proofs.

Below is a rapid-fire list of terminology, notation and ideas that should be familiar or quickly grasped.

§ 1.1   Terminology and notation

The words set, collection and family mean the same thing.

The phrases "x is a member of A" and "x belongs to A" and the notation x ∈ A mean the same thing.

A is a subset of B iff A ⊆ B iff for all x, if x ∈ A, then x ∈ B.

If S is a collection of sets, then the union of S is

    ∪ S = { x ∣ there exists A ∈ S such that x ∈ A }.

The union of two sets A and B is A ∪ B = { x ∣ x ∈ A or x ∈ B } = ⋃ { A , B }.

If S is a nonempty collection of sets, then the intersection of S is

    ∩ S = { x ∣ for all A ∈ S, x ∈ A }.

The intersection of two sets A and B is A ∩ B = { x ∣ x ∈ A and x ∈ B } = ⋂ { A , B }.

( x , y ) is notation for the ordered pair whose first coordinate is x and second coordinate is y.

This is different from the unordered pair { x , y } = { y , x }.

Ordered pairs could also called 2-tuples.

There are ordered triples, also called 3-tuples, which have the form ( x , y , z ).

In general, we have n-tuples. which look like ( x0 , … , xn-1 ).

A × B = { ( x , y ) ∣ x ∈ A and y ∈ B }. This is called the Cartesian product of A and B.

An = { x̅ ∣ x̅ is an n-tuple of members of A }.

R is an n-ary relation on A iff R ⊆ An.

R ( x̅ ) means the same thing as x̅ ∈ R.

f is a function from A to B iff f ⊆ A × B and for every x ∈ A, there exists a unique y ∈ B such that ( x , y ) belongs to f.

We write f ( x ) = y instead of ( x , y ) ∈ f when f is a function.

The words function, operation and map mean the same thing. Also indexed family and sequence.

If f is a function from A to B, then the domain of f is dom ( f ) = A = { x ∣ there exists y such that f ( x ) = y }.

If S ⊆ A, then f [ S ] = { f ( x ) ∣ x ∈ S }.

The range of f is ran ( f ) = f [ A ].

We write f : A → B to indicate that f is a function with dom ( f ) = A and ran ( f ) ⊆ B.

We also use the notation f : x ↦ f ( x ) and < f ( x ) ∣ x ∈ A > to refer to the function f.

If S ⊆ A, then the restriction of f to S is written f ↾ S or < f ( x ) ∣ x ∈ S >.

f is an injection from A to B iff f is a function from A to B and for all x , x' ∈ A, if x ≠ x' , then f ( x ) ≠ f ( x' ).

f is surjection from A to B iff f is a function from A to B and for all y ∈ B, there exists x ∈ A such that f ( x ) = y .

f is a bijection from A to B iff f is an injection and a surjection from A to B.

f is a permutation of A iff f is a bijection from A to A.

f is an n-ary function on A iff f : An → A.

unary and 1-ary mean the same thing.

binary and 2-ary mean the same thing.

Sometimes we write x R y instead of R ( x , y ) when R is a binary relation.

For example, we write 0 < 1 instead of < ( 0 , 1 ).

Sometimes we write x F y = z instead of F ( x , y ) = z when F is a binary function.

For example, we write 1 + 2 = 3 instead of + ( 1 , 2 ) = 3.

§ 1.2   Natural numbers, induction and recursion

The natural numbers are 0, 1, 2, 3, 4 etc.

More precisely, 0 = { } , 1 = { 0 } , 2 = { 0 , 1 } , 3 = { 0 , 1 , 2 } , 4 = { 0 , 1 , 2 , 3 } etc.

Each natural number is the set of natural numbers that precedes it.

This choice is convenient because, for all natural numbers i and n,

    i < n   iff   i ∈ n .

ω is the set of natural numbers. So ω = { 0 , 1 , 2 , 3 , 4 etc. }.

    Induction Theorem 1.1

    Let Statement ( x ) be a statement about x.

    First version

    Assume that for every n ∈ ω, if Statement ( i ) holds for every i < n, then Statement ( n ) holds.

    Then, for every n ∈ ω, Statement ( n ) holds.

    Second version

    Assume that Statement ( 0 ) holds.

    Assume that for every n ∈ ω, if Statement ( n ) holds, then Statement ( n+1 ) holds.

    Then, for every n ∈ ω, Statement ( n ) holds.

    Recursion Theorem 1.2

    Let B be a set.

    P = { f ∣ f is a function with dom ( f ) ∈ ω and ran ( f ) ⊆ B }.

    Let G : P → B be a function.

    Then there is a unique function F : ω → B such that, for every n ∈ ω, F ( n ) = G ( F ↾ n ).

Example of a definition by recursion

Unless you took a set theory course, you probably have not seen the Recursion Theorem stated this way.

Here is an example of how Theorem 1.2 is used that should convince you it is equivalent to the version you saw.

Given a function f with dom ( f ) = n, define

    G ( f ) = 0 if n = 0 ,

    G ( f ) = 1 if n = 1, and

    G ( f ) = f ( n-2 ) + f ( n-1 ) if n ≥ 2.

By Theorem 1.2, there is a function F with domain ω and F ( n ) = G ( F ↾ n ) for every n ∈ ω.

Calculating, we see

    F ( 0 ) = G ( < > ) = 0

    F ( 1 ) = G ( < 0 > ) = 1

    F ( 2 ) = G ( < 0 , 1 > ) = 1

    F ( 3 ) = G ( < 0 , 1 , 1 > ) = 2

    F ( 4 ) = G ( < 0 , 1 , 1 , 2 > ) = 3

    F ( 5 ) = G ( < 0 , 1 , 1 , 2 , 3 > ) = 5

    F ( 6 ) = G ( < 0 , 1 , 1 , 2 , 3 , 5 > ) = 8

In general, F ( n+2 ) = G ( F ↾ ( n+2 ) ) = F ( n ) + F ( n+1 ).

These are the Fibonacci numbers, which will play no role in the course other than this example.

§ 1.3   Finite sets

Powers

Notice that nm has two meanings:
  1. n raised to the m'th power.

    (This is a number.)

  2. { x̅ ∣ x̅ is an m-tuple of numbers less than n }.

    (This is a set but not a number.)

Above, the set above has size the number above.

It is always clear from context what we mean when we write nm.

There are 2m many subsets of m.

Factorials

n has n! permutations.

In particular, 0! = 1 because the empty set has one permutation.

(The identity function on A is a permutation of A even if A = { }.)

Primes

The prime numbers are 2, 3, 5, 7, 11, 13, 17 etc.

Each natural number n ≥ 2 can be factored into powers of primes in a unique way.

This implies that the function

    ( m0 , … , mj-1 )   ↦   ∏ i < j ( pi ) mi+1

is an injection from ω < ω - { ( ) } to ω , where pi stands for the i'th prime number here.

We should have said earlier that, for any set A,

    A< ω = ∪ { An ∣ n ∈ ω }.

The "product of powers of primes" function is a popular way to code a finite sequence of numbers by a single number.

§ 1.4   Countable sets

A set S is finite iff there exists a natural number n and a surjection from n onto S.

A set S is infinite iff S is not finite.

A set S is countable iff S = { } or there exists a surjection from ω onto S.

    Lemma 1.3

    If S is infinite and countable, then there exists a bijection from ω to S.

    Lemma 1.4

    If S is a countable collection of sets and every member of S is countable, then ∪ S is countable.

The following sets are countable:

    ω = { 0 , 1 , 2 , 3 , … } = the set of natural numbers

    ℤ = { … , -2 , -1 , 0 , 1 , 2 , 3 , … } = the set of integers

    ℚ = { m / n ∣ m , n ∈ ℤ and n ≠ 0 } = the set of rational numbers

    ω < ω = the set of finite tuples of natural numbers

§ 1.5   Uncountable sets

The following sets are uncountable:

    ℝ = the set of real numbers

    P ( ω ) = { X ∣ X ⊆ ω } = the collection of subsets of ω

    2ω = { f ∣ f is a function from ω to 2 }

The reason that P ( ω ) is uncountable is that if f is a function from ω to P ( ω ), then

    { n ∈ ω ∣ n ∉ f ( n ) }

is a subset of ω that is not in the range of f.

For A ⊆ ω, we have its characteristic function charA : ω → 2 given by

    charA ( n ) = 1   iff   n ∈ A.

The map A ↦ charA is a bijection from P ( ω ) to 2ω.

This explains why 2ω is also uncountable.

Every real number x between 0 and 1 has a binary representation.

This means that there exists b ∈ 2ω such that

    x = ∑n ∈ ω   b ( n ) / 2n+1 .

Some x have two such representations. For example, in binary notation:

    0.100000 ⋅ ⋅ ⋅   =   0.011111 ⋅ ⋅ ⋅

But there are never more than two representations.

These thoughts lead to a proof that ℝ is uncountable.

§ 1.6   Equivalence relations

Consider an arbitrary binary relation E on S.

So E ⊆ S × S.

E is reflexive iff for every x ∈ S, E ( x , x ).

E is symmetric iff for all x , y ∈ S, if E ( x , y ), then E ( y , x ).

E is transitive iff for all x , y , z ∈ S, if E ( x , y ) and E ( y , z ), then E ( x , z ).

E is an equivalence relation on S iff E is a reflexive, symmetric and transitive relation on S.

For x ∈ S, define [ x ]E = { y ∈ S ∣ E ( x , y ) }.

Define S / E = { [ x ]E ∣ x ∈ S }.

Define a partition of S to be a family of nonempty pairwise disjoint subsets of S whose union is S.

    Lemma 1.5

    Let E be an equivalence relation on S.

    Then S / E is a partition of S.

    Lemma 1.6

    Let P be a partition of S.

    Define a binary relation E on S by E ( x , y ) iff x and y belong to the same member of P.

    Then E is an equivalence relation on S and S / E = P.