Philosophy 3340
Symbolic Logic II

First Examination - Review
Spring, 2010

Sets, Functions, Relations

• relation between set and its elements: membership; relations between sets: subset, proper subset
• functions on sets: union, intersection, powerset, Cartesian product
• relation: set of ordered pairs
• kinds of relations: reflexive, symmetric, transitive, equivalence; antisymmetry, asymmetry, irreflexivity
• function: set of ordered pairs, no two of which have the same first member and different second members
• a function relates two sets: it is from a set A to a set B. (So each of the ordered pairs "in" the function has a first member from A and a second member from B.) We say f: A -> B to indicate that the function f is from A to B.
• domain, range
• one-to-one/not one-to-one, onto/not onto (given two sets, should be able to construct functions that have any combination of one property from each pair)
• total vs. partial function
• inverse function

Informal Proofs

• You should be able to prove simple results in set theory, and also proofs about the syntax or semantics of propositional and first-order logic (i.e. proofs similar to the homework problems). Remember that we prove a universal claim, e.g. "all X that have property P also have property Q," by considering an arbitrarily chosen instance: "Let a be any arbitrary set that has property F. [insert proof that a has G.] Therefore, every set with F also has G."
• You should be able to do simple inductive proofs. (Remember, you need a base step and an inductive step. The inductive step involves assuming an inductive hypothesis.)

Induction, Recursion

• An inductive definition is a specification of a set. We need a base clause, an inductive clause, and a closure clause.
• When we have an inductively defined set, we can use proof by induction to show that every element of the set has a given property.

Propositional Logic

• truth assignment h
• extension of a truth assignment to the whole language (h-hat)
• definition of tautological consequence, tt-satisfiability
• soundness theorem for propositional logic (You don't need to be able to prove it, but should know what it says and know in general terms how to go about proving it)
• completeness theorem for propositional logic: if a sentence S is a tautological consequence of a set of sentences T, then S is provable from T using the propositional rules
• definition of formal consistency
• be able to explain why, to prove the Completeness Theorem, it suffices to prove that every formally consistent set is tt-satisfiable
• definition of formal completeness
• procedure for extending a formally consistent set to a formally complete, formally consistent set
• strategy for proving that a formally complete, formally consistent set is tt-satisfiable (the general idea is to give a recipe for building a truth assignment that makes all sentences in the set true. What's the recipe?)

First Order Logic

• inductive definitions of term, formula, free variable, sentence
• semantics: structure, domain (universe), variable assignment, definition of the denotation of a term
• definition of satisfaction (you don't need to be able to reproduce it but you should understand what it's doing and how it works; for instance if I have you a clause of the definition you should be able to explain what it means)
• definition of truth
• definition of first-order consequence and first-order satisfiability
• given a language L, be able to explain what the extended language L_H is
• witnessing constant
• for an extended language L_H, what is the Henkin theory H?