All Questions
6,026 questions
8
votes
2
answers
1k
views
Weakest subsystems of second order arithmetic for mathematical logic
It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it?
What about the incompleteness theorems? Is ...
- 1,465
34
votes
8
answers
8k
views
Arithmetic fixed point theorem
I want to understand the idea of the proof of the artihmetic fixed point theorem. The theorem is crucial in the proof of Gödel's first Incompletness theorem.
First some notation: We work in $NT$, the ...
- 63.1k
14
votes
3
answers
2k
views
Has there ever been a weaker Church-like thesis?
Background. The Church-Turing thesis, in one of its many equivalent formulations, states that the intuitively computable arithmetical functions are exactly those computed by Turing machines.
...
- 1,185
3
votes
0
answers
559
views
Unprovability of the Steiner-Lehmus theorem
Conway postulated that the Steiner-Lehmus theorem is unprovable using direct methods of proof. Can this be proven directly, that the Steiner-Lehmus theorem cannot be proven directly over Euclidean ...
- 131
12
votes
1
answer
1k
views
How to locate the paper that established Robinson Arithmetic?
If I'm not mistaken, it was in his seminal paper “An Essentially Undecidable Axiom System”, published in
Proceedings of the International Congress of Mathematicians (1950), 1952:729–730,
where R.M. ...
- 2,992
13
votes
7
answers
7k
views
Are real numbers countable in constructive mathematics?
We are talking about ordinary reals in constructive mathematics.
Let represent each real number by infinite converging series:
$$r = [\;(a_0,b_0),(a_1,b_1),...,(a_i,b_i),...\;]$$
$$where\quad a_i \...
16
votes
1
answer
2k
views
Sneaky Recursive Non-Well-Orders
Background
An ordinal $\alpha$ is called a recursive ordinal if there is a recursive well-order $R$ on $\mathbb{N}$ such that ordertype($\mathbb{N},R) = \alpha$. For example, $\omega\cdot 2$ is a ...
- 1,601
3
votes
4
answers
720
views
How much are reduced powers different?
Given two infinite sets $X$ and $I$, and a filter ${\cal F}$ on $I$, one defines as usual the equivalence relation $\approx_{\cal F}$ on $X^I$ and obtains the reduced power $Y = X^I / \approx_{\cal F}$...
2
votes
1
answer
199
views
Lowering order of theory
Let define procedure for converting second order theory to first order:
Take any second order theory with equality
Invent sort Bool' and new fresh constants F' and T', of sort Bool'
Create fresh sort ...
- 342
2
votes
1
answer
611
views
cardinal of a quotient space
Let $X$ be a nonvoid set of cardinal $\alpha$. Let $\cong$ be an equivalence relation on $X$. Let $\beta$ be the cardinal of the set
(1) $ D = \{ \, ( x, y ) \in X \times X ~|~...
60
votes
15
answers
11k
views
Abstract thought vs calculation
Jeremy Avigad and Erich Reck claim that one factor leading to abstract mathematics in the late 19th century (as opposed to concrete mathematics or hard analysis) was the use of more abstract notions ...
25
votes
3
answers
3k
views
Composite pairs of the form n!-1 and n!+1
It's well known that the numbers of the form $n!\pm1$ are not always prime. Indeed, Wilson's Theorem guarantees that $(p-2)!-1$ and $(p-1)!+1$ are composite for every prime number $p > 5$.
Is ...
- 44.4k
1
vote
1
answer
262
views
$\omega$-monoids
Does the notion of $\omega$-monoid exist, analogous to the notions of $\omega$-groupoid and $\omega$-category? If so, some references would be appreciated.
This is an attempted rephrasing of question:...
- 1,882
5
votes
2
answers
768
views
Are the types of nonstandard natural numbers within a Z-chain identical?
Hi,
I was wondering how much (if anything) $\mathcal{L}_{PA}$ can express about individual nonstandard elements in a nonstandard model of PA. For instance, presumably it can say that each has $k$-...
- 145
2
votes
0
answers
292
views
About Tarski's axioms A and A' (4): ZFC + Tarski-Grothendieck axiom
4-(suite): axiom A (or equivalently axiom TG) have powerfull consequences.
(i) It is easy to see that A1 and A2 prove the power-set axiom, by separation, because P(x is included inside the set y;
(ii)...
- 2,655
2
votes
0
answers
196
views
About Tarski's axioms A and A' (3): 16 equivalent axioms
3-On the same page (84) he states axioms A and A', Tarski also considers the 16 following axioms variants for A and A' and asserts witout giving a proof that they are all equivalent.
Axiom C: "For ...
- 2,655
2
votes
0
answers
160
views
About Tarski's axioms A and A' (2): transitive sets
2-By A'2, every set y satisfying axiom A' must be a transitive set. But it is not true that every set y satisfying axiom A must be transitive. So, it seems natural to ask the following.
Question 2: (i)...
- 2,655
3
votes
1
answer
332
views
About Tarski's axioms a and A' and around (1)
1-In his article written in German "Über unerreichbare Kardinalzahlen" (On inaccessible cardinals), inside Fund. Math. 1938 (pages 68-89), Alfred Tarski states his axioms A and A' as follows.
Axiom A: ...
- 2,655
10
votes
2
answers
1k
views
Cohomology Theories on The Stone Space of Complete n-types
Just a random thought here: Can cohomology theories (e.g. sheaf cohomology) on the Stone space $S_n(T)$ (the space of complete n-types) of a first-order theory $T$ tell us anything interesting (e.g. ...
- 468
3
votes
5
answers
793
views
Derivation rules and Godel theorem
Every formal theory is a collection of alphabet, axioms and derivation rules. My question is - what kind of "derivation rules" are acceptable here. For example, "from A B it follows $A \cup B$" is a ...
- 189
27
votes
2
answers
2k
views
Is there a name for a family of finite sequences that block all infinite sequences?
Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} \...
- 114k
86
votes
7
answers
21k
views
How many orders of infinity are there?
Define a growth function to be a monotone increasing function $F: {\bf N} \to {\bf N}$, thus for instance $n \mapsto n^2$, $n \mapsto 2^n$, $n \mapsto 2^{2^n}$ are examples of growth functions. Let's ...
- 114k
2
votes
4
answers
951
views
Monadic Second Order (MSO) logic on graphs
Given a conflict graph $G = (V, E)$, a man has to transport a set $V$ of items/vertices across the river. Two items are connected by an edge in $E$, if they are conflicting and thus cannot be left ...
- 53
20
votes
5
answers
3k
views
[solved] sequent calculus as programming language
intuitionistic logic ~ programming
natural deduction ~ lambda-calculus
Hilbert system ~ combinatory logic {S, K}
Gentzen system=sequent calculus ~ ?
What would you write in place of the question ...
- 530
6
votes
1
answer
1k
views
Can we hope to solve all Diophantine equations?
According to Godel result, neither ZFC nor other particular theory is strong enough to resolve all questions about, say, Diophantine equations. But maybe we can hope that a sequence of theories will ...
- 189
3
votes
4
answers
556
views
Deriving the complete set of "non-redundant" true statements in disjunctive form in propositional logic
Given a finite set of statements known to be true, I need to derive all the "non-redundant" statements in disjunctive form using only literals that can be derived from this set of statements, i e all ...
- 135
86
votes
10
answers
11k
views
What's wrong with the surreals?
Of all the constructions of the reals, the construction via the surreals seems the most elegant to me.
It seems to immediately capture the total ordering and precision of Dedekind cuts at a ...
- 1,843
2
votes
1
answer
261
views
Relation between different definitions of types [closed]
Is there any connection between the definition of type in model theory and the definitions from type theory? Is there any explanation why the same term is used for these notions, maybe in the ...
- 141
54
votes
5
answers
15k
views
The unification of Mathematics via Topos Theory
In her paper The unification of Mathematics via Topos Theory, Olivia Caramello says "one can generate a huge number of new results in any mathematical field without any creative effort". Is ...
- 1,190
16
votes
3
answers
19k
views
Non-computable but easily described arithmetical functions
I have read about the existence of functions of the kind described in the title in several places, but never seen an instance of them. Sorry if this is too much an elementary question to be posted ...
- 1,465
26
votes
9
answers
8k
views
Why are proofs so valuable, although we do not know that our axiom system is consistent? [closed]
As a person who has been spending significant time to learn mathematics, I have to admit that I sometimes find the fact uncovered by Godel very upsetting: we never can know that our axiom system is ...
17
votes
9
answers
3k
views
Direct construction of the integers
Question. Is there a direct construction of the integers which does not involve taking any quotients?
I am of course aware of the usual construction. I am also aware of the nice axiomatic ...
- 11.8k
7
votes
2
answers
3k
views
How to think like a set (or a model) theorist.
Kenneth Kunen in his “The Foundations of Mathematics” writes:
‘Set theory is the study of models of ZFC’ (p. 7)
‘Set theory is the theory of everything’ (p. 14)
With (1) Kunen is pointing to a ...
- 1,465
9
votes
3
answers
1k
views
Structure Theorem for finitely generated commutative cancellative monoids?
Is there a Structure Theorem for finitely generated commutative cancellative monoids?
Of course they can be densely embedded into a finitely generated abelian group, whose structure is known. Also, ...
- 63.1k
6
votes
4
answers
2k
views
Why is Cohen's result insufficient to settle CH?
OK, Cohen has constructed a model in which both ZFC and ~CH are true. Isn't this model an answer to the continuum problem? Hasn't he showed that it is indeed possible to construct a set with ...
- 551
1
vote
0
answers
260
views
Is this first-order statement true? [closed]
Consider the natural numbers $\mathbb{N}$ as a structure for NBG set theory.
If we interpret the Axiom of Unions in this structure, we get the statement
$(\forall a \in \mathbb{N})$ $(\exists w \in \...
- 21
150
votes
45
answers
30k
views
Nontrivial theorems with trivial proofs
A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because ...
5
votes
2
answers
899
views
Connection between the axiom of universes and Tarski's axiom
Grothendieck's axiom states that any set is a member of a Grothendieck universe (i.e. of a set that is closed under the subset, powerset, pairing and family-union relations), or equivalently, that ...
- 1,228
3
votes
1
answer
1k
views
About Grothendieck Universe and Tarski's A and A' Axioms
A-The addition of the Grothendieck Universe Axiom (for every set x, there exists a set y that is a universe and contains x as member element) to ZFC (ZFC+GU) is considered as giving an almost good ...
- 2,655
7
votes
3
answers
426
views
What are other theories of causality besides graphical models and Bayesian networks?
I am trying to find some data structures/mathemetical theories to represent causal relationships which differ from graphical models or Bayesian Networks. Any ideas?
- 71
31
votes
3
answers
3k
views
Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?
Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, ...
- 236k
17
votes
1
answer
1k
views
Some constructive versions of the Continuum Hypothesis are false. Are any true, or open?
Background
In constructive set theory (say based on CZF) there are inequivalent ways of stating the continuum hypothesis. Some of them are easily if not trivially refutable with common anti-classical ...
- 935
16
votes
2
answers
3k
views
Clarification of Gödel's second incompleteness theorem
I am sorry for the following question, because the actual answer to this question is in the beautiful works of Feferman and Jeroslow, but, unfortunately, I havn't any time to go into that specific ...
- 1,175
67
votes
5
answers
10k
views
Decidability of chess on an infinite board
The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
- 50.8k
10
votes
2
answers
506
views
When does replacement (accidentally) hold in amenable sets?
A set $M$ is called amenable if it is transitive and satisfies the following conditions:
For all $x,y\in M$, $\{x,y\}\in M$
For all $x\in M$, $\bigcup x \in M$
$\omega \in M$
For all $x,y \in M$, $x\...
- 1,601
42
votes
7
answers
3k
views
How would one even begin to try to prove that a simple number-theoretic statement is undecidable?
This question is closely related to this one: Knuth's intuition that Goldbach might be unprovable. It stems from my ignorance about non-standard models of arithmetic. In a comment on the other ...
- 29k
11
votes
4
answers
1k
views
Russell and Whitehead's types: ramified and unramified
I was reading Logicomix (a fictionalised account of logic from Frege to Gödel through Russell's eyes) and there was mention about two different versions of types developed by Russell and Whitehead for ...
- 35.5k
185
votes
11
answers
52k
views
Knuth's intuition that Goldbach might be unprovable
Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really ...
- 2,745
17
votes
1
answer
3k
views
Do these conditions on a semigroup define a group?
As is well known, if $S$ is a semigroup in which the equations $a=bx$ and $a=yb$ have solutions for all $a$ and $b$, then $S$ is a group. This question arose when someone misunderstood the conditions ...
- 7,217
14
votes
5
answers
2k
views
Formulas for the liar paradox
How can the liar paradox be expressed concisely in symbols? In which formal languages?
- 503