# Tagged Questions

The tag has no usage guidance.

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 ...
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 ...
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) ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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. ...
1k views

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

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