Formal Systems

Question 1

Investigation of a formal system:

Answer 1

(1) Find limitations and (2) conditions uder which they are obtained

Question 2

Difference between syntax and semantics:

Answer 2

Syntax: formal structure, grammer
Semantics: meaning and contect

Ordinary language there two are tightly connected and we do not precieve the distiction.

To be explicit, put word in quotation marks when mentioned, not when we use it.
Ex:
(a) Bruce is eating
(b) “Bruce” has two vowels

Interpretation: Both syntax and semantics. (“Connects”) Gives semantics to syntax

Question 3

Parts of a formal system:

Answer 3

1. Alphabet (from which we form well-formed strings)
2. Axoims
3. Inference Rules

Theorems are the product of a formal system.

Derivations are non-empty, well-formed sequences contructed from the axoims or inference rules of the formal system.

Question 4

Define a meta-variable:

Answer 4

Use in a recursive definition about the variables (Syntax)

Used to specify inference rules. Not part of the alphabet

Like x and y in the MIU system

Question 5

What are well-formed strings?

Question 6

What is a derivation?

Answer 6

Non-empty sequence of well-formed strings, each of which either an axiom or derived from applying the inference rules to items occuring earlier in the derivation (Recursive Definition)

Explicitly: Derivation is a non-empty sequence of strings, such that each string is either an axoim or obtained from strings that are earlier in the sequences by one of the inference rules

Question 7

What is a theorem?

Answer 7

A theorem is the last string in a derivation

Other definitions:
(1) “Last line in a proof”
(2) “Theorems: strings can be derived from axioms and inference rules”

Question 8

What aspects of theorems and rules in a formal system are inductive and deductive?

Answer 8

1. Derive a few theorems: induction
2. Reason about rules of system: deductive

Question 9

What is the difference between inside and outside the system?

Answer 9

M-Mode: Mechanical mode (inside)
Reasoning within the formal system

I-Mode: Intellegent mode (outside)
Reasoning about formal system

Question 10

Difference between object and meta-language:

Answer 10

Object language (strings in M-Mode) and meta-language (strings in I-Mode)

Question 11

What is a decision procedure?

Answer 11

Procedure that:
1. Guarantees a yes-answer or a no-answer to a question (bivalence)
2. After a finite amount of time

If a question has a decision procedure, it is decidable

Axoims of a formal system must be determined by a decision procedure.

Question 12

When is a set decidable?

Answer 12

If the question is ‘Is x an element of the set?’ then it is decidable for all elements x