Midterm Flashcards

1
Q

What are the steps to an inductive proof?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an interpretation?

A

An interpretation of P is an assignment to each propositional symbol of P either T or F.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is semantic consequence?

A

A⊨B iff there is no interpretation of P for which A is true and B is false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is syntactic consequence?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a theorem? What is a metatheorem?

A

A formula is a theorem in PS just in case there is some proof of that formula.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a proof?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the axiom schema of PS?

A

[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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the rule of inference for PS?

A

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]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is p-consistency?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is logical validity?

A

A is a logically valid formula of P [⊨p] iff A is

true for every interpretation of P.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is semantics?

A

Having to do with the interpretation of formal languages.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is syntax?

A

Having to do with formal systems without regard to interpretation.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is a formula? What is a wff?

A

A formula is a string of marks.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a model? What is model theory?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the continuum hypothesis?

A

There is no cardinal greater than aleph naught, and smaller than the power set of natural numbers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is disjunctive normal form?

A

A formula is in DNF iff it is a disjunction of conjunctions.

17
Q

What is TF-connective adequacy?

A

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.

18
Q

What is a derivation?

A

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.

19
Q

What is denumerability?

A

A set is denumerable iff there is a 1-1 correspondence between it and the set of natural numbers.

20
Q

What is simple consistency?

A

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.

21
Q

What is a wff?

A

A well-formed formula is a formula (string of marks) created using formation rules and an alphabet.

22
Q

What is a subset?

A

A set x is a subset of a set y iff every member of x is also a member of y.

23
Q

What is a proper subset?

A

The proper subsets of a set are all its subsets othan than that set itself.

24
Q

What are the natural numbers?

A

0, 1, 2, 3…

25
What are the integers?
-3, -2, -1, 0, 1, 2, 3...
26
What is a power set?
The set of all subsets of A is the power set of A.
27
What is Cantor's theorem?
The power set of a set always has a greater cardinality than the set itself.
28
What are truth functions?
A truth function is a function whose domain is a set of sequences of truth values and whose range is a subset of the set of truth values. A truth function is a function whose arguments and values are truth values.
29
What is '⊨'?
Semantic consequence.
30
What are the rational numbers?
1, 1/2, 3/4, 2...
31
What are the real numbers?
The continuum...
32
What is proof theory?
Proof theory is the theory of formal systems that does not require any reference to interpretation (model theory).
33
What is a metatheorem?
A metatheorem is a theorem (true statement) about some formal system in the metalanguage.
34
What are rules of inference?
A set of transformation rules (also called rules of inference) that determines which relations between formulas of L are relations of immediate consequence in S. (Intuitively, the transformation rules license the derivation of some formulas from others.)
35
OTHER WORK:
1. Show TF Adequacy. 2. Semantic proof of simple consistency. 3. Mathematical induction. 4. 1:1 Correspondence. 5. Decimal expansion. 6. Proof of deduction theorem.