All Questions
6,026 questions
8
votes
2
answers
354
views
Where's the notion of interpretation (model) originally introduced?
Where's the notion of interpretation (model) originally introduced?
I find it used in Skolem's paper "Logico-combinatorial investigations in the satisfiability or provability of mathematical ...
- 153
6
votes
2
answers
1k
views
Does the beth function have fixed points of arbitrarily large cofinality?
Background
The beth function is defined recursively by: $\beth_0 = \aleph_0$, $\beth_{\alpha + 1} = 2^{\beth_\alpha}$, and $\beth_\lambda = \bigcup_{\alpha < \lambda} \beth_\alpha$. Since the beth ...
- 1,793
-2
votes
1
answer
271
views
how to weigh the conditions given in a proposition
As we can see,there are some conditions given in a proposition.
If there are 2 propositions having approximate conclusions.Usually，we can name one propositions gives stronger conditions than the ...
- 57
17
votes
1
answer
875
views
Which finitely presented groups can be distinguished by decidable properties?
This question continues the line of inquiry
of these
three
questions.
Question. Which finitely presented groups can be
distinguished by decidable properties?
To be precise, let us say that φ is ...
- 236k
2
votes
2
answers
183
views
Algebraic structures at hypernatural parameters
Let's start with some family of algebraic structures of the same type indexed by the natural numbers, say the symmetric group $S_n$. Suppose that the axioms of this algebraic structure (in this case, ...
- 25.6k
10
votes
2
answers
2k
views
Scott on the consistency of the lambda calculus
I have twice heard it attributed to Dana Scott that he said something to the effect that the consistency of the lambda-calculus was an accident.
Does anyone have a reasonable-sounding source for this?...
- 2,283
28
votes
3
answers
3k
views
Does $\operatorname{Con}\sf(ZF)$ imply $\operatorname{Con}\sf(ZF + \operatorname{Aut}{\bf C = Z/\mathrm 2Z})$?
How many field automorphisms does $\mathbf{C}$ have? If you assume the axiom of choice, there are tons of them -- $2^{2^{\aleph_0}}$, I believe. And what if you don't -- how essential is the axiom ...
- 4,487
19
votes
4
answers
1k
views
Does every decidable question about finitely presented groups amount to a question about abelian groups?
This question is about an issue left unresolved by Chad
Groft's excellent
question and
John Stillwell's excellent
answer of
it. Since I find the possibility of an affirmative answer
so tantalizing, I ...
- 236k
1
vote
2
answers
2k
views
What does the disjunction elimination rule say?
I read about two different versions of the disjunction elimination rule.
The first version (http://www.fecundity.com/logic/) says that:
if $\Sigma\vdash\phi_0\lor\phi_1$ and $\Sigma\vdash\lnot\phi_0$...
- 737
11
votes
4
answers
2k
views
Can dependent sums be encoded as dependent products?
Please forgive any unorthodox notation or obvious errors here... I'm trying to get an intuition for dependently typed languages, so I'm starting out by seeing which analogies I can take from the ...
- 211
6
votes
3
answers
1k
views
Proof formalization
I read some time ago some papers about proof formalization. Typically, I began whith this one, from Lamport.
Are there more recent works in this field ?
7
votes
1
answer
2k
views
Least ordinal not in a countable transitive model of ZFC
Frequently it is useful do deal with countable transitive models M of ZFC, for example in forcing constructions.
The notion of being an ordinal is absolute for any transitive model, so certainly if ...
- 884
8
votes
3
answers
2k
views
Formalizing "no junk, no confusion"
Goguen has popularized the initial algebra view of semantics via his "no junk, no confusion" slogan. By "no junk", he means that models of a theory presentation should not have unnecessary elements, ...
- 11.8k
7
votes
2
answers
957
views
Can models of set theory contain extra ordinals?
In the paper "Complete topoi representing models of set theory" by Blass and Scedrov, they consider a general notion of Boolean-valued model of set theory, and one of the conditions they impose is ...
- 66.8k
4
votes
1
answer
862
views
Generalized Cox Theorems, valuations on boolean sets, bayesian probabilities and posets
Bayesian probabilities are usually justified by the Cox theorems, that can be written this way:
Under some technical assumptions (continuity, etc, etc...), given a set $P$ of objects $A, B, C, \ldots$...
1
vote
3
answers
3k
views
Is there formal definition of universal quantification?
From wikipedia quantification has meaning:
In logic, quantification is the
binding of a variable ranging over a
domain of discourse
Is there any formal "definition" of universal quantifier for ...
- 1,626
22
votes
6
answers
2k
views
Is any interesting question about a group G decidable from a presentation of G?
We say that a group G is in the class Fq if there is a CW-complex which is a BG (that is, which has fundamental group G and contractible universal cover) and which has finite q-skeleton. Thus F0 ...
- 1,219
26
votes
4
answers
22k
views
Propositional Logic, First-Order Logic, and Higher-Order Logics
I've been reading up a bit on the fundamentals of formal logic, and have accumulated a few questions along the way. I am pretty much a complete beginner to the field, so I would very much appreciate ...
- 820
2
votes
3
answers
780
views
Does the axiom of specification prevent writing any proof?
In set theory, the axiom of specification says that $\forall x_0\exists x_1\forall x_2\left(x_2\in x_1\leftrightarrow x_2\in x_0\land\theta\left[x_2\right]\right)$, where $\theta\left[x_2\right]$ is ...
- 737
13
votes
3
answers
4k
views
Non-principal ultrafilters on ω
I thought I had heard or read somewhere that the existence of a non-principal ultrafilter on $\omega$ was equivalent to some common weakening of AC. As I searched around, I read that this is not the ...
- 475
0
votes
4
answers
310
views
Deficiency of necessary conditions
Motivation
Consider the situation: You know that
every $x$ that has property $P$ must have property $Q$. $Q$ is a
rather strong condition but not strong
enough to fulfill $P$. What is ...
- 9,720
-1
votes
1
answer
750
views
Is theory with domain of interpretation in second order objects a First Order Theory?
Thank everybody for answering my previous questions: first, and second.
Here I would like to ask about some important thing which I do not understand clearly.
Is it necessary for theory to have given ...
- 1,626
3
votes
2
answers
989
views
Theory interpreted in non-set domain of discourse may be consistent?
Following the blow. I will try to ask question in order to check if I well understand what was pointed. I decide to ask another question, because mathoverflow is not projected to be good environment ...
- 1,626
12
votes
7
answers
10k
views
Is there any proof assistant based on first-order logic?
I'm looking for a proof assistant in order to write formal proofs about basic facts of set theory, such as:
$a\subseteq a$
$(a,b)=(c,d)\leftrightarrow a=c\land b=d$
Natural deduction for first-order ...
- 737
10
votes
3
answers
2k
views
Is there a version of the Archimedean property which does not presuppose the Naturals?
All the statements of the Archimedean property with which I am acquainted fundamentally uses ℕ -- more than as a totally ordered semi-group, really being the 'standard model' of the naturals. ...
- 11.8k
6
votes
1
answer
930
views
"$\kappa$ strongly inaccessible" = "every function $f:V_\kappa\to V_\kappa$ can be self-applied"?
Strongly inaccessible cardinals are usually introduced either as (a) cardinalities of models of ZFC or (b) cardinals which are not the power set of a smaller cardinal nor the supremum of a set with ...
- 3,267
9
votes
1
answer
911
views
An ubiquitous pattern of questions
There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):
Can a ...
- 9,720
13
votes
2
answers
713
views
How do you compute the space of lifts of an E-infinity map?
Let X, Y and B be $E_\infty$ spaces, and let $p: X \rightarrow Y$ and $f: B \rightarrow Y$ be $E_\infty$ maps. We can ask for the space of lifts of f across p, that is the space of $E_\infty$ maps $g:...
- 3,103
0
votes
3
answers
817
views
How do we construct (in a vector space) a chain of countable dimensional subspaces that can only be bounded by an subspace of uncountable dimension?
In more rigorous language:
" V: a vector space having an uncountable base
S: The set of subspaces of V that have countable dimension.
Can we construct explicitly a chain in the poset S (ordered by ...
- 45
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
1
vote
1
answer
190
views
Is the semigroup M(n, Z) finitely presented? If so, where can I find a presentation of it?
I am new to semigroup research, so I apologize if this is an easy question.
- 87
13
votes
4
answers
1k
views
Why is a monoid with closed symmetric monoidal module category commutative?
Given a symmetric monoidal category and a monoid object A in it, one can form the category of modules over this monoid object, i.e. objects are $A \otimes M \rightarrow M$ satisfying the natural ...
- 12.3k
4
votes
6
answers
1k
views
Are there nonequivalent randomnesses?
There are nonequivalent geometries, nonequivalent groups finite and infinite, nonequivalent logics ( fregean and nofregean http://www.formalontology.it/suszkor.htm), even nonequivalent logicians;-)
...
- 1,626
14
votes
6
answers
5k
views
Do you know any good introductory resource on sequent calculus?
I'm looking for a good introductory resource on sequent calculus suitable for someone who has studied natural deduction before. Books and online resources are both OK, as long as each rule of ...
- 737
11
votes
3
answers
2k
views
Is any true sentence in the second-order Peano Axioms provable
Forgive the elementary nature of the question. I understand that the second order Peano Axioms are categorical in the sense that all their models are isomorphic. This equivalence class of models is ...
17
votes
1
answer
1k
views
How are the two natural ways to define “the category of models of a first-order theory $T$” related?
$\DeclareMathOperator\Mod{Mod}\DeclareMathOperator\Elem{Elem}$Background/Motivation: Inspired by an interesting question by Joel, I’ve been wondering about the relationship between two very natural ...
- 3,966
5
votes
3
answers
3k
views
Pigeonhole Principle for infinite case
Suppose $X_n$ are finite sets for any natural integer $n$. let $Y$ be an infinite subset of $\prod_n X_n$. Do there exist $y$ and $y'$ in $Y$ and an infinite subset $S$ of $\mathbb N$ such that $y_n=...
- 51
17
votes
5
answers
5k
views
Bourbaki's epsilon-calculus notation
Bourbaki used a very very strange notation for the epsilon-calculus consisting of $\tau$s and $\blacksquare$. In fact, that box should not be filled in, but for some reason, I can't produce a \Box.
...
- 19.6k
40
votes
7
answers
8k
views
What is the general opinion on the Generalized Continuum Hypothesis?
I'm community wikiing this, since although I don't want it to be a discussion thread, I don't think that there is really a right answer to this.
From what I've seen, model theorists and logicians ...
2
votes
5
answers
2k
views
Decidability of the Axiom of Choice
Everything that I read regarding Set Theory states that the Axiom of Choice is independent and undecidable within the context of Zermelo-Frankel Set Theory. My question is this: Is there any ...
- 153
1
vote
1
answer
365
views
Naturally definable sets of natural numbers (3)
[This shall be the last of a series of questions, see Naturally definable sets of natural numbers (2)]
I cannot explain why I have been so stubborn not to see the most straight-forward definition for ...
- 9,720
2
votes
1
answer
1k
views
monoid ring and some structure within it - how is it called?
I am amateur - mathematics is my hobby, and I find some strange structure working with toy matrices structure so I try to ask some questions regarding it. Let me allow to introduce some structure ...
- 1,626
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 258
-1
votes
1
answer
679
views
Naturally definable sets of natural numbers (2): Can the circle be broken?
(follow-up to: Naturally definable sets of natural numbers)
Every formula $\Psi(x)$ in the first-order language of Peano arithmetic defines a set of natural numbers. Some of these sets are finite, ...
- 9,720
4
votes
2
answers
292
views
Goedelizability and decidability of a property of Peano formulas
Sorry for not knowing the answers to these elementary questions:
Is the property of formulas of the first-order language of Peano arithmetic of "defining a finite set of natural numbers" goedelizable?...
- 9,720
3
votes
2
answers
3k
views
Why are universal introduction and existential elimination valid inference rules?
I'm studying the inference rules of natural deduction for the first-order logic. I cannot understand why universal introduction and existential elimination are valid rules. The first one says that if $...
- 737
1
vote
2
answers
394
views
Relations in matrix semigroups
Suppose that $A_1, \dots, A_k \in M_n(\mathbb{Q})$ and $S$ is the semigroup generated by them. Two questions: are there always a finite set of relations $\{R_i\}$ among the $A_j$ such that $S$ is ...
- 4,636
4
votes
1
answer
795
views
Shortest Key for the Monte Carlo Lock of Smullyan
This question is about a puzzle from the book of Raymond Smullyan: The Lady or the Tiger? The description of the puzzle starts in Chapter 8, p. 103, and here is the important part (copy-pasted from ...
- 18.9k
-1
votes
3
answers
1k
views
Naturally definable sets of natural numbers
(This is a follow-up question from over there: Natural models of graphs.)
(And it has a follow-up question over there: Naturally definable sets of natural numbers (2): Can the circle be broken?)
...
- 9,720
11
votes
6
answers
1k
views
Computing the structure of the group completion of an abelian monoid, how hard can it be?
Cherry Kearton, Bayer-Fluckiger and others have results that say the monoid of isotopy classes of smooth oriented embeddings of $S^n$ in $S^{n+2}$ is not a free commutative monoid provided $n \geq 3$. ...
- 44.4k