### Dana Scott's talk

Jun. 3rd, 2017 05:55 pm### Part 2

#### axiomatizing lambda

we have α, β, η (will drop η somehow)

But is it consistent?

Algebraic Query Language (AQL) based on CT

Using Gödel numbering

- pairing
`(n, m) = 2`

^{n}*(2m+1) - sequences
`<> = 0, <n0,...n`

_{k}> = (<n_{0},,, n_{k-1}>, n_{k} - Sets
`set(0) = {}, set((n, m)) = set(n) ∪ {m}`

- Kleene star
`X* = {n | set{n} ⊂ X}, for sets X ⊂ ℕ`

#### The universe is the powerset of integers

**Definition**Primitive recursive functions are those generated from the following: constant, projection, successor, by composition and simple recursion

f(0, x) = g(x) f(n+1, x) = h(n, x, f(n, x))

**Definition**

*Recursively enumerable (RE)*sets: those of the form {m |∃ n.p(n) = m+1} where p is primitive recursive.

#### Powerset of Integers

1) `P(ℕ)`

is a topological space, `{X | n ∊ X*}`

form a basis

2) CONTINUOUS FUNCTION `Φ:P(ℕ)`

if for all ^{n} → P(ℕ)`m ∊ ℕ, m ∊ Φ(x`

iff there are _{0}, x_{1}, ...)*`k`

for each _{i} ∊ X*`i<n`

such that `m ∊ Φ(set(k`

, _{0})`set(k`

- _{1}), ..., set(k_{n-1}))*"finite subset of function value information is determined by finite amount of information about the arguments"*

3) APPLICATION OPERATION

Application `F(X) = {m | ∃ n ∊ X* (n, m) ∊ F }`

4) ABSTRACTION

Abstraction `λ X.p...X... = {0} ∪ {(n, m) | m ∊ [... set(n)...]}`

This `{0}`

is here to ensure that it is the largest such set of numbers, `0`

is not needed actually.

Application operator

`F(X)`

is continuous in both arguments (`F`

and `X`

)Easy to prove (he says).

* If

`Φ(X`_{0}, X_{1}, ..., X_{n-1})

is continuous, `λ X`_{0}.Φ(X_{0},...X_{n-1})

is continuous on all remaining variables* If

`Φ(X)`

is continuous, `λ X. Φ(X)`

is the largest set `F`

such that for all sets `T`

, `F(T) = Φ(T)`

. Therefore, generally, `F ⊂ λ X. F(X)`

*(draws picture, how open sets look like)*

Complement function is not continuous (e.g. Russell set)

**Theorem.**For all sets of ints

`F`

and `G`

,λ X.F(X) ⊂ λ X.G(X) iff ∀ X. F(X) ⊂ G(X) λX.(F(X) ∩ G(X)) = λ X.F(X) ∩ λ X.G(X)

same for union