All Questions
6,026 questions
7
votes
3
answers
2k
views
Decidable but nonrecursive sets
Until recently, I believed that recursive=decidable,
subscribing to this Wikipedia quote:
"In computability theory, a set is decidable, computable, or recursive if there
is an algorithm that ...
- 151k
3
votes
1
answer
1k
views
Proving inequalities over algebraic structures
I've been looking at proof techniques in formal systems like Coq and Agda recently, and encountered the newring tactic described here for proving equalities over ...
- 177
2
votes
3
answers
434
views
Undecidable completion of undecidable theory, and pairs of RCF
Given an undecidable collection of first-order sentences, is there necessarily a complete undecidable theory containing it? A direct attempt to prove it seems to require some control over the ...
- 341
10
votes
4
answers
1k
views
Complete extensions of first order logic (or language)
Lindstrom's theorem states that any extension of first order logic (FOL) more expressible than FOL fails to have either compactness or Lowenheim-Skolem. When I first read Lindstrom's theorem my first ...
- 1,175
6
votes
3
answers
927
views
Fraissé limit of the finite linear orderings
Hodges in his Shorter Model Theory promises to show "in what sense the finite linear orderings 'tend to' the rationals rather than, say, the ordering of the integers" (p. 160). After going through his ...
- 9,720
3
votes
1
answer
394
views
Residual finiteness of groups versus residual finiteness of semigroups
A group $G$ is residually finite if, for any two elements $g$ and $g^\prime$ in $G$, there is a finite group $G^\prime$ and a (group) homomorphism $f: G \rightarrow G^\prime$ such that $f(g)$ doesn't ...
- 155
4
votes
3
answers
3k
views
First-order logic without equality and set theory
Is it possible to build set theory on first-order logic without equality?
For example, how could one show that if $x_0=x_1$ then $\left\{x_0\}=\{x_1\right\}$, where $x_0$ and $x_1$ are two sets? And ...
- 737
7
votes
2
answers
878
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 ...
- 1,175
36
votes
8
answers
2k
views
Does the truth of any statement of real matrix algebra stabilize in sufficiently high dimensions?
This question is related to this recent but currently
unanswered MO
question
of Ricky Demer, where it arose as a comment.
Consider the structure $R^n$ consisting of $n\times n$
matrices over the ...
- 236k
20
votes
12
answers
10k
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 ...
1
vote
2
answers
1k
views
Is the isomorphism class of a fixed cardinality a set?
Is the isomorphism class of a fixed cardinality a set(not a proper class)? Or a fixed ordinality for that matter?
By "isomorphism" I mean just bijection for cardinals and order preserving bijection ...
- 2,857
17
votes
5
answers
2k
views
Is {Ø,{Ø},{Ø,{Ø}}, ... } the only known universe?
In the first pages of SGA4 I read
[...] Cependant le seul univers connu est l'ensemble des symboles du type {Ø,{Ø},{Ø,{Ø}}, ... } etc. (tous les éléments de cet univers ...
- 13.6k
5
votes
1
answer
378
views
Representations of products of groups (and monoids)
I have very little knowledge of representation theory, but the following has come up in my summer undergrad research project (relates to conformal field theory and geometric function theory).
Suppose ...
- 51
7
votes
3
answers
915
views
Decidability of matrix algebra
Take multi-sorted first-order logic with equality, complex scalars, 1xn vectors, nx1 vectors, nxn matrices, addition and multiplication for each pair of sorts they make sense for, and hermitian ...
user5810
4
votes
1
answer
328
views
Subsets of sequences of natural numbers vs. strategies under ZFC
This question is related to a previous question of mine:
Determinacy interchanging the roles of both players
Given any set A of sequences of natural numbers, every strategy (no matter for which ...
- 1,465
3
votes
1
answer
251
views
Image of composite morphisms
I am new to categories and I found in a book that it is possible to construct a category in which the following are true: there exist morphisms $f:A \to B$ and $g:B \to C$, and monomorphisms $\alpha:A'...
- 205
5
votes
2
answers
944
views
Is the subobject functor really a presheaf?
I refer to "Sheaves in Geometry and Logic", by S. MacLane.
Let C be a category. Dealing with a subobject of an object $D \in \text{Ob}_{\mathbf C}$, one defines an equivalence relation between ...
- 13.6k
13
votes
7
answers
2k
views
What happens when we print the digits of a real number?
Here are two well known facts, which put together leave me confused.
First, it's well known that intuitionistic logic is the logic of constructive mathematics. From every intutionistic proof, you ...
- 9,201
2
votes
2
answers
751
views
Confusion about model theory notes
On p.8 of http://www.msri.org/publications/books/Book39/files/marker.pdf, the author writes $\Gamma(\bar{d})$, when $\Gamma$ is, first of all, a set of formulas (not a single one), and it is a formula ...
- 15.4k
4
votes
2
answers
1k
views
Semantics of Higher-Order Logics
I've been trying to get to grips with the various semantics commonly discussed in formal logic. Specifically, the nature and role of interpretations of first and higher-order logics is slightly ...
- 820
10
votes
1
answer
380
views
Extra assumption in Hodges' lemma on the resultant of a first-order formula?
Background
I am working through a particular result in a paper of Cherlin, Shelah, and Shi, and am satisfied that it follows from basic model theory material - but I'm stuck on one point in the ...
- 354
11
votes
6
answers
5k
views
Can we have A={A} ?
Does there exist a set $A$ such that $A=\{A\}$ ?
Edit(Peter LL): Such sets are called Quine atoms.
Naive set theory By Paul Richard Halmos On page three, the same question is asked.
Using the ...
- 2,855
18
votes
3
answers
4k
views
How would calculus be possible in a finitist axiom system?
I am interested in learning a little more about finitism, currently about which I only know a few encyclopedic paragraphs.
I know that during some time, some mathematicians like Kronecker thought ...
- 2,745
5
votes
2
answers
350
views
A question about definability in first order theories based upon classical logic
Let T be a theory formalized in the classical first order predicate calculus with equality. If P(x) is a formula of T in which one and only one variable of T--here denoted by 'x'--occurs free, and if ...
- 6,215
11
votes
3
answers
2k
views
Use of Conjectures to Prove a Theorem
Name a theorem T that has a proof based upon the truth of a conjecture C, and also has another proof based upon the falsehood of the same conjecture C, but for longtime has no known direct proof that ...
- 113
29
votes
6
answers
38k
views
Reading materials for mathematical logic [closed]
Hi everyone, the summer break is coming and I am thinking of reading something about mathematical logic. Could anyone please give me some reading materials on this subject?
6
votes
2
answers
1k
views
When is a statement provable?
We all know that Gödel showed that there, in a formal system, are true statements that are non-provable (undecidable). In ZFC, there's Kaplansky's Conjecture, the Whitehead problem, etc.
We can also ...
- 1,071
18
votes
5
answers
4k
views
How do proof verifiers work?
I'm currently trying to understand the concepts and theory behind some of the common proof verifiers out there, but am not quite sure on the exact nature and construction of the sort of systems/proof ...
- 820
3
votes
2
answers
571
views
What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?
For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. :
$$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \...
- 786
71
votes
5
answers
9k
views
Does anyone know a polynomial whose lack of roots can't be proved?
In Ebbinghaus-Flum-Thomas's Introduction to Mathematical Logic, the following assertion is made:
If ZFC is consistent, then one can obtain a polynomial $P(x_1, ..., x_n)$ which has no roots in the ...
- 25.6k
16
votes
2
answers
2k
views
Structure theorems for Turing-decidable languages?
Languages decidable by weak models of computation often have certain necessary characteristics, e.g. the pumping lemma for regular languages or the pumping lemma for context-free languages. Such ...
- 23k
29
votes
8
answers
4k
views
When is something too big to be a set?
Hello,
recently, I've been reading some algebra and sometimes I stumble up on the concept of something "being too big" to be a set. An example, is given in (http://www.dpmms.cam.ac.uk/~wtg10/tensors3....
- 1,071
27
votes
4
answers
10k
views
Finite axiom of choice: how do you prove it from just ZF?
The axiom of choice asserts the existence of a choice function for any family of sets F. Suppose, however, that F is finite, or even that F just has one set. Then how do we prove the existence of a ...
- 287
2
votes
2
answers
1k
views
Is an arbitrary product of sets a set?
$(A_{\alpha})_{\alpha\in B}$ a family of sets indexed by a set $B$. Is $\Pi _ {\alpha\in B} \ A_{\alpha}$ a set? I can see that it is a set if $A_{\alpha}=A \ \ \forall\alpha$ because in that case the ...
- 2,857
4
votes
2
answers
883
views
Group & modules of arbitrary cardinality [closed]
How do I see that there is a group of an arbitrary cardinality? Is this also true for abelian groups? Also, given a commutative ring $R\neq 0$ how do I see that there is an $R$-module of arbitrary ...
- 2,857
4
votes
0
answers
306
views
To what extent MSO = WS1S, when adding relations?
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...
- 786
13
votes
3
answers
4k
views
Most general formulation of Gödel's incompleteness theorems
Modern statements of Gödel's incompleteness theorems are usually in terms of first-order predicate logic. However, I've often read the claim that they extend to arbitrary formal systems that can prove ...
4
votes
1
answer
972
views
Can one really construct an "ordinal table"?
Many books describe how one can construct "by hand" a table of ordinals $1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega +2,\ \ldots,\ \omega\cdot 2,\ \omega\cdot 2 +1,\ \ldots,\ \omega^{2},\ \ldots,\ \...
- 2,857
4
votes
1
answer
405
views
Vocabulary on monoid periodicity
I'm learning about periodic languages, and I'm confused over the vocabulary used to describe the periodicity of (syntactic) monoids.
If I understand correctly, a monoid M is periodic if :
$$(\forall ...
- 786
1
vote
2
answers
692
views
Ambiguity in ordered tuples
I hope this question is not too elementary for math overflow… My knowledge on set theory is very sketchy so it will seem very simple to a working mathematician
It’s a subtle thing I only realized ...
- 161
8
votes
4
answers
2k
views
Infinite games: are they well defined?
It is just my curiosity about this question where we have an infinite game and (according to the answers) winning strategies for both players. I am familiar with terminating games only, and I am ...
14
votes
3
answers
2k
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$ ( $...
- 5,502
17
votes
3
answers
3k
views
What is the history of the Y-combinator?
Inspired by the comments to this question, I wonder if someone can explain the history of the fixed point combinator (often called the Y combinator) in lambda calculus.
Where did it first appear? ...
- 8,803
61
votes
5
answers
12k
views
Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?
1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence?
More formally,
2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA?
Update (July 2010):
So we have two ...
- 5,502
114
votes
2
answers
12k
views
How would you solve this tantalizing Halmos problem?
$1-ab$ invertible $\implies$ $1-ba$ invertible has a slick power series "proof" as below, where Halmos asks for an explanation of why this tantalizing derivation succeeds. Do you know one?
Geometric ...
- 4,736
-1
votes
3
answers
845
views
Do all uncountable sets contain elements with infinite Kolmogorov complexity?
Otherwise, if all the elements in a set can be represented by a at most n symbols (finite Kolmogorov complexity), I could count them by creating a n dimensional pairing function. Or atleast, that is ...
16
votes
1
answer
2k
views
Does ZF prove that all PIDs are UFDs?
Main Question:
Does ZF (no axiom of choice) prove that every Principal Ideal Domain is a Unique Factorization Domain?
The proofs I've seen all use dependent choice.
Minor Questions:
Does ZF + ...
user5810
19
votes
6
answers
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 ...
- 305
4
votes
0
answers
1k
views
Associative binary operations on natural numbers
Which are all the associative binary operations on natural numbers ?
Certain results in this regard can be found in arxiv:math/0508215.
It appears that such associative operations cannot grow too fast....
0
votes
1
answer
642
views
Bicartesian closed categories and Heyting algebras
In Lambek and Scott's "Introduction to higher order categorical logic" (1988), they state that every Heyting Algebra can be understood as a bicartesian closed category.
On the other hand, fixing a ...
