All Questions
6,026 questions
8
votes
2
answers
824
views
Ordinal Analysis of Peano Arithmetic with Restricted Induction
If we take Peano Arithmetic and restrict induction to formulas over various fragments of the arithmetic hierarchy, say to the $\Sigma^0_n$ formulas for various $n$ or some other interesting fragments, ...
- 1,439
16
votes
2
answers
3k
views
Can randomness add computability?
I have been looking at Church's Thesis, which asserts that all intuitively computable functions are recursive. The definition of recursion does not allow for randomness, and some people have suggested ...
- 3,475
5
votes
2
answers
571
views
Is it possible for P(N) to be larger than Aleph_omega?
I have seen a proof that $|\mathcal{P}(\mathbb{N})| \neq \aleph_\omega$ using the fact that $\aleph_\omega$ is the union of countably many smaller cardinals, while $|\mathcal{P}(\mathbb{N})|$ is not. ...
- 51
0
votes
1
answer
444
views
Saturated extensions of ZFC models
Hi, I would like some help on something that in some ways has already been touched in the past here. I saw these relevant questions being answered, but I am still unable to understand some things. I ...
- 3
22
votes
2
answers
2k
views
What is the largest Laver table which has been computed?
Richard Laver proved that there is a unique binary operation $*$ on $\{1,\ldots,2^n\}$ which satisfies $$a*1 \equiv a+1 \mod 2^n$$
$$a* (b* c) = (a* b) * (a * c).$$
This is the $n$th Laver table $(A_n,...
- 3,547
0
votes
2
answers
587
views
Is it true that a set is countable if and only if there exists a Turing machine to enumerate all the elements in the set? [closed]
In many textbooks, it is said that a set is countable if we can list the elements as $a_1, a_2, \dots$.
My question is: is it true that a set is countable if and only if there exists a Turing ...
- 29
12
votes
3
answers
877
views
Complementation of $\omega$-regular languages in reverse mathematics
Does anyone know where Büchi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over $\...
- 866
10
votes
2
answers
673
views
"Probabilistic ultrafilters?"
A naive question.
Let $S$ be a set and let $[0,1]^S$ the set of functions from $S$ to the closed interval $[0,1]$.
Suppose given some function $P \colon [0,1]^S \to [0,1]$ satisfying the following ...
- 19.2k
5
votes
1
answer
498
views
Percolation in Cayley graphs of semigroups.
Percolation in Cayley graphs of groups are studied by many researchers. There are also the concept Cayley graphs for semigroups. Are there any research about percolation in Cayley graphs for ...
- 6,211
76
votes
9
answers
6k
views
Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations?
The question is the extent to which we can unify addition
and multiplication, realizing them as terms in a single
underlying binary operation. I have a number of questions.
Is there a binary ...
- 236k
8
votes
4
answers
870
views
Self-defining structures
The relations $R$ in abstract graphs (with genuinely propertyless vertices) cannot be defined because there is nothing the relations can base on: they have to be presupposed.
But consider derived ...
- 9,720
0
votes
1
answer
147
views
Small set of acts over a countable monoid?
Given a countable monoid $S$, is the set of all (isomorphic representatives of) $S$-acts a small set?
- 11
1
vote
0
answers
203
views
Maximizing the number of 'correct' literals in planar monotone 3SAT
I'm trying to find the complexity of this optimization problem:
Given an instance of planar monotone 3SAT, with positive clauses $C_i = v_{i1} V v_{i2} V v_{i3}$ and negative clauses $D_i = not(w_{i1}...
- 1,182
1
vote
1
answer
2k
views
Slaman and Woodin on Mathematical logic
At the references section of the wikipedia article for Definable set, one finds the following entry:
Slaman, Theodore A. and W. Hugh Woodin. Mathematical Logic: The Berkeley Undergraduate Course. ...
- 1,465
39
votes
6
answers
7k
views
A remark of Connes on non-standard analysis
In an interview (at http://www.alainconnes.org/docs/Inteng.pdf) Connes remarks that
I had been working on non-standard analysis, but after a while I had found a catch in the theory.... The point is ...
- 1,131
6
votes
4
answers
11k
views
About the proof of the proposition "there exists irrational numbers a, b such that a^b is rational"
What does the classical proof of the proposition "there exists irrational numbers a, b such that $a^b$ is rational" want to reveal? I know it has something to do with the difference between classical ...
- 179
3
votes
1
answer
266
views
A question about the "information-content" of a very simple type of Turing machine.
All the Turing machines we consider have (1) a two-way infinite tape (2) one and only one halting
state (3) an alphabet of exactly two symbols-"1" and " "(or "blank"). Let n be any positive integer.
...
- 6,215
15
votes
0
answers
741
views
Minimal resources for Undecidability of First-Order Logic: the number of variables
It is well-known that First-Order Logic (FO) with a full vocabulary (i.e., a countable numbers of unary predicate symbols, a countable number of binary predicate symbols, etc.) is undecidable. And it ...
- 768
1
vote
1
answer
154
views
undecidability in the dynamics of functions $f: \Sigma^* \rightarrow \Sigma^*$
Does anyone know any undecidable problems in the dynamics of functions (not necessarily monoid homomorphisms or anything) from \Sigma^* to \Sigma^* where \Sigma is a finite set? In particular, I'm ...
- 549
12
votes
5
answers
1k
views
Predicates of infinite arity
Infinitary logic considers languages being infinite by infinite conjunctions and disjunctions.
I wonder why it not considers languages being infinite by relations and functions of infinite arity.
...
- 9,720
5
votes
2
answers
1k
views
What is the state of research on Horn Angles?
The ancient Greeks struggled with the concept of a horn angle, the "angle" formed by the intersection of two curves. The only information I find in Mathworld is that horn angles are examples of non-...
- 4,597
3
votes
1
answer
437
views
Axiomatizations of complete theories
This question was motivated by this recent question by Ricky Demer.
In his paper $\Pi^0_1$ classes and Boolean combinations of recursively enumerable sets, Carl Jockusch showed that there is no ...
- 44.4k
3
votes
1
answer
625
views
computable "completion" of ZFC
Let $f : \omega \to \{\text{wffs of set theory}\}$ be a function. Let $\leq_f$ be a total order on $\omega$.
Definition: $\langle f,\leq_f \rangle$ is a computable quasi-completion of ZFC if and ...
user5810
18
votes
2
answers
2k
views
What proofs cannot be relativized
I am afraid this post may show my naivety. At a recent conference, someone told me that there are some arguments in computability theory that don't relativize. Unfortunately, this person (who I ...
- 6,287
17
votes
12
answers
4k
views
Why semigroups could be important?
There is known a lot about the use of groups -- they just really appear a lot, and appear naturally. Is there any known nice use of semigroups in Maths to sort of prove they are indeed important in ...
- 1,437
7
votes
2
answers
1k
views
Are there uncountably many essentially inequivalent versions of Mathematics?
Hi everyone,
Disclaimer 1: logic and set theory are a long way from my field, so apologies in advance if I demonstrate extreme ignorance or stupidity, and please correct me if (when?) I write stupid ...
- 1,990
1
vote
1
answer
481
views
Is there a conjunction bias?
This is slightly related to question The unprecedented success of the “intersection” operator .
Apart from a set of maths books of null measure, most have the following property:
Objects ...
5
votes
3
answers
885
views
Additive functions on a lattice
Consider a lattice $L$. Can one classify all functions $f:L\rightarrow \mathbb{R}$, that satisfy
$f(a \wedge b)+f(a\vee b) = f(a)+f(b)$.
Some examples are the the set of all finite subsets of a given ...
- 11.1k
5
votes
1
answer
761
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,902
10
votes
5
answers
645
views
Syntactically capturing complexity classes
Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...
user10891
15
votes
5
answers
2k
views
Intended interpretations of set theories
In his Set Theory. An Introduction to Indepencence Proofs, Kunen develops $ZFC$ from a platonistic point of view because he believes that this is pedagogically easier. When he talks about the intended ...
- 1,465
5
votes
4
answers
2k
views
Subsystems of Peano arithmetic and incompleteness theorem
I think everyone is familiar with Goedel's incompleteness theorems. In particular they imply that PA (Peano arithmetic) can not prove its own consistency. Now my question is what is the largest ...
- 741
6
votes
2
answers
462
views
need references regarding the elementary theory of free semigroup and free abelian groups
Recently, I read that two free abelian groups $S$ and $T$ have the same elementary theory if and only if rank$S$=rank$T$. Does anyone have a reference with a proof of this? Also, what is known about ...
- 549
2
votes
2
answers
1k
views
Countable Fields with No Countable Extension
Let $\mathscr{S}$ be the set of all countable subfields of $\mathbb{C}$. Clearly, $\mathscr{S}$ is a partially ordered set under inclusion, and if $K_1\subseteq K_2 \subseteq \cdots$ is an ascending ...
- 5,759
30
votes
11
answers
6k
views
Physics and Church–Turing Thesis
Is there constructed some set of physical laws from which we can logically obtain that any function that can be implemented in some device is Turing computable?
EDIT
I believe that if we restrict ...
- 1,318
21
votes
6
answers
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 ...
- 1,228
16
votes
1
answer
2k
views
Fulfilling Pythagoras' Dream using Nonstandard Models of Arithmetic and/or Surreal Numbers
Pythagoras and his followers believed that the Universe was made of numbers. Specifically, they thought that if you compared any magnitudes of the same kind, say the lengths of two objects, you would ...
- 4,597
4
votes
1
answer
563
views
"Less than" formula for complete theory of the rationals
Does anyone know the name/author of the model theory paper where it's proven that you can define the $ < $ relation on $ (\mathbb{Q}, +, \cdot, 1, 0) $?
- 433
5
votes
1
answer
293
views
semigroups acting as continuous functions on regular rooted trees
Let $T$ be a regular rooted tree. Make $T$ into a metric space by making each edge isometric to the unit interval. What is known about what semigroups can act as continuous functions on $T$ such ...
- 51
5
votes
2
answers
813
views
What is known about links with a countably-infinite number of tame components?
I want to be clear about my phrasing, but I'm not a topologist, so when I say "knot" or "link" I mean the equivalence class under ambient isotopy of an embedding of the circle into $\mathbb{R}^3$.
...
- 354
5
votes
2
answers
655
views
$C^n$ And Forcing: Reading a Recent Paper By Kunen
While reading a recent paper by Kunen arxiv.org/abs/0912.3733, which deals with PFA and the existence of certain differentiable functions, (defined on all of $\mathbb{R}$) which map certain $\aleph_1$-...
- 1,615
11
votes
1
answer
829
views
Axiom of Choice in a weaker system
Is it known whether or not there is a consistent system of logic where two or all of the axiom of choice, well-ordering principle, and Zorn's lemma have no (known) proof of equivalence?
I was ...
- 1,049
16
votes
5
answers
4k
views
Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?
Gödel's original proof of the First Incompleteness theorem relies on Gödel numbering.
Now, the use of Gödel numbering relies on the fact that the Fundamental Theorem of Arithmetic is true and thus the ...
- 603
5
votes
4
answers
739
views
Logical equivalences for FTA
I hope this isn't a stupid question...
It's well known that (in the presence of various other axioms), Euclid's Postulate 5 ('parallel axiom') is equivalent to the Pythagorean Theorem. That is, ...
- 367
16
votes
1
answer
561
views
Real algebraic sets bounded away from integer points
A subset $S$ of $\mathbb{R}^n$ is "bounded away from integer points" if for some positive $\epsilon$ every point in $S$ lies at a distance of at least $\epsilon$ from $\mathbb{Z}^n$. For example the ...
- 6,199
14
votes
2
answers
3k
views
Maximal ideal and Zorn's lemma
It is known that any nonzero ring A (say commutative with 1) has a maximal ideal. The proof uses Zorn's lemma.
Now I heard some people saying that if we assume A to be noetherian, then we don't need ...
- 1,271
17
votes
3
answers
2k
views
Decidability of tiling R^2
Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane?
I know the ...
- 453
5
votes
1
answer
1k
views
Does BQP^P = BQP ? ... and what proof machinery is available?
Update #3:
Over on TCS StackExchange, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is in essence "Do ...
- 1,389
26
votes
1
answer
2k
views
Nontrivial circular arguments?
There is a famous circular argument for the Prime Number Theorem (PNT). It turns
out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates
that taken together imply ...
- 17.6k
7
votes
2
answers
896
views
Iterated forcing and CH
I need some help with this theorem: if $P_\beta=\langle P_\alpha,\dot{Q}_\alpha:\alpha\leq\beta\rangle$, $\beta<\omega_2$, is a CSI of proper forcings, $P_\alpha\Vdash \lvert \dot{Q}_\alpha\rvert\...
- 71