since it’s the only thing that makes sense to me in regards to my logic homework tonight.

To set the stage we need to do a little be on functions though…

F: A –> B range (f) is the set of values from B to which f
takes numbers of A.
S: Natural # –> Natural # ran(S):{1,2,3,…}

If ran(f)=B we say f maps A and B. if for every element
ran(f), there is only an xЄA such that f(x)=y, then f is one to one.

If f(x)=f(y) then x=y

Let f, h be functions. We say their ranges are disjoint when
there are no x,y such that F(x) =h(y). (their ranges have no elements in
common.)

F: AxB –> C eg. +: NI x NI à NI
Let |S be the set of wffs

Є¬ : |S –> |S

Є≡: |S x |S –> |S where ≡ is a binary connective.

Formula building functions are one to one on wffs and have
disjoint ranges. (Freely generated)

(α ^ β)
= (γ ^ δ) implies α = γ and β =
δ one to one.
Disjoint
ranges (α ^ β) /= (γ v δ)

Set
|S of wffs is freely generated by the formula building fns.
Natural
#s freely generated by S (successor)

n+1 =
m+1 n = m

Natural
#s freely generated by S, +–> addition is not one to one.They
also don’t have disjoint ranges. Everything is a successor.
S(2)
= 3 = 1+2

 
alrighty.. now, with those definitions I can dive into a little recursion

f(0)
= 0 | f = (0)

f(1)
= 2 | f (n+1) = 2+f (n)

f(2)
= 4 | f(3) ? 3 = 2+1

f(n)
= 2n | f(3) = f(2+1) = 2 + f(2) = 2+4= 6

  f(2) = f(1+1) = 2+f (1) = 2+2 = 4

  f(1) = f(0+1) = 2+f(0) = 2+0 = 2

  f(0) = 0

 

Where
recursion doesn’t work:
NI is
not freely generated by s, x

Example:

h(0)
= 0

h
(n+1) = h (n) + 2

h
(nxm) = h (n) x h(m)
1 =
0+1 successor of 0
1 =
(0+1) x (0+1) multiply successor of 0
h
(1) = h (0+1) = h (0) +2 = 0+2 =2
h (1)
= h ((0+1) x (0+1)) = h (0+1) x h (0+1) = 2×2 = 4

Fails
because successor and x’s don’t freely generate. There are 2 different way to
calculate value of 1 #.

 

The
rules have conflicting instructions. The ranges of the functions were not
disjoint.
H is
defined a S.S
H
defined on negation/binary connection, you won’t get conflicting instructions.
You always know what rule to apply.

Start with v on sentence symbols, extend it using recursion
to |v on all wffs.
How do we know |v exists? – is it a function?

Special case of recursion theorem:

What we know: The formula building functions freely generate
the set of wffs. (Freely generated – a) generates all effs b) on to one c)
disjoint ranges.)
For each binary connective ≡, we have a function:

f≡: {F,T} x {F,T} à {F,T} defined by the
truth table (shown below for this particular case).
f^
f^ (T,F) = F
f^ (T,T) = T

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

A	B	f^
T	T	T
T	F	F
F	T	F
F	F	F

 

Theorem: Given that the formal building operations freely
generate the set |S of wffs, given a function v:S à {F,T}, which is a
truth assignment on sentence symbols then there is a unique |v: |S à
{F,T}

 

i) for AЄ|S, |v(A) = v(A)

ii) for α, βЄ|S, |v ((α≡β)) = f≡ (|v(α)), (|v(β)) and
|v((¬α)) = f¬(|v(α))

 

Example:

Suppose v(A) = T, v(B) = F, v(C) = T
|v ((A^(¬B)) à (C v A) = ? … f à (|v(A^(¬B))), (|v(C v
A))

α = (A^(¬B))
β = (C v A)
|v((A^(¬B)) = f^ (|v(A)), (|v(¬B))
|v(A) = v(A) = T
|v(¬B) = f¬(|v(B)) f¬ (B) = T (negation of B)
= f^ (T, T) = T

|v (( C v A)) = fv (|v (C), (|v(A)) = fv (T,T) = T

α = T
β = T
f (T, T) = T.

However, how do we prove the theorem?

(this may, or may not make sense, we’re doing it *tomorrow* in class…however, I’m fairly certain I’ve got it under control.)
Prove – Then there is a unique |v: |S à
{F,T}. Call a function acceptable if it satisfies (i) and (ii).
(Calculated in the same way as |v, using the same rules) Let |v be the union of all acceptable functions. This means:
|v (β) = T when ever all acceptable functions defined on β are T given β.
To do this we need to show all acceptable functions agree.

 

• Definition of |v
  • Gives us a function. All acceptable functions agree
    • If h and g are acceptable functions defined and β, then h(β)= g(β) (Recall
             acceptable functions agree on sentence symbols) This therefore proven by
             induction
• Does this |v satisfy the conditions?
  • Is it defined on all of |S?
    • Show that there is always a way to extend an acceptable function to an
             acceptable function. If h is defined on α and β then h, such that h1((α≡
             β)) = f≡(h(α)), h(β) is acceptable
  • Does it satisfy (i) and (ii)?
    • Follows from definition of |v as union of acceptable functions
• Show |v is unique
  • Follows from the fact that acceptable functions agree