FB

Question 1

Function unknown to be computable

Answer 1

Patterns of the digits of pi - function is not known to be effectively computable or non-computable

Question 2

∅

Answer 2

stands for the empty set which has no
members. The empty set may also be written {}.

Question 3

Set membership

Answer 3

x ∈ S

Question 4

subset

Answer 4

S is a subset of T, written S ⊆ T, exactly when for every
x ∈ S it also holds that x ∈ T.

Question 5

Set union, set intersection, set difference

Answer 5

Set union is written as S ∪ T, set intersection is written as
S ∩ T, and set difference is written as S \ T

Question 6

set product

Answer 6

notation S × T
stands for the set of all ordered pairs (x, y) such that x ∈ S
and y ∈ T.

Question 7

N
2

Answer 7

set of all pairs of natural numbers

Question 8

N

Answer 8

set of all natural numbers: 0, 1, 2, 3, and so on.

Question 9

Z

Answer 9

set of all integers: . . . , −3, −2, −1, 0, 1, 2, 3, . . . .

Question 10

Q

Answer 10

set of all rational numbers, each of which is the result
of dividing an integer x by a positive integer y, written x/y

Question 11

R

Answer 11

set of all real numbers, each of which can be viewed
as the sum of an infinite sequence of rational numbers.

Question 12

binary relation

Answer 12

a set of ordered pairs.

Question 13

application

Answer 13

Given a binary relation R, the application R(x) denotes y
such that (x, y) ∈ R, if there is exactly one such y, and is
otherwise undefined.

Question 14

domain

Answer 14

dom(R) = { x ∃y. (x, y) ∈ R }.

Question 15

range

Answer 15

ran(R) = { y ∃x. (x, y) ∈ R }.

Question 16

Function Space

Answer 16

S to set T, written S → T, is the
set of every function f such that dom(f ) ⊆ S and ran(f ) ⊆ T.
If f ∈ S → T, it is said that f is a function from S to T.

Question 17

Total function spaces

Answer 17

A function f is total on S if and only if dom(f ) = S. The
total function space from S to T, written S −
tot → T, is the set
of every function f ∈ S → T such that dom(f ) = S.

Question 18

inverse

Answer 18

the inverse of a binary relation R is
R−1 = { p ∃x. ∃y. p = (y, x) and (x, y) ∈ R }.

Question 19

one-to-one (injective)

Answer 19

exactly when
both R and its inverse R
−1
are functions.

Question 20

onto S (surjective to S)

Answer 20

A function f is onto S (surjective to S) if and only if
ran(f ) = S.

Question 21

bijection

Answer 21

A bijection from S to T is a function that is total on S,
one-to-one (injective), and onto T (surjective).

Question 22

enumerate

Answer 22

To enumerate a set is to arrange its members in a single list
with a first entry, a second entry, etc., so that:
- every member of the set appears sooner or later in the list and
- every entry in the list belongs to the set. In an enumerated set, every member of the set must be listed
after at most a finite number of other members.

Question 23

cardinality

Answer 23

Sets can be finite or infinite. The notation |A| stands for the
cardinality of A, i.e., the number of members in the set A.

Question 24

countable set

Answer 24

When thinking more about a set’s size rather than about
listing the set, we say an enumerable set is countable.

Question 25

countably
infinite

Answer 25

lf a set is enumerable and infinite, we say it is countably
infinite (or enumerably infinite)

Question 26

a

Answer 26

The size of a countably infinite set is a.

Question 27

N countable?

Answer 27

The set N is countably infinite.

Question 28

|A| = |B|

Answer 28

(i.e., A and B are of the same size) if and only if
there exists a bijection f from A to B.

Question 29

Uncountability

Answer 29

[0, 1[ is not countable.

Question 30

enumeration function

Answer 30

A set with an enumeration function is enumerable and also
countable.

Question 31

Uncountability of the power set of N

Answer 31

t ℘(N) is not countable.

Question 32

Uncountability of P(N)

Answer 32

Proof by contradiction.
Assume P(N) is countable. Meaning we can list all elements in a sequence.
Since S contains all possible subsets of N, we can represent each element of S as a sequence of 0s and 1s, where the ith position of the sequence is 1 if the ith element of N is included in the subset, and 0 otherwise.

Now, let’s construct a new subset of N, T: for each ith element of N, we include it in T if the ith position of the sequence corresponding to the ith element in S is 0, and we exclude it from T if the ith position of the sequence is 1. In other words, we construct T by flipping the membership status of each element of N in each corresponding subset of S.

It can be shown that T is not in S, since T differs from every subset of S in at least one element. Therefore, we have found a subset of N that is not in the sequence S, contradicting the assumption that S contains all possible subsets of N. Hence, we conclude that the power set of N is uncountable.

Question 33

Q states TMB for n-1

Answer 33

q0: go right til ^
q1: go through left through 0s til 1. Swap 1 with 0, R.
if ^ Halt.
q2: go right through 0 swap with 1. When ^ L.
q3: go left through 0+1, ^ go R.
q4: 1 Halt. If 0, go through right ^.
If ^ go L.
q5: replace ^ with 0. Halt
q6: Halt

Question 34

Define Effective Procedure:

Answer 34

An effective procedure is one that always correctly returns the right answer, only where there is a finite number of steps which are mechanical if all requested resources are provided.

Question 35

Effectively computable

Answer 35

A process is effectively computable exactly when an effective procedure calculates it.

Question 36

Church Thesis - TM

Answer 36

Every effectively computable function is Turing computable

Question 37

Solvable?
Halt?
Even?

Answer 37

Halt - unsolvable. No TM calculates halt.
Even is solvable

Question 38

Surjective (onto)

Answer 38

Every B has some A

Question 39

Injective (one-to-one)

Answer 39

B can’t have many A

Question 40

Bijective (surjective, injective)

Answer 40

A to B, perfectly

Question 41

Turing Computable

Answer 41

A function f ∈ N^j → N^k is Turing Computable exactly when there exists a Turing Machine M such that f = unaryIOj(M). f is computed by M

f (x) = x + 1 for every x ∈ N
f = unaryIO1,1(Madd1)