The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
210 views

If there is a Reinhardt cardinal, then there is one universe? [closed]

If there is a nontrivial elementary embedding $j:V \to V$, then there is a universe which contains all the large cardinals. Is there such a universe? Does this imply there is one universe from ...
0
votes
1answer
135 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
1answer
157 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
3answers
286 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
2answers
985 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 ...
0
votes
1answer
106 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
vote
0answers
208 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
1answer
312 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
1answer
299 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
0answers
439 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
3answers
481 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 ...
6
votes
5answers
768 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
vote
2answers
970 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 ...
6
votes
5answers
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
1answer
407 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
3answers
866 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 ...
3
votes
1answer
460 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
8answers
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 ...
3
votes
1answer
454 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 ...
12
votes
5answers
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 ...
9
votes
3answers
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
5answers
833 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 ...
10
votes
3answers
623 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
2answers
580 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 ...
9
votes
10answers
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 ...
21
votes
1answer
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
3answers
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$ ( ...
19
votes
6answers
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 ...
4
votes
1answer
750 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 ...
22
votes
8answers
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) ...
6
votes
7answers
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
1answer
814 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$ ...
0
votes
1answer
519 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
3answers
950 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
1answer
931 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? ...
3
votes
9answers
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
4answers
279 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 ...
18
votes
8answers
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, ...
2
votes
3answers
469 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 ...
9
votes
3answers
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. ...
1
vote
0answers
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
3answers
487 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 ...
2
votes
2answers
397 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 ...
18
votes
11answers
1k 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 ...
51
votes
28answers
5k 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 ...
6
votes
2answers
754 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 ...