The metamathematics tag has no usage guidance.

**56**

votes

**29**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 ...

**24**

votes

**1**answer

2k 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 ...

**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) ...

**21**

votes

**13**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 ...

**21**

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

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

**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, ...

**16**

votes

**4**answers

2k 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 ...

**15**

votes

**12**answers

5k 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 ...

**13**

votes

**5**answers

2k 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 ...

**13**

votes

**3**answers

1k 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 ...

**12**

votes

**4**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.
...

**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$ ( $...

**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 \...

**11**

votes

**2**answers

1k 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 ...

**10**

votes

**3**answers

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

**9**

votes

**2**answers

463 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 $...

**8**

votes

**3**answers

1k 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 ...

**6**

votes

**5**answers

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

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

**6**

votes

**2**answers

1k 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 link));...

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

**6**

votes

**2**answers

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

**6**

votes

**3**answers

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

**5**

votes

**5**answers

971 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 A$...

**5**

votes

**1**answer

1k 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?
...

**5**

votes

**2**answers

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

**5**

votes

**1**answer

110 views

### Is it possible to prove concentration bounds from optional stopping theorem?

It is known that the optional stopping theorem from martingale theory is a very powerful theorem in probability theory in statistics.
I have heard of a probability course at Stanford where ...

**5**

votes

**0**answers

109 views

### Gleason’s Theorem for non-separable Hilbert spaces: On a theorem of Solovay

Gleason’s theorem plays an important role in the foundations of
quantum mechanics. On the positive side it demonstrates how the probabilistic
structure of quantum theory follows from its logical ...

**4**

votes

**9**answers

2k 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. ...

**4**

votes

**3**answers

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

**4**

votes

**1**answer

491 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 (i....

**4**

votes

**1**answer

485 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 $...

**4**

votes

**1**answer

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

**3**

votes

**1**answer

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

**3**

votes

**2**answers

2k 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 ...

**3**

votes

**1**answer

821 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

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

**3**

votes

**1**answer

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

**2**

votes

**3**answers

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

**2**

votes

**2**answers

454 views

### How much faith should I put in numerics? [closed]

Edit: Let me summarize what this question was meant to ask. Is there a quantitative theory of "approximate" soundness? Arguments are usually either sound or unsound. This is binary. If we don't ...

**1**

vote

**2**answers

323 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

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

**1**

vote

**3**answers

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

**1**

vote

**1**answer

248 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) ...

**1**

vote

**0**answers

207 views

### The theory of frames and locales as elementary topology [closed]

In What is elementary geometry? (pdf) Alfred Tarski defined elementary geometry to be
that part of Euclidean geometry which can be formulated and established without the help of any set-...

**1**

vote

**0**answers

475 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

**0**answers

211 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 first-...

**1**

vote

**1**answer

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

**0**

votes

**4**answers

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