Questions tagged [metamathematics]
the mathematical discipline that applies mathematical methods to the study of mathematical theories themselves.
96
questions
5
votes
1
answer
213
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 ...
- 103
5
votes
1
answer
2k
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,328
5
votes
1
answer
1k
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 ...
- 897
4
votes
1
answer
514
views
Can adding Hilbert's epsilon to a theory, and then expanding that theories axiom schema to include the new language, cause it to become inconsistent?
Epsilon Calculus is a formalism developed by Hilbert adding his $\epsilon$ operator to predicate logic. $\epsilon x. A(x)$ is a term such that $\exists x.A(x) \implies A(\epsilon x.A(x))$. In can ...
- 5,821
4
votes
1
answer
735
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....
- 5,692
4
votes
2
answers
473
views
Experiments physically performable in a finite amount of time whose results are independent of ZFC [closed]
In On independence and large cardinal strength of physical statements we see that their are physical statements which are independent of ZFC, and even strong cardinal axioms. There were many answers, ...
- 5,821
4
votes
2
answers
779
views
What things does ZFC not know if it knows?
The statement "ZFC $\vdash 0=1$" is independent of ZFC due to Goedel's second incompleteness theorem. That got me wondering, for what other statements $\phi$ is "ZFC $\vdash \phi$" independent of ZFC?
...
- 5,821
4
votes
1
answer
2k
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 ...
- 41
4
votes
0
answers
140
views
Are the relations of being homeomorphic or being homotopy equivalent on the compact polyhedra definable in the structure of the natural numbers?
Let $ K(\mathbb{N}) $ denote the set of all finite simplicial complexes with vertices in $\mathbb{N}$.
Let $ f\colon \mathbb{N} \to K(\mathbb{N}) $ be a computable bijection.
Let $ R $ = { $ (m, n) $ |...
- 41
4
votes
0
answers
402
views
How can I prove that primitive recursion “preserves” representability in Peano Arithmetic?
I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.
By recursive function ...
- 49
4
votes
0
answers
283
views
the strength of saying "each sentence of true arithmetic has a recursive proof"
Let $PA_{\omega}$ be just like $PA$ except that $PA_{\omega}$-proofs can use any number of applications of the recursive $\omega$-rule.
The recursive $\omega$-rule allows the following:
For each ...
- 449
3
votes
1
answer
442
views
Is there an equivalent of the incompleteness theorems/halting problem in category theory?
Taking the doctrine of computational trinitarianism ( https://ncatlab.org/nlab/show/computational+trinitarianism ), if one understands the incompleteness theorems as the "logic" version, and ...
- 141
3
votes
1
answer
348
views
Can you formulate a theory stating that a truth predicate does not exist for first order set theory?
A truth predicate for first order set theory would allow you to determine the truth of statements in first order set theory. A definition is given here.
My question is, can you formulate a statement ...
- 5,821
3
votes
1
answer
857
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 ...
- 1,475
3
votes
1
answer
295
views
Unorthodox constructive reasoning: The Kleene Getaway
KG (the Kleene Getaway) is the name I improvised (in my answer to a question on MO on constructive Perron-Frobenius) for a constructive principle which enables the direct constructive use of a ...
- 1,606
3
votes
1
answer
151
views
Does CZF prove there is a minimal cauchy completion of the rationals?
In IZF, we can easily prove there is a minimal cauchy complete field extending the rationals: the dedekind reals are cauchy complete, so just intersect all of its cauchy complete subfields.
CZF can ...
- 5,821
3
votes
1
answer
384
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 ...
- 7,613
3
votes
0
answers
272
views
Can we prove the epsilon theorems without the axiom of choice?
Hilbert's epsilon $\epsilon$ is a quantifier. It follows the rule that if $\exists x. p(x)$, for some predicate $p$, we can infer $p(\epsilon x. p(x))$. Semantically, it represents picking some ...
- 5,821
3
votes
0
answers
251
views
A theory which denies the existence of a truth predicate
Is there a paper or other reference that explores the implications of a theory that denying the existence of a truth predicate in its own language (perhaps based on ZFC or PA)?
I know that a theory ...
- 5,821
2
votes
3
answers
584
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 ...
- 1,596
2
votes
1
answer
269
views
Possible to prove a lemma from Godel's completeness theorem in intuitionistic logic?
I am trying to determine whether a particular theorem used in the course of Godel’s (1930) proof of the completeness of predicate logic could be proven in an intuitionistic metatheory.
Theorem VI (p....
- 583
2
votes
1
answer
412
views
ZFC ability to express truth and $\omega$ - consistency
Some theories can lie about their own consistency (for example, if $PA$ is consistent then the theory $PA + \lnot CON(PA)$ is consistent, although it proves its own inconsistency).
Now working with ...
- 257
2
votes
1
answer
643
views
Is ZFC plus a truth predicate capable of variable substitution consistent?
Let us define a truth predicate that allows one to substitute in variables. For example, for a 3-ary predicate $p$ and sets $A$, $B$, and $C$, then $\text{true}(\ulcorner p \urcorner, A, B, C)$ (where ...
- 5,821
2
votes
1
answer
170
views
Internal operations on uncomputable functions
Is there know set of operations for which uncomputable functions are, let's name it down-unclosed? I mean a set of operations which takes two ( or more) uncomputable functions and return computable ...
- 1,596
2
votes
0
answers
231
views
A formal definition of a useful theorem?
Sorry if this feels a bit squishy, but I'm wondering if there is any published work trying to give a fully formal definition of the notion of a useful theorem. I mean, in mathematics we all know that ...
- 2,633
2
votes
0
answers
95
views
How restrained are we in terms of metatheories when working with higher order logics with full semantics?
When working in the realm of first order logic one can use very basic mathematical backgrounds(in reverse mathematical sense) to prove interesting things about more "structures".
In what ...
- 743
2
votes
0
answers
363
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,102
2
votes
2
answers
497
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
753
views
Can you remove all the extra arithmetic from ZFC (or other theories)?
Let $\mathbb{N}$ be the standard model of the natural numbers. For any statement in the language of arithmetic, we can translate into a statement in the language of set theory by asking if it is true ...
- 5,821
1
vote
2
answers
467
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 ...
- 9,628
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
978
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 ...
- 15
1
vote
1
answer
342
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,596
1
vote
1
answer
1k
views
Question about the validity of Michael Grossman, Robert Katz and Jane Grossman Non-Newtonian / Meta / Multiplicative Calculus [closed]
I am no mathematician by far, but I have studied diff. and integral calc and beyond, in my undergrad years. I recently came upon this book:
"The First Systems of Weighted Differential and ...
- 127
1
vote
0
answers
95
views
Questions in proof theory (PRA-provability of EA-theorems, Girards book from '87)
I've been working through a textbook, often encountering difficulties with the exercises.
On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
1
vote
0
answers
106
views
n-consistency - provability/truth of $\Sigma^0_n$ and $\Pi^0_{n+1}$ -formulas; n-consistent extensions, etc
I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
1
vote
0
answers
124
views
Can $GPK^{+}_{\infty}$ + $AC_{WF}$ prove "$ZFC$ proves that the class of ordinals is not weakly compact for definable classes?
Consider the topological set theory $GPK^{+}_{\infty}$ +$AC_{WF}$, where $GPK^{+}_{\infty}$ is defined as follows (this from Olivier Esser's papers, "An Interpretation of the Zermelo-Fraenkel Set ...
- 6,024
1
vote
0
answers
620
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 ...
- 11
1
vote
0
answers
222
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-...
- 9,628
1
vote
1
answer
580
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 ...
- 223
0
votes
4
answers
309
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 ...
- 9,628
0
votes
1
answer
126
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".
- 1
0
votes
0
answers
158
views
Are the HBL derivability conditions necessary for Gödel's incompleteness theorems? (For Löb's theorem?)
I've been working through a textbook, often encountering difficulties with the exercises.
On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
-1
votes
1
answer
568
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 ...
- 11.7k
-4
votes
1
answer
196
views
Is there a procedure to derive models from axiomatic systems? [closed]
Is there a systematic procedure to construct a model of an axiomatic system from the system itself?
For example given the abstract postulates of a ring we can show that the integers satisfies them ...
- 4,792
-5
votes
1
answer
467
views
How much would a mathematician cost? [closed]
Recently our department lost one of the best professors who was attracted by a better University. If we were a football club, and he were a leading player, we would receive many millions of ...