relation between set and its elements: membership; relations between sets:
subset, proper subset
functions on sets: union, intersection, difference, powerset, Cartesian
product
relation: set of ordered pairs
kinds of relations: reflexive, symmetric, transitive, equivalence;
antisymmetry, asymmetry, irreflexivity
partial ordering, linear ordering
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)
inverse function
composite function (given functions f, g you should be able to say what
the composite function fg is)
know what the characteristic function of a set is
Informal Proofs
You should be able to prove simple results in set theory. Remember our
notational conventions: capital letters represent sets, lower-case letters
represent items that are not sets; in both cases, letters late in the alphabet
are variables and letters early in the alphabet are constants. So X is a
variable ranging over sets; A is the name of a particular set; x is a variable
ranging over non-set items; and a is a constant that refers to a particular
non-set item. 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 P. [insert proof that
A has Q.] Therefore, all X with P also have Q."
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.
A recursive definition is a specification of a function. Suppose we have
an inductively defined set A, and we want to define a function f from A to
another set B. (Example: A = PL, B = {T, F}.) We begin by specifying the value
(image) of f for each element of the base on which A is defined. Then we add
clauses corresponding to the inductive clauses in the definition of A. These
clauses extend f to the rest of A.
Propositional Logic
PL-assignment
admissible PL-assignment
atomic PL-assignment, extension of an atomic PL-assignment
how many admissible extensions of an atomic PL-assignment are there? Why?
(You don't need to be able to prove the answer rigorously, but should be able
to explain informally why there is at least one and why there is at most one.)
Unique Readability Theorem. You don't need to be able to prove this
rigorously, but should be able to explain what it says and, informally, why
it's true.
Formal Systems (Material from Hofstadter)
Axioms
Rules
Syntax: which strings are well formed?
Semantics
consistency, completeness
Recursive Transition Networks (RTNs): should be able to construct an RTN
for aspects of FOL similar to those in GEB or the one we constructed for PL,
for example should be able to build an RTN for a term of FOL, supposing we
already have definitions for constant and variable.
inside and outside the system
proofs vs. derivations (what's the difference? How is it related to the
distinction between working inside or outside the system?)