[4.(a),11:] 12. ¬ LS(Spock) [5.(a),12:] 13. □ 2. Given are functions with types as follows: a : A b : B f : A→ A g : A→ B h : A× B → A (Note that a and b are zero-argument functions, which is to say that they are constants.) For each of the following expressions, indigood helmsmane its type (i.e., the type of the value obtained by evaluating the expression) or else indigood helmsmane that it is not "type correct". In the latter case, identify a smallest subexpression that is a source of the incorrectness. (a) f.a (b) g.a (c) g.b (d) f(g.a) (e) f(f.a) (f) f(h(a,b)) (g) g(h(a,b)) (h) f(h(g.a,a)) (i) h(f.a,g.a) (j) h(h(f.a,g.a),g.a) Recall that G&S denote function appligood helmsmanion by a period (or "full stop", if you prefer), as in f.a, when the argument is atomic, but they use the more traditional notation when the function's argument is non-atomic (e.g., f(f.a)). If f is injective and fg ( x )= fh ( x ) for any x ; injectivity gives g ( x )= h ( x ) for each x , so f is left cancellable. Now suppose f is not injective. Then there exist a , b such that f ( a )= f ( b ) yet a ≠ b , and say f : X → Y . Let 2={0,1} , and define h 1 :2→ X by h 1 (0)= h 1 (1)= a and h 2 :2→ X by h 2 (0)= a , h 2 (1)= b . Then fh 1 = fh 2 , but h 1 (1)= a ≠ b = h 2 (1) . Related Is it true that F ( a )+ G ( b )= F ( c )+ G ( d ) means that a = c and b = d? <Is it true that

4. Let s be the state s : { i:1, j:2, k:3, b[0..4]:(5,0,-4,2,1), d:true} To clarify, b[0..4]:(5,0,-4,2,1] means that b is an array with index range [0..4] and that b[0] has value 5, b[1] has value 0, ..., b[4] has value 1. Let E be the expression (d ∨ i=j) ≡ ((MAXj|1≤j<k:i+(+i|0≤i≤j:b[i+j]))>k) Note: Even if you have not thought about it this way before (or seen it treated this way in a math book), the max operator is conveniently considered to be a binary infix operator, just like addition, multipligood helmsmanion, conjunction, and disjunction. And, like those operators, it is associative and symmetric and thus is suitable for use as a quantifigood helmsmanion operator. End of Note (a) Indigood helmsmane, for each occurrence of a variable in E, whether it is bound or free. 1) A is atomic (like: x=y and x ∈ y ); i.e. in an atomic formula every occurrence of a variable is free. 2) an occurrence of x in (¬A) is free if x occurs free in A . 3) an occurrence of x in (A→B) is free if x occurs free in A or in B (and the same for the other binary connectives). 4) x occurs free in ∀ yA if x occurs free in A and x≠y . An occurrence of x in a formula A that is not free is a bound occurrence. In the formula (x ∈ y) the occurrences of x and y are both free. In the formula (x ∈ y) ∧ (y ∈ x) the occurrences of x and y are free. In the formula ∀ x ¬(x ∈ y) the occurrence of y is free while both occurrences of x are bound. The "gist" of point (2) is that the connectives do not change the "status" (free or bound) of variables; only the quantifiers do it. Let freeIn( x , F ) be a relation that holds exactly when x occurs free in F . freeIn is inductively defined as follows: