Recursively Enumerable vs. Recursive Sets Flashcards
Theorems:
Theorems: Strings can be derived from the axoims and inference ruels of the system
Non-Theorems:
Well-formed strings that are not theorems
Recursively Enumerable (sets):
Can be generated as theorems of a formal system
The Figure
Recursive (sets):
Both theorems and non-theorems (wff that are not theorems) can be generated by a formal system
Both the set and its complement are r.e.
the Figure and Ground
Every recursive set is r.e.
If it is recursive then it has a decision procesure - decidable
There are r.e. sets that are not recursive
Relation between Recursive and R.E. sets:
- Every recursive set is r.e.
- If it is recursive then it has a decision procesure - decidable
- There are r.e. sets that are not recursive
Why must a recursive set be decidable?
Generate the theorems and the non-theorems.
Any well-formed string will appear in one or the list after a finite amount of time
How to build a formal system for multiplication:
x * 1 = x
x * (n + 1) = (x * n) + x
What is a composite number?
A number is composite, if it is obtained by multiplying two numbers each of which is greater than 1 (denoted at C)
Ex: C-System
Relation between composite and prime numbers:
Numbers that are not composite are prime
Therefore - Recursive
Ex: in the C-System, all strings of the form Cx are divided into the C-System into composite (theorems) and primes (non-theorems)
Quiz 2
Is a set of prime numbers recursive? if yes, say why; if not, say why not.
Yes. Using the C-system (of composite numbers), both theorems and non-theorems (primes) can be derived.
Meaning, it is recursive - the figure (composite numbers) and the ground (primes)
Quiz 2
What is the name of the relation between syntactic and semantic consequence if set of formulas entails x then the set of formulas proves x?
Completeness
Quiz 2
⊢_(AX) A
What does this mean?
In the axiomatic calculus system, the cconclusion A is proven from no open assumptions
Quiz 2
(a) Tautology, (b) Logical theorem, (c) Derivation, (d) Truth table, and (e) inference rule
Say whether the following notions are syntactic or semantic:
(a) Semantic
(b) Syntactical
(c) Syntactic
(d) Semantic
(e) Syntactic
Quiz 2
What are the cardinalities of the following sets?
(1) The wffs of propositional logic,
(2) The tautologies of propositional logic, and
(3) the wffs of propositional logic that are not tautologies.
ℵ0
