Logic

From MGSA
Jump to: navigation, search

Foundations

  • Explain to a mathemtician what you mean by a sentence (for example, in the language of groups). Explain the syntax and semantics of this language.
  • What does the completeness theorem tell us about the sentences in this language? What about arbitrary sets of sentences?
  • What does the completeness theorem say about the valid sentences of number theory?
  • What can you say about the axiom system P of number theory?
  • What does the undecidability of Q tell you about the valid sentences in the language of number theory?
  • What is meant by a relation definable in the standard model of number theory?
  • Are all arithmetical relations Σ1 definable? Why?
  • What does the completeness tell a group theorist?
  • Let σ be a first order sentence. Suppose a group theorist has proved (in some fashion, not necessarily first order) that σ is true of all torsion free groups. What can you tell him?
  • Does the completeness theorem tell us taht there is a way for us to decide, given a first order sentence, whether it is true for all group?
  • Is ZF decidable? Is the consistency of P decidable in ZF?
  • What is Church's thesis? Why can't it be proved?
  • What is Beth's Theorem? Sketch a proof.
  • Is the complete theory of \langle \omega,+,\cdot\rangle model complete?
  • What is the Compactness Theorem? How is it proved?
  • What sets are definable in \langle \omega, {\rm S}\rangle? What do you know about \langle \omega,{\rm S}\rangle? Is it finitely axiomatizable?
  • What sets are definable in \langle\omega,{\rm S}\rangle in second order logic?
  • In what sense is every first order sentence equivalent to a Σ sentence? A \forall\exists sentence?
    • Does the above require the Axiom of Choice?
  • Is the second order theory of \langle\omega,{\rm S}\rangle decidable?
  • Do you know a natural essentially undecidable finitely axiomatizable subtheory of ZF?
  • Do you know a sytactical equivalent to model completeness?
  • What decidable theories do you know?
  • How do you prove Gödel's Incompleteness Theorem?
  • Is ZF finitely axiomatizable?
  • Is there a theory T such that {\mathcal A} is a model of T iff {\mathcal A} is a finite group?
  • Is there a theory T such that a sentence σ holds in T if and only if σ holds in every finite group?
  • What important properties does Q have? (The theory Q of Tarski's {\it Undec. Theories}).
  • Prove that if a theory T has no complete axiomatizable extension, tehn T is undecidable.
  • Do you know any theories with denumerably ennumerable models?
  • Give your favorite system of propositional calculus, and show that this system is uniquely readble. Give a procedure for reading formulas.
  • Let L be the language with 0, s, + , \cdot. Let T be the theory in L whose only non-logical axiom is s_x\cdot s_y = x\cdot y + (x+s_y). Is T decidable?
  • Is there a theory in which the Gödel sentence expressing inconsistency is true, and yet which is consistent? Why?
  • Use the Completeness Theorem to prove the existence of non-Archimedean fields.
  • State the downward Löwenheim-Skolem Theorem.
  • Give an example to show why it is important to have "elementary substructure" and not just "elementary equivalent structure" in the downward Löwenheim-Skolem theorem.
  • Define recursive function, recursive set, and recursevely ennumerable set.
  • What is the most important result about representability and what is it used for?
  • Is there an undecidable theory with just one mathematical symbol?
  • Do you know anything interesting about propositional calculus?
  • What is the most general form you know of Gödel's Theorem?
  • Name a decidable theory. How do you know it is decidable?
  • What is meant by a proof?
  • What is meant by a categorical theory? Give an example.
  • Can one define \vee in terms of \rightarrow?
  • What is the relation between completeness and compactness?
  • Is the set of Σ1 sentences true in \langle\omega, +,\cdot\rangle recursively ennumerable? Is it recursive?
  • What is the difference between recursive and primitive recursive?
  • Give a purely algebraic characterization of ECΔ classes.
  • What is an elementary class? (Silver)
    • Are the cyclic groups an elementary class?
    • Are the torsion groups an elementary class?
  • How do you prove that the theory of algebraically closed fields of characteristic zero is decidable? (Silver)
  • Why is a complete axiomatizable theory decidable? (Silver)
  • What is Gödel's Second Incompleteness Theorem? (Silver)

Set theory

  • Are there measurable ordinals?
  • Draw a Venn diagram showing recursive, recursively ennumerable, co-recursively ennumerable, primite recursive, arithemtical, second order definable sets, and implicitly definable sets. State Beth's Theorem, and show where the following sets fall, and explain why:
    • Th(ω, + ), Th(ω,S).
    • Sets definable in second order theory of \langle\omega,+\rangle.
    • ({\mathbb Q},+,\cdot), (\omega,+,\cdot).
    • Universal validities and existential validities
    • Theory of groups; universal sentences of group theory.
    • \forall\exists sentences.
    • {\rm Th}(\R,+,\cdot), {\rm Th}(\Z,+\cdot).
  • Prove the recursion theorem and Rice's theorem.
  • Show that any uncountable well-ordered set has a countable well-ordered subset.
  • Define "representable set".

This page was originally derived from this TeX file.

Retrieved from "http://www.ocf.berkeley.edu/~mgsa/wiki/Logic"
Personal tools