The metamathematics tag has no wiki summary.

**9**

votes

**2**answers

209 views

### Is there a compendium of the consistency strength between the most important formal theories?

Preliminar Notions:
A formal system is a tuple $(\Sigma,G,A,R)$ where $\Sigma$ is an alphabet (set of symbols), $G$ is a formal grammar on $\Sigma$ that generates a formal language $L$ (set of well ...

**12**

votes

**12**answers

3k views

### The best text to study both incompleteness theorems

Hi!
What text on both incompleteness theorems you would recommend for beginner?
Specifically, I'm looking for the text with the following properties:
1) The proofs should be finitistic, in Godel's ...

**11**

votes

**2**answers

1k views

### Existential statement without witness

Are there existential theorems of ZFC, or PA say, with no witnesses?
Ie does there exist a formula $\phi$ such that ZFC $\vdash\exists x \phi(x)$, but for all numerals $\underline{n}$, ZFC $\nvdash ...

**3**

votes

**1**answer

333 views

### Applications of line graphs

I am trying to collect a few examples of applications of line graphs in sciences other than mathematics. To be more precise: I am thinking of models where there is a clear conceptual added value in ...

**1**

vote

**2**answers

282 views

### Rationale behind an requirement on Turing machines

Hopcroft and Ullman's definition of a Turing machine seems to be standard. This definition defines a Turing machine to be a 7-tupel $T = \langle Q,\Gamma,b,\Sigma,\delta,q_0,F \rangle$ obeying some ...

**1**

vote

**1**answer

326 views

### Is there any current development of a first order formalization of metamathematics?

I hope that this post isn't off topic, but I already asked math.stackexchange about first order formalizations of first order logic. There are provability logics and extensions in modal logic's that ...

**4**

votes

**2**answers

860 views

### Meta$^{n{-}th}$ mathematics [duplicate]

Metamathematics has a reasonably clear connotation,
enough to have a Wikipedia page,
with Gödel, Tarski, and Turing playing leading roles;
Kleene's book (Introduction to Metamathematics (Amazon ...

**9**

votes

**2**answers

366 views

### How necessary is Godel's Condensation Lemma

It seems that the Godel's Condensation Lemma is typically used to show that certain constructible sets will appear by some stage of the construction of $L$. For example in the proof that CH holds in ...

**6**

votes

**5**answers

827 views

### Formal proof of Con(ZFC) => Con(ZFC + not CH) in ZFC

Is it possible to prove $Con(ZFC) \rightarrow Con(ZFC + \neg CH)$ purely within ZFC? To prove this (using forcing) one seems to need a countable transitive model of ZFC. The texts I am reading avoid ...

**-1**

votes

**1**answer

194 views

### What is an example of a non-axiomatic mathematical system? [closed]

In this wikipedia article on the foundations of mathematics, it says:
In practice, most mathematicians ... do not work from axiomatic systems
Is this correct? If so, what is an example of this?

**1**

vote

**1**answer

183 views

### Nontrivial, partially uncomputable function

is there any example of function which is computable on some set and uncomputable on other set? That is for example function f(n) which is computable on some (finite, or for example for even numbers) ...

**3**

votes

**3**answers

339 views

### Embedding Theorem for topological spaces, and in general

There are many examples throughout mathematics of abstracting the formal properties of a "familiar" structure, but then having a theorem stating that all models of the abstract axioms embed into one ...

**2**

votes

**2**answers

1k views

### In What Sense is Set Theory a 'Foundation' for Mathematics? [closed]

In what sense is set theory a foundation for mathematics? To my mind (for what that is worth), there are at least three (somewhat) distinct senses in which set 'theory' (I put "theory" in scare ...

**12**

votes

**5**answers

1k views

### Consistency strength needed for applied mathematics

Given that we can never proof the consistency of a theory for the foundations of mathematics in a weaker system, one could seriously doubt whether any of the commonly used foundational frameworks (ZFC ...

**0**

votes

**1**answer

107 views

### $\epsilon$-Formalization of Undecidability of CH

Can the statement
CH is not provable in ZFC
be formalized as en $\epsilon$-Formula $\phi$ s.t. $ZFC \vdash \phi $
If so why is it refered to as an "metatheorem".

**51**

votes

**28**answers

6k views

### Can infinity shorten proofs a lot?

I've just been asked for a good example of a situation in maths where using infinity can greatly shorten an argument. The person who wants the example wants it as part of a presentation to the general ...

**1**

vote

**2**answers

1k views

### An undergraduate's guide to the foundational theorems of logic [closed]

How would you explain one of these theorems in the foundations of mathematics to a fellow colleague outside the field of logic (or rather to an undergraduate mathematics student) handwaving over the ...

**3**

votes

**1**answer

474 views

### subset sum problem when the number of integers in the sum is known

Hi everyone,
I'm trying to solve a variation of the subset sum problem (http://en.wikipedia.org/wiki/Subset_sum_problem) in which all the integers that I'm using are strictly positive and (most ...

**3**

votes

**1**answer

311 views

### Godel 's Ladder: Undecidable PI_N sentences for N =2, 3, …

After Godel's groundbreaking results, a plethora of $\Pi_1^0$ undecidable arithmetical sentences have been found by many authors.
But what about $\Pi_n^0$ for $n=2,3,.....$ ?
There are, to my ...

**1**

vote

**0**answers

458 views

### Arguments against Reductio ad Absurdum [closed]

Could Reductio ad Absurdum not be consireded a valid proof method? Are there any compelling arguments against it, or at it's favor?
I feel like I am assuming some metamathematical hypothesis about my ...

**1**

vote

**3**answers

545 views

### Applicability of Deduction theorem to Primitive recursive arithmetic [closed]

Hello. I already asked the question here. The main point is that I tried to prove in Primitive recursive arithmetic (PRA) the totality of the Ackerman function, and I found, that the single thing ...

**22**

votes

**8**answers

2k views

### Intuitive and/or philosophical explanation for set theory paradoxes

Every student of set theory knows that the early axiomatization of the theory
had to deal with spectacular paradoxes such as Russel's, Burali-Forti's etc.
This is why the (self-contradictory) ...

**18**

votes

**8**answers

3k views

### Proofs of Gödel's theorem

I am interested in different contexts in which Gödel's incompleteness theorems arise. Besides traditional Gödelian proof via arithmetization and formalization of liar paradox it may also be obtained ...

**6**

votes

**5**answers

2k views

### A meta-mathematical question related to Hilbert tenth problem

I am reading Bjorn Poonen's very nice survey on Hilbert's Tenth problem
(http://www-math.mit.edu/~poonen/papers/uniform.pdf), and while I believe I understand the mathematics well, I have widespread ...

**4**

votes

**1**answer

431 views

### Does ZF prove that a finite subtheory axiomatizes it over transitive proper class models?

If $\text{ZF}$ is consistent, then it is not finitely axiomatizable. For if $\Gamma$ is a finite axiomatization, then $\text{ZF}$ proves by reflection that $\Gamma$ has a set model, and hence (since ...

**13**

votes

**3**answers

906 views

### Are there examples of nonconstructive metaproofs?

This came up in a question on the xkcd forums. Is it possible to have a nonconstructive metaproof, i.e. a proof that there exists a proof in some formal system which does not construct said proof? Are ...

**19**

votes

**6**answers

2k views

### Complete mathematics

Hello, I would like to ask you if there is a mathematical theory, that is complete (in the sense of Goedel's theorem) but practically applicable. I know about Robinson arithmetic that is very limited ...

**3**

votes

**1**answer

516 views

### Feferman's extensional and intensional applications of the method of arithmetization

At the very beginning of Feferman's Arithmetization of metamathematics in a general setting it can be read:
The method of arithmetization, as developed by Gödel[10], exploits the possibility of ...

**18**

votes

**8**answers

1k views

### Cryptomorphisms

I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are
Topological Spaces. These can be defined in terms of open sets, ...

**3**

votes

**1**answer

465 views

### Should consistency be considered as a concept in the metatheory?

Consider the statement: "ZFC is consistent". Normally this is considered at first sight as a statement in the metatheory. But if we follow Kunen's (informally) description of what the metatheory is ...

**10**

votes

**3**answers

1k views

### Don't the axioms of set theory implicitly assume numbers?

When one writes down the axioms of ZFC, or any other axiomatic theory for that matter, and making statements like "let x, y ..." doesn't this assume an understanding (and thus existence) of natural ...

**4**

votes

**5**answers

904 views

### “Let $x \in A$”, beginning a proof of “$\forall x \in A$ …”, if A were empty [closed]

I work at a four-year teaching school, where we pride ourselves on teaching pure math, proof, and a rather obsessive carefulness of work. Recently I have been criticized for saying that "Let $x \in ...

**24**

votes

**1**answer

1k views

### Is there a common genesis for ADE classifications?

Recall that a certain type of object admits an ADE classification if there is a notion of equivalence relative to which equivalence classes of objects of the given type can be placed in one-to-one ...

**10**

votes

**3**answers

650 views

### Complete Extensions of First Order Logic (or Language)

Lindstrom's theorem states that any extension of FOL more expressible than FOL fails to have either compactness or Lowenheim-Skolem. When I first read Lindstrom's theorem my first reaction was: "Does ...

**5**

votes

**2**answers

604 views

### Are computable models sufficient?

What I mean is this. By downward Lowenheim-Skolem theorem, first-order formula Q is a always true iff it is true in every countable structure. But is there some first-order formula Q which is true in ...

**12**

votes

**3**answers

1k views

### Are there natural examples of mathematical statements which follow from consistency statements?

Motivation
One of the methods for strictly extending a theory $T$ (which is axiomatizable and consistent, and includes enough arithmetic) is adding the sentence expressing the consistency of $T$ ( ...

**10**

votes

**3**answers

3k views

### Bourbaki's epsilon-calculus notation

Bourbaki used a very very strange notation for the epsilon-calculus consisting of $\tau$s and $\blacksquare$. In fact, that box should not be filled in, but for some reason, I can't produce a \Box.
...

**18**

votes

**11**answers

2k views

### Are there any good nonconstructive “existential metatheorems”?

Are there any good examples of theorems in reasonably expressive theories (like Peano arithmetic) for which it is substantially easier to prove (in a metatheory) that a proof exists than it is ...

**6**

votes

**7**answers

1k views

### The isomorphism inference rule

Suppose we are writing very detailed proofs, absolutely without any gaps (for example, for checking proofs by computer).
In such formal proofs every step (even a trivial one) must be justified.
For ...

**4**

votes

**1**answer

771 views

### Bourbaki theory of isomorphism, examples of untransportable formulas

In their book "Theory of sets" Bourbaki suggested a general theory of isomorphism.
(See also http://www.tau.ac.il/~corry/publications/articles/pdf/bourbaki-structures.pdf )
The example of an ...

**6**

votes

**1**answer

842 views

### Using the multiverse approach to decide the law of the exluded middle?

Recently, in response to deciding the Continuum Hypothesis $CH$, Hamkins and Gitman have proposed consider a multiverse of set-theoretic universes, some in which $CH$ is true, some in which $\neg CH$ ...

**4**

votes

**9**answers

1k views

### Are there any important mathematical concepts without discrete analog?

In "continuous" mathematics there are several important notions such as covering space, fibre bundle, Morse theory, simplicial complex, differential equation, real numbers, real projective plane, etc. ...

**0**

votes

**1**answer

526 views

### Formal definition of 'useful' ?

Has anyone worked out a formal, general-enough definition of what is 'useful', so that it could reflectively be used in mathematics? I am aware of the work in utility theory from economics (but ...

**8**

votes

**3**answers

988 views

### Is there a formal notion of what we do when we 'Let X be …'?

This is likely an elementary question to logicians or theoretical computer scientists, but I'm less than adequately informed on either topic and don't know where to find the answer. Please excuse the ...

**5**

votes

**1**answer

969 views

### Is there a known way to formalise notion that certain theorems are essential ones?

Suppose You ask a question beginning from "Why some structure is..." or "Why some object has property..." and several
answers arises. Which criteria do You
use to qualify which answer is correct?
...

**0**

votes

**4**answers

282 views

### Deficiency of necessary conditions

Motivation
Consider the situation: You know that
every $x$ that has property $P$ must have property $Q$. $Q$ is a
rather strong condition but not strong
enough to fulfill $P$. What is ...

**2**

votes

**3**answers

482 views

### Given is “model”. How many theories may it be a model?

Usually we have axiomatic theory and the we look for model for it - this is book picture. Of course in real math usual one has a "model" that is given structure and looks for proper axiomatizing of ...

**6**

votes

**3**answers

506 views

### What assumptions and methodology do metaproofs of logic theorems use and employ?

In logic modules, theorems like Soundness and completeness of first order logic are proved. Later, Godel's incompleteness theorem is proved. May I ask what are assumed at the metalevel to prove such ...

**1**

vote

**0**answers

206 views

### Classification of properties of structures

Is there a sensible classification of the properties of structures with a given signature $\sigma$, e.g. graphs with $\sigma = \lbrace R \rbrace$?
For example like this:
properties defined by ...

**6**

votes

**2**answers

803 views

### “Requires axiom of choice” vs. “explicitly constructible”

I think I'm a bit confused about the relationship between some concepts in mathematical logic, namely constructions that require the axiom of choice and "explicit" results.
For example, let's take ...