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.
