© Ernest Schimmerling

Online textbook for Basic and Intermediate Logic

Chapter 1 : Course background

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

§ 1.1   Terminology and notation

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 ( x₀ , … , x_n-1 ).

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

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

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

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 : Aⁿ → 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

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

Example of a definition by recursion

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

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 n^m.

There are 2^m many subsets of m.

Factorials

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

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

This implies that the function

    ( m₀ , … , m_j-1 )   ↦   ∏ _{i < j} ( p_i ) ^m_i+1

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

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

    A^{< ω} = ∪ { Aⁿ ∣ 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 infinite iff S is not finite.

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

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 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 char_A : ω → 2 given by

    char_A ( n ) = 1   iff   n ∈ A.

The map A ↦ char_A 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 ) / 2ⁿ⁺¹ .

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

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.