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

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_{0} , … , x_{n-1} ).

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

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

R is an n-ary __relation__ on A iff R ⊆ A^{n}.

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^{n} → 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.

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

Let Statement ( x ) be a statement about x.

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

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

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.

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

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.

- n raised to the m'th power.
(This is a number.)

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

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

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

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

This implies that the function

( m_{0} , … , m_{j-1} )
↦
∏_{ i < j } ( p_{i} ) ^{mi+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} ∣ n ∈ ω }.

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

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.

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

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

ℝ = 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^{n+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.

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.

Let E be an equivalence relation on S.

Then S / E is a partition of S.

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.