Midterm Flashcards
What are the steps to an inductive proof?
The first step is the basis step. You show that something holds of some minimal element (i.e. n = 0).
The second step is the induction step. It has two parts.
First is the induction hypothesis. Here, you assume that something holds for n = k.
Second, you prove that if it holds for n = k then it holds for n = k+1.
What is an interpretation?
An interpretation of P is an assignment to each propositional symbol of P either T or F.
What is semantic consequence?
A⊨B iff there is no interpretation of P for which A is true and B is false.
What is syntactic consequence?
A formula A is a syntactic consequence in PS of a set R of formulas of P iff there is a derivation in PS of formula A from set R.
What is a theorem? What is a metatheorem?
A formula is a theorem in PS just in case there is some proof of that formula.
What is a proof?
A proof is a finite sequence of one or more formulas of P, each which is either an axiom or an immediate consequence of two formulas preceding it.
*In a proof in PS, every formula is a theorem.
Every proof in PS is a derivation in PS of the last formula of the theorem it proves from the empty set, and also any formulas of P.
What are the axiom schema of PS?
[PS1] A -> (B -> A)
[PS 2] (A -> (B -> C)) -> ((A -> B) -> (A -> C))
[PS 3] ( ~A -> ~B) -> (B -> A)
*Note, these aren’t axioms of P because ‘A’ ‘B’ ‘C’ aren’t symbols of P. Things are axioms in P ‘in virtue of’ these schemata. Any wff of P of the form of the schema is an axiom.
What is the rule of inference for PS?
If A and B are any formulas of P, then B is an immediate consequence in PS of the pair of formulas A and (A -> B). [Modus ponens]
What is p-consistency?
A set of formulas, R, is p-consistent iff there is no formula A such that A is a syntactic consequence of R and ~A is a syntactic consequence of R.
What is logical validity?
A is a logically valid formula of P [⊨p] iff A is
true for every interpretation of P.
What is semantics?
Having to do with the interpretation of formal languages.
What is syntax?
Having to do with formal systems without regard to interpretation.
What is a formula? What is a wff?
A formula is a string of marks.
What is a model? What is model theory?
A model of a formula of a language is an interpretation of the language for which the formula comes out true. Model theory is the theory of interpretations of formal languages.
What is the continuum hypothesis?
There is no cardinal greater than aleph naught, and smaller than the power set of natural numbers.
What is disjunctive normal form?
A formula is in DNF iff it is a disjunction of conjunctions.
What is TF-connective adequacy?
A set of TF connectives is adequate iff any truth function can be expressed by some formula or other in a formal language containing only those connectives.
What is a derivation?
A string of formulas is a derivation in PS of a wff A from a set R of wffs of P iff (1) it is a finite, but not empty, string of formulas (2) the last formula in the string is A (3) either i. each formula in the string is an axiom ii. is an immediate consequence of two formulas preceding it iii. is a member of the set R.
What is denumerability?
A set is denumerable iff there is a 1-1 correspondence between it and the set of natural numbers.
What is simple consistency?
A formal system, S, is simply consistent iff there is no formula A in language S such that both A and ~A are theorems of S.
What is a wff?
A well-formed formula is a formula (string of marks) created using formation rules and an alphabet.
What is a subset?
A set x is a subset of a set y iff every member of x is also a member of y.
What is a proper subset?
The proper subsets of a set are all its subsets othan than that set itself.
What are the natural numbers?
0, 1, 2, 3…
