All Questions
6,026 questions
24
votes
8
answers
6k
views
Choice vs. countable choice
This question arose after reading the answers (and the comments to the answers) to Why worry about the axiom of choice?.
First things first. In my intuitive conception of the hierarchy of sets, the ...
- 1,848
256
votes
16
answers
71k
views
Why worry about the axiom of choice?
As I understand it, it has been proven that the axiom of choice is independent of the other axioms of set theory. Yet I still see people fuss about whether or not theorem X depends on it, and I don't ...
8
votes
1
answer
281
views
Ideals of statements?
The following is a somewhat vague question concerning logic, but with ideas from algebraic geometry (see in particular the example at the end). The vagueness is in the notion of "language".
Let $A$ ...
- 8,659
4
votes
5
answers
2k
views
Analytic Functions over Fields other than Real or Complex Numbers
Let K denote either the field of real numbers or the complex fields. An analytic function over $K^n$ is a function that can be represented locally by a convergent power series in n variables with ...
user2529
41
votes
6
answers
13k
views
Can we prove set theory is consistent?
Disclaimer
Of course not, I'm aware of Gödel's second incompleteness theorem. Still there is something which does not persuade me, maybe it's just that I've taken my logic class too long ago. On the ...
- 14.7k
8
votes
1
answer
1k
views
Why does this sum depend on the Axiom of Choice?
On page 168 of Mathematical Fallacies and Paradoxes, it states that the fact that the series
$1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \cdots $
has a sum depends on the Axiom of Choice. Where ...
- 1,823
-4
votes
3
answers
2k
views
Infinite CPU clock rate and hotel Hilbert [closed]
Suppose we have a computer with infinte CPU clock rate, infinite CPU registers, storage etc. Lets run a program that could look something like this:
A=1
while A>0
A = A+1
repeat
We start the program ...
- 49
34
votes
5
answers
1k
views
Does the exact pair phenomenon for partial orders occur in your area of mathematics?
Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if
...
- 236k
17
votes
2
answers
2k
views
Why is Kleene's notion of computability better than Banach-Mazur's?
In this post about the difference between the recursive and effective topos, Andrej Bauer said:
If you are looking for a deeper explanation, then perhaps it is fair to say that the Recursive Topos ...
- 9,201
7
votes
4
answers
1k
views
`Topos' with alternate subobject lattice?
We know that for any topos E, and for any object A in E, the subobjects of A, Sub(A), form a Heyting lattice.
Does anybody know of any sort of modification of the definition of a topos that makes Sub(...
- 855
0
votes
2
answers
172
views
small extensions of the free semigroup of rank 1
Let N denote the free semigroup of rank 1. Say that a semigroup T is a small extension
of N if N embeds in T and |T - N| is finite. Is there some kind of classification
of small extensions of N? ...
- 91
2
votes
4
answers
621
views
Provability of termination. Whats wrong with my reasoning?
Let A be a pair (i, x)
$H(A)$ <=> program i halts on input x
$P(A)$ <=> (there exists a proof for $H(A)$) $\vee$ (there exists a proof for $\neg H(A)$)
Assume $\forall A: P(A)$ then we can ...
- 31
3
votes
1
answer
394
views
Ultimate limits of Tennenbaum's Theorem
This is version 2 of a question about the ultimate limits of Tennenbaum's Theorem. The attempt to find these limits by moving up the induction heirarchy, as in Wilmer's Theorem, seems somehow ...
- 6,199
34
votes
2
answers
3k
views
"Transitivity" of the Stone-Cech compactification
Let $\beta \mathbb{N}$ be the Stone-Cech compactification of the natural numbers $\mathbb{N}$, and let $x, y \in \beta \mathbb{N} \setminus \mathbb{N}$ be two non-principal elements of this ...
- 114k
3
votes
1
answer
205
views
characterization of regular languages among (say) those computable in linear time
For a given language A let A(n) denote the number of words in A of length smaller or equal to n. It is know that if A is a regular language then the function $ f(x) = \sum_{i=0}^\infty A(n)x^n$ is in ...
- 3,897
19
votes
3
answers
3k
views
Can you show rank E(Q) = 1 exactly for infinitely many elliptic curves E over Q without using BSD?
Let $K$ be a number field and let $\mathcal O_K$ be the ring of integers. Following this paper of Cornelissen, Pheidas, and Zahidi, a key ingredient needed to show that Hilbert's tenth problem has a ...
- 3,268
9
votes
2
answers
844
views
Connection between the two-variable case of Hilbert's Tenth Problem and Roth's Theorem.
Connection between Hilbert's Tenth Problem and Roth's Theorem.
The following two decision problems seem to be open:
Given a polynomial equation in two variables with integer coefficients, determine ...
- 6,199
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
- 236k
7
votes
1
answer
583
views
A Diophantine Decision Problem
Let $S$ be a subset of $\mathbb{R}^n$ defined by a system $\theta$ of polynomial inequalities with integer coefficients.
Let's say that $\theta$ has no integer solutions "for trivial reasons" if ...
- 6,199
13
votes
2
answers
1k
views
Ultrafilters vs Well-orderings
This question was actually asked by John Stillwell in a comment to an answer to this question. I thought I would advertise it as a separate question since no one has yet answered and I am also ...
- 32.1k
2
votes
5
answers
903
views
Proofs that require the existence of large finite numbers
I know some proofs require the existence of large infinite ordinals, they give the fuel that drives induction principles. An example of this is the use of ε0 to give a consistency proof of ...
11
votes
2
answers
2k
views
How hard is it to solve SAT if the promise is that it has an odd number of solutions?
SAT is NP-complete even if we promise that it has an even number of solutions (by introducing a new dummy variable). However, USAT (when the promise is that it has exactly one solution) is not known ...
- 19k
96
votes
16
answers
34k
views
Most 'unintuitive' application of the Axiom of Choice?
It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even ...
6
votes
1
answer
455
views
Mechanically instantiating abstract constructions
I am looking for work on the effective inverse of abstraction, aka specialization.
There are two ways in which abstraction helps us:
Get a better understanding of the structural rules at play in ...
- 11.8k
8
votes
2
answers
991
views
Higher-order axiomatisations of Euclidean Geometry?
I am currently thinking about the possibility to axiomatise Euclidean Geometry using higher-order axioms. The idea is that all objects are points, and that we only have two primitive notions: A three ...
- 1,228
4
votes
1
answer
358
views
Prime-ness checking for polynomial ideals over ACFs( algebraically closed fields).
Let $f_1,\ldots f_m \in k[X]$ have degrees bounded by $l$. and $I(\bar{f})$ be the ideal generated by $\bar{f}$.
If $I(\bar{f})$ is not a prime ideal then its non-primeness is witnessed by polynomials ...
- 255
4
votes
1
answer
967
views
Contradiction to axiom of foundation
Consider the usual language and axioms of ZF. Now add constants $x_1, x_2, \dots$ to the language together with the axioms $x_2\in x_1, x_3\in x_2, \dots$ to form a new theory. Then by the compactness ...
- 2,967
10
votes
1
answer
549
views
A decision problem concerning Diophantine inequalities
Let $S$ be a subset of $\mathbb{R}^n$ defined by a system $\theta$ of polynomial inequalities with integer coefficients. Let $S+\mathbb{Z}^n$ be all points of the form $s+z$ with $s \in S$ and $z \in \...
- 6,199
10
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 ...
- 1,376
2
votes
1
answer
625
views
Finite axiomatizability and constructible sets
In the development of constructible sets via the Gödel operations, one of the main point seems to be that for $\Delta_0$ formulas, one can construct the sets of of elements verifying them with a ...
- 3,804
6
votes
1
answer
554
views
What is a reference for an explicit, logic-based, statement of duality in category theory (in ''complicated'' situations)? And what are the prerequisites for a beginner in logic?
Background
In the course of reading Mac Lane linearly (currently in Chapter VI),
I have seen again and again that duality can make life much easier. My
problem is that I have almost no background in ...
- 1,411
46
votes
4
answers
5k
views
What was Gödel's real achievement?
When I first heard of the existence of Gödel's theorem, I was amazed not just at the theorem but at the fact that the question could be made precise enough to answer: how on earth, even in ...
- 29k
7
votes
2
answers
1k
views
candidate for rigorous _mathematical_ definition of "canonical"?
In this question: What is the definition of "canonical"?
, people gave interesting "philosophical" takes on what the word "canonical" means. Moreover I percieved an underlying opinion that ...
- 41.4k
60
votes
6
answers
7k
views
Has decidability got something to do with primes?
Note: I have modified the question to make it clearer and more relevant. That makes some of references to the old version no longer hold. I hope the victims won't be furious over this.
Motivation:
...
- 2,824
32
votes
6
answers
5k
views
How do we recognize an integer inside the rationals?
My question is fairly simple, and may at first glance seem a bit silly, but stick with me. If we are given the rationals, and we pick an element, how do we recognize whether or not what we picked is ...
- 18.7k
2
votes
1
answer
424
views
Degrees many-one below $0^\omega$
Is there any nice categorization of degrees of sets which are many-one reducible to $0^{\omega}$? ($0^{\omega}$ is the set whose nth column answers which $\Sigma_n$ statements are true in $(\mathbb{N},...
- 255
3
votes
3
answers
464
views
Can you tell if you have escaped from a recursive definition?
Most people define a function, f(n) on N recursively. I think I can calculate f(n) without dealing with f(n-r) for any 0 < r < n. How do I know that my method isn't still going through the same ...
- 466
6
votes
5
answers
2k
views
A book explaining power and limitations of Peano Axioms?
Are there books or survey articles explaining the subject to a non-expert? To clarify what I mean, here is a couple of issues that I would like to read about. (I am mainly interested in references but ...
- 32.4k
20
votes
7
answers
2k
views
Extensional theorems mostly used intensionally
Some theorems are stated and proved extensionally, but in practice are almost always used intensionally. Let me give an example to make this clear -- integration by parts:
$$ \int_a^b f(x)g'(x)ds = \...
- 11.8k
58
votes
9
answers
8k
views
How do they verify a verifier of formalized proofs?
In an unrelated thread Sam Nead intrigued me by mentioning a formalized proof of the Jordan curve theorem. I then found that there are at least two, made on two different systems. This is quite an ...
- 32.4k
10
votes
5
answers
5k
views
Examples of inductive proofs that can be generalized by transfinite induction
Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial ...
29
votes
2
answers
5k
views
What is the manner of inconsistency of Girard's paradox in Martin Lof type theory
I am aware that assigning the type of Type to be Type (rather than stratifying to a hierarchy of types) leads to an inconsistency. But does this inconsistency allow the construction of a well-typed ...
- 595
3
votes
1
answer
946
views
On statements provably independent of ZF + V=L
Are there any known statements that are provably independent of $ZF + V=L$? A similar question was asked here but focusing on "interesting" statements and all examples of statements given in that ...
- 33
-2
votes
1
answer
780
views
commutative monoids have binary products? [closed]
Does the category CMonoid of commutative monoids have binary products?
thanks
- 1
5
votes
1
answer
3k
views
Does the category Monoid of monoids have finite coproducts?
Does the category Monoid of monoids have finite coproducts?
- 67
2
votes
2
answers
465
views
When forcing with a poset, why do we order the poset in the order that we do?
In forcing, we take a collection of forcing conditions and impose a partial order on them. The convention is that if $p$ is stronger than $q$, then we say $p < q$. This is perfectly fine, but it ...
- 1,793
2
votes
1
answer
658
views
Higher-order, multi-sorted, non purely equational version of universal algebra ?
I have been looking around, unsuccessfully, for generalizations of universal algebra based on higher-order logic (rather than first order) and where the relations are not purely equational. ...
- 11.8k
-1
votes
1
answer
358
views
Properties of collections (functions) that make them proper classes (uncomputable)
There are collections too big to be a set, e.g. the collection of all sets (in ZFC), and there are collections that cannot be sets for "pure" logical reasons, e.g. the collection of sets that do not ...
- 9,720
42
votes
2
answers
6k
views
A question about ordinal definable real numbers
If ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice) is consistent, does it remain consistent
when the following statement is added to it as a new axiom?
"There exists a denumerably ...
- 6,215
5
votes
5
answers
2k
views
Defining 'free monoid' without Nat?
Is there a definition of what is a 'free monoid' which does not pre-suppose that the natural numbers has already been defined? The definitions that I have been able to track down all use the natural ...
- 11.8k