All Questions
6,026 questions
0
votes
1
answer
2k
views
Dual of Zorn's Lemma? [closed]
It seems to me that the dual of Zorn's Lemma should be true: if $S$ is a non-empty partially ordered set and every chain of $S$ has a lower bound in $S$, then $S$ has at least one minimal element.
...
- 1
7
votes
2
answers
1k
views
A question about iterated forcing
I'm trying to get a better grasp of iterated forcing, and I ran across the following problem:
0) Let $P_\alpha$ be posets in a c.t.m. $M$, $\alpha<\beta$, and for each $\alpha$ let $G_\alpha$ be $...
- 20.5k
11
votes
0
answers
305
views
What are the logical morphisms from a topos E to Set?
If $E$ is a topos, is there a nice way to characterize the category of logical morphisms $E\to Set$? Is it complete and/or cocomplete?
The topos $Set$ geometrically represents a point; what does it ...
- 8,659
27
votes
4
answers
7k
views
Did Pogorzelski claim to have a proof of Goldbach's Conjecture?
In 1977, Henry Pogorzelski published what some believed was a claimed proof of Goldbach's Conjecture in Crelle's Journal (292, 1977, 1-12). His argument has not been accepted as a proof of Goldbach's ...
5
votes
1
answer
427
views
Computable rings similar to Z
(This is related to my question at Computable nonstandard models for weak systems of arithemtic )
Is there a nontrivial computable discrete ordered ring with Euclidean division that is not isomorphic ...
user5810
35
votes
8
answers
4k
views
Interpretation of the Second Incompleteness Theorem
For simplicity, let me pick a particular instance of Gödel's Second Incompleteness
Theorem:
ZFC (Zermelo-Fraenkel Set Theory plus the Axiom of Choice, the usual foundation of mathematics) does not ...
- 16.2k
18
votes
3
answers
1k
views
Computable nonstandard models for weak systems of arithmetic
By Tennenbaum's theorem, PA itself does not have any computable nonstandard models. The integer polynomials which are 0 or have a positive leading coefficient form a computable nonstandard model of ...
user5810
15
votes
5
answers
1k
views
Monoids with infinite products
Say a monoid $M$ has infinite products if, for any (possibly infinite) sequence $(m_1,m_2,\ldots)$ of elements of $M$, there exists an element $m_1m_2\cdots\in M$, satisfying some good properties. ...
- 8,659
21
votes
4
answers
2k
views
Is every probability space a factor space of the Haar Measure on some group?
Let P be an arbitrary probability space.
I would like to find a compact topological group $G$ so that the Haar probability measure on $G$ admits a measurable map to the probability space $P$.
By a ...
- 5,898
14
votes
6
answers
28k
views
Induction vs. Strong Induction
Is there ever a practical difference between the notions induction and strong induction?
Edit: More to the point, does anything change if we take strong induction rather than induction in the Peano ...
14
votes
3
answers
2k
views
Which recursively-defined predicates can be expressed in Presburger Arithmetic?
In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...
6
votes
2
answers
655
views
Mostowski collapses and universal extensional relational classes
In the following, by a relational class I mean a pair$^1$ $(A,R)$, where $A$ is a class and $R \subseteq V \times V$ is a class relation, such that $R$ is well-founded and set-like on $A$ ($R$ is not ...
- 63.1k
17
votes
3
answers
3k
views
Gödel's Incompleteness Theorem and the complexity of arithmetic
In How complicated can structures be? Jouko Väänänen says:
The guiding result of mathematical logic is the Incompleteness Theorem of Gödel,
which says that the logical structure of number theory ...
- 9,720
4
votes
4
answers
444
views
Lower bounds on the degrees of representatives of $u^n$ as $n \to \infty$
Let $k$ be an algebraically closed field and $A$ a finitely generated $k$-algebra, together with a specified surjective morphism $\phi \colon k[x_1, \dotsc, x_n] \to A$. For $f \in A$, define $\...
- 7,338
4
votes
3
answers
682
views
What is the proper name for "compact closed" multiplicative intuitionistic linear logic?
Multiplicative intuitionistic linear logic (MILL) has only multiplicative conjunction $\otimes$ and linear implication $\multimap$ as connectives. It has models in symmetric monoidal closed ...
- 1,532
19
votes
2
answers
1k
views
Which graphs are elementarily equivalent to their own disjoint sums?
In Stefan Geschke's recent
question,
one of the solutions observed that the graph consisting of
a single infinite beaded chain, a $\mathbb{Z}$-chain where
each integer is connected to its nearest ...
- 236k
25
votes
2
answers
3k
views
Is there a known natural model of Peano Arithmetic where Goodstein's theorem fails?
(I've previously asked this question on the sister site here, but got no responses).
Goodstein's Theorem is the statement that every Goodstein sequence eventually hits 0. It turns out that this ...
- 6,546
78
votes
12
answers
12k
views
Why aren't representations of monoids studied so much?
It seems to me like every book on representation theory leaps into groups right away, even though the underlying ideas, such as representations, convolution algebras, etc. don't really make explicit ...
- 2,392
0
votes
1
answer
238
views
Models for the given FOL statement
Consider the following FOL sentence:
$\phi = \exists x \forall y \exists z ((x=y) \lor (P(x,y,z) \land \lnot P(y,x,z) ) $
It can be proven that for any natural number n > 0 there exits a model of ...
2
votes
1
answer
310
views
Graph properties and infinite FOL sentences
This question is related to this Question.
Above questions revealed that even though FOL is not expressive enough to describe properties such as Connectivity, Bipartite etc. It is possible to ...
4
votes
2
answers
544
views
Membership problem in monoids
What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ ...
- 41
39
votes
6
answers
7k
views
Why can't proofs have infinitely many steps?
I recently saw the proof of the finite axiom of choice from the ZF axioms. The basic idea of the proof is as follows (I'll cover the case where we're choosing from three sets, but the general idea is ...
- 15.4k
14
votes
3
answers
4k
views
Is non-connectedness of graphs first order axiomatizable?
A recent
question
asked for graph properties that are first order axiomatizable but not finitely axiomatizable.
Connectedness was mentioned in the context. Connectedness can be axiomatized in ...
- 16.2k
2
votes
2
answers
300
views
what conditions can one place on a finitely generated periodic semigroup that will ensure the semigroup is finite?
I am not familiar with much semigroup theory, but this question came up in my research and I've been unable to find much on it.
- 549
2
votes
3
answers
994
views
Predicative definition
Hi, I met several times the expressions "predicative definition" and "unpredicative definiton" in texts about logic. What these expressions do mean ? I precise I'm a french student, thanks for your ...
user2664
3
votes
2
answers
2k
views
Graph properties and FOL
If a certain property of graphs cant not be expressed by a first order logic sentence $\phi$ over $\Sigma$ then can we say with confidence that such as property can not be expressed even by a an ...
68
votes
4
answers
12k
views
Nelson's program to show inconsistency of ZF
At the end of the paper Division by three by Peter G. Doyle and John H. Conway, the authors say:
Not that we believe there really are any such things as infinite sets, or that the Zermelo-Fraenkel ...
- 25.5k
22
votes
3
answers
2k
views
Algebraization of second-order logic
Is there an algebraization of second-order logic, analogous to Boolean algebras for propositional logic and cylindric and polyadic algebras for first-order logic?
- 445
2
votes
3
answers
975
views
Finitely generated monoids are finitely presented?
I saw in the answer of this post that any finitely generated monoids are finitely presented in the sense that there is a coequalizer diagram $P_1\rightrightarrows P_0\rightarrow M$ with $P_1$ and $P_0$...
- 5,052
20
votes
4
answers
3k
views
How constructive is Doyle-Conway's 'Division by three'?
In the (whimsically written) article Division by three, Doyle and Conway describe a proof, (apparently) not using Choice, that an isomorphism $A \times 3 \simeq B\times 3$ of sets (where $3$ is a ...
- 35.5k
68
votes
9
answers
8k
views
Is all ordinary mathematics contained in high school mathematics?
By high school mathematics I mean Elementary Function Arithmetic (EFA), where one is allowed +, ×, xy, and a weak form of induction for formulas with bounded quantifiers. This is much weaker than ...
- 20.7k
7
votes
1
answer
636
views
Model theory stressing order type of universe.
In Appendix B to their Model Theory, Chang and Keisler list some problems and conjectures that, at the time of publication, were unsolved. A few of them take imperative form, for instance:
"Develop a ...
- 1,081
11
votes
2
answers
981
views
Elementary equivalence of ordinals
What is the smallest ordinal alpha which is elementarily equivalent to some smaller ordinal beta with the signature (<)?
What is the corresponding ordinal beta?
What if we instead require that ...
user5810
15
votes
3
answers
2k
views
Construction of a proper uncountable subgroup of $\mathbb{R}$ without Choice.
It is straightforward to construct proper uncountable subgroups of $\mathbb{R}$. One can construst a basis for $\mathbb{R}$ over $\mathbb{Q}$, and then there are many possibilities (just consider the ...
- 2,441
3
votes
3
answers
955
views
Models within a model of set theory
Assume (M,∊M) is a model of ZF. Assume also that (n,∊n) ∊ M is a model in the sense of M and (N,∊N) is a model in the real world with the property that for all sentences σ...
- 367
37
votes
1
answer
3k
views
Community experiences writing Lamport's structured proofs
About two years ago, I came across this paper by Lamport
http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-how-to-write.pdf
on writing proofs hierarchically. It changed how I wrote ...
14
votes
4
answers
1k
views
How fast can the base-bumping function in Goodstein's theorem grow?
In the usual presentation of Goodstein's theorem, the base is bumped up by the "add 1" function. Does the theorem still hold when we replace this function by a fast-growing one (e.g. Ackermann or busy ...
- 2,437
2
votes
2
answers
2k
views
post correspondence problem
I have read a couple of proofs for the undecidability of the post correspondence problem, but neither reference gave a concrete example of two lists of words over a fixed alphabet such that the ...
- 549
1
vote
1
answer
274
views
Natural number properties as uninterpreted functions in first order logic
Can we express the following property of natural numbers as FOL. The property given below is only indicative, I am more interested in knowing how the concepts such as "infinitely many X exists for so ...
2
votes
4
answers
1k
views
Can transfinite induction be defined as axiom scheme in FOL on bin-tree structures?
Transfinite induction requires a second order induction hypothesis. So, that can not be defined as axiom scheme in FOL.
However, if I look to Goodstein's theorem en the Hydra games, then they have to ...
- 1,659
7
votes
1
answer
2k
views
Ackermann function in the Primitive recursive arithmetic
Hello.
I study primitive recursive arithmetic and have the following questions.
1) Is it possible to express in the PRA that Ackermann function is total?
2) If yes, is such expression decidable in ...
- 1,318
1
vote
1
answer
630
views
Exponent function as uninterpreted function in first order logic
I want to express the following sentence in first order logic.
There are naturals numbers that can not be expressed as one natural number raised to the power of another natural number other than one....
5
votes
2
answers
2k
views
Horn clauses and satisfiability
It is well known that satisfiability of Horn formulae can be checked in polynomial time using unit propagation.
But suppose we relax the condition for horn clauses from at most one un-negated ...
20
votes
2
answers
4k
views
Logically independent but true sentences
My question is of a logical nature and concerns what I perceive to be two different types of mathematical independence.
Suppose we have a (sufficiently strong) axiomatic theory $T$. Gödel's ...
- 1,035
45
votes
8
answers
10k
views
What is Realistic Mathematics?
This post is partially about opinions and partially about more precise mathematical questions. Most of this post is not as formal as a precise mathematical question. However, I hope that most readers ...
- 25.5k
4
votes
2
answers
226
views
Modal models as reduced products?
In model theory for standard first-order logic, one constructs a single model, a reduced product, from a collection of first-order models, together with an index set and a filter on the index set.
In ...
- 327
9
votes
2
answers
559
views
Which classes are sets?
From Smullyan and Fitting's Set Theory and the Continuum Problem:
Which classes are sets? Rather than
attempt an absolute answer to this
(which some authors have done with
dubious success), ...
- 2,615
12
votes
2
answers
2k
views
Proving Independence of Axioms by Exhibiting Models Which Don't Satisfy Our Intuition
I recently saw the proof of the independence of ZF (with allowance for multiple empty sets) and AC. The proof constructed the model based on a set theory generated by infinitely many empty sets and ...
- 15.4k
5
votes
0
answers
336
views
Defining a topology by means of closed subsets in a topos
In the following we fix a topos. I'll speak of sets instead of objects and of subsets instead of subobjects.
Let $X$ be a set and assume $F$ is a set of subsets of $X$ that contains $\emptyset, X$, ...
- 63.1k
77
votes
8
answers
12k
views
Succinctly naming big numbers: ZFC versus Busy-Beaver
Years ago, I wrote an essay called Who Can Name the Bigger Number?, which posed the following challenge:
You have fifteen seconds. Using standard math notation, English words, or both, name a single ...
- 9,833