All Questions
6,026 questions
4
votes
2
answers
2k
views
Independence of PA implies independence of PA union all true $\Pi_1$ statements
Prove that if a statement is independent of Peano Arithmetic (PA), then it's also independent of PA$_1$, where PA$_1$ is the union of the set of axioms in PA and the set of all true $\Pi_1$ statements....
- 551
7
votes
2
answers
2k
views
A question about fields of real numbers
Assume that the continuum hypothesis holds. If $F$ is an uncountable field of real numbers, does $F$ always contain a proper uncountable subfield? Are there many specific uncountable fields of real
...
- 6,215
5
votes
4
answers
1k
views
Proof of Gödel incompleteness
in Jech's paper:
On Gödel's Second Incompleteness Theorem
http://www.math.psu.edu/jech/preprints/goedel.pdf
He proves:
Theorem if ZF proves there is a model of ZF, then ZF proves 0=1.
In the ...
- 165
15
votes
3
answers
1k
views
Reasons for success in automated theorem proving
It seems to me (at least according to books and papers on the subject I read) that the field of automated theorem proving is some sort of art or experimental empirical engineering of combining various ...
- 1,175
8
votes
6
answers
2k
views
Stone Spaces, Locales, and Topoi for the (relative) beginner
I am currently reading Vickers' text "topology via logic" and Peter Johnstone's "stone spaces", and I understand the material in both of these texts to pertain directly to constructions in elementary ...
- 1,539
13
votes
7
answers
928
views
Replacing logician-constructive with combinatorist-constructive?
Logicians interpret the word "constructive" in a very well-defined way: they take it to mean, more or less, "computability". Taking constructivity seriously and working in a world where everything ...
- 9,201
9
votes
4
answers
3k
views
Incompleteness and nonstandard models of arithmetic
The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.
Reading Peter Smith's "Gödel Without (Too Many) Tears",...
- 1,465
2
votes
1
answer
853
views
"standard system" of a nonstandard model of PA, interpreted in ZFCfin?
ZFCfin (ZFC without the axiom of infinity, plus its negation) is biinterpretable with Peano Arithmetic.
Each countable model of PA has what is known as its "standard system": the collection of sets ...
- 3,267
2
votes
1
answer
183
views
Are these separation logic statements valid?
I have to say whether or not the following two separation logic statements are valid:
$ x \mapsto 3 * y \mapsto 7 \Longrightarrow x \mapsto 3 * true $
$ true * x \mapsto 3 \Longrightarrow x \mapsto 3 ...
- 123
11
votes
2
answers
504
views
Uniform solutions to Post's problem for axiomatizable theories
The Second Incompleteness Theorem says that if $T$ is a consistent (computably) axiomatizable theory which extends IΣ1, then $\mathrm{Con}(T)$ is not provable from $T$. By analogy with ...
- 44.4k
8
votes
1
answer
2k
views
models of PA which are isomorphic but not elementarily equivalent?
On page 164 of his book Models of Peano Arithmetic, Kaye states Friedman's Theorem:
Let $M{\vDash}PA$ be nonstandard and countable, let $a\in M$ and let $n\in {\mathbb N}$. Then there is a proper ...
- 3,267
13
votes
4
answers
3k
views
{transcendental numbers} \ {computable transcendental numbers}
I know Chaitin's constant Ω is not computable (and therefore transcendental). Are there other specific, known noncomputable numbers? I am trying to understand what distinguishes a computable ...
- 151k
2
votes
2
answers
980
views
What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic
Let T be a true theory of arithmetic to which the incompleteness theorems apply. Consider two sentences in the language of T to be equivalent if they are provably equivalent over T. How many ...
- 995
22
votes
4
answers
3k
views
Impredicativity
I hope this question is not so elementary that it'll get me banned...
In mathematics we see a lot of impredicativity. Example of definitions involving impredicativity include: subgroup/ideal ...
- 231
12
votes
6
answers
2k
views
Uses of bisimulation outside of computer science.
Bisimulation is one of the most important ideas of theoretical computer science. I was wondering whether bisimilarity is used/known outside of computer science/modal logic? I am aware that it ...
- 1,882
22
votes
8
answers
3k
views
Connections between ultrafilters in topology and logic
I have a some-what vague question. It seems to me that there are two main ways in which ultrafilters (on a set) can be used. One is in topology. The notion of an ultrafilter converging to a point is ...
- 15.5k
41
votes
3
answers
2k
views
What is the minimal size of a partial order that is universal for all partial orders of size n?
A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds
order-preservingly into $\mathbb{B}$.
For example, every partial order
$\langle\...
- 236k
7
votes
4
answers
1k
views
Torsors for monoids
Torsors are defined as a special kind of group action. I am wondering whether the analogous notion exists for monoid actions. Some references would be helpful.
In general I'm interesting in the ...
- 1,882
15
votes
2
answers
748
views
Effectively closed computable functions
I've recently been interested in the following type of functions. A total computable function f:N→N is effectively closed if there is a computable function p such that f[N \ We] = N \ Wp(e), ...
- 44.4k
1
vote
2
answers
1k
views
Can Goodstein's theorem been proven with first order PA + Constructive Omega Rule?
I am trying to understand transfinite induction and Gentzen's theories.
But I was wondering, if there is any connection with the Constructive Omega Rule (COR).
With COR I mean that if you can proof:
...
- 1,659
14
votes
4
answers
6k
views
Au revoir, law of excluded middle?
In what way and with what utility is the law of excluded middle usually disposed of in intuitionistic type theory and its descendants? I am thinking here of topos theory and its ilk, namely synthetic ...
- 1,539
14
votes
1
answer
457
views
References regarding a connection between recursion theory and sheaves
In Manin's A Course in Mathematical Logic for Mathematicians, he defines (p.201) a structure $(\mathcal{E},R)$ given an enumerable set $E \subset (\mathbb{Z}^+)^n$ by:
$\mathcal{E}$ is the set of all ...
user2028
9
votes
2
answers
2k
views
Using the multiverse approach to decide the law of the exluded middle?
Recently, in response to deciding the Continuum Hypothesis $CH$, Hamkins and Gitman have proposed consider a multiverse of set-theoretic universes, some in which $CH$ is true, some in which $\neg CH$ ...
user2529
5
votes
1
answer
473
views
A subset of Baire space Wadge incomparable to a Borel set?
Let $\omega^\omega$ be Baire space. If $A,B\subseteq\omega^\omega$ we say that $A$ is Wadge reducible to $B$ (written $A\leq_w B$) if there is a continuous function $f:\omega^\omega\rightarrow\omega^\...
- 2,701
8
votes
3
answers
5k
views
Cardinality: Why is there no "ℵ½"?
A wikipedia page/paragraph on ℵ₁ states:
"The definition of ℵ₁ implies (in
ZF, Zermelo-Fraenkel set theory
without the axiom of choice) that no
cardinal number is between ℵ₀ and
ℵ₁."
"If the axiom ...
- 207
9
votes
4
answers
2k
views
Order types of positive reals
Suppose one has a set $S$ of positive real numbers, such that the usual numerical ordering on $S$ is a well-ordering. Is it possible for $S$ to have any countable ordinal as its order type, or are the ...
- 18.6k
3
votes
2
answers
373
views
L^α_{β,γ}: do we need both α and β for model theory?
The notation ${\mathcal L}^\alpha_{\beta,\gamma}$ refers to the set of sentences of predicate calculus with less than $\alpha$ variables, conjunctions of size less than $\beta$, and quantification ...
- 3,267
2
votes
1
answer
207
views
Bounded-variable logic: "fewer than $\alpha$ variables" equivalent to "every subformula has fewer than $\alpha$ free variables"?
I believe that "fewer than $\alpha$ variables" is equivalent to "every subformula has fewer than $\alpha$ free variables." The left-to-right implication is straightforward, and from right to left one ...
- 3,267
9
votes
3
answers
2k
views
What is the reverse mathematics of first-order logic and propositional logic?
Suppose one tries to formalize first-order logic. How much "strength" is required to do this?
Strength can mean in various senses:
The fragment of ZFC needed to codify first-order logic.
Which ...
user2529
21
votes
2
answers
3k
views
Integer matrices with no integer eigenvalues
Let $$A = \begin{pmatrix} 3&1 \\ 0&1 \end{pmatrix}$$ and $$B = \begin{pmatrix} 1&0\\ 1&2 \end{pmatrix}$$ I want to show that the only elements of the semigroup generated by $A$ and $B$...
- 1,045
5
votes
0
answers
350
views
Chain/Hierarchy of Monoids
Let's assume that we have the following collection of structures:
Some space $P$.
Monoids $(M_{i+1},\circ_{i+1})$, and
Actions $\bullet_{i+1}:M_{i+1}\times M_i\to M_i$, for $i\ge 0$
And $\bullet_{0}:...
- 1,882
17
votes
2
answers
1k
views
What do you use categorical glueing/sconing/Freyd covers for?
In the theory of programming languages and structural proof theory, one of the handiest techniques we have available is a method called "logical relations", in which you can prove properties of ...
- 9,201
16
votes
2
answers
1k
views
Ultrafilters arising from Keisler-Shelah ultrapower characterisation of elementary equivalence
In model theory, two structures $\mathfrak{A}, \mathfrak{B}$ of identical signature $\Sigma$ are said to be elementarily equivalent ($\mathfrak{A} \equiv \mathfrak{B}$) if they satisfy exactly the ...
6
votes
1
answer
922
views
Correspondence between functions on a set and "states" on its power set
Let $L$ be the poset (ordered by set inclusion) that is the power set of some set $X$.
A state is a function $s:L \rightarrow [0,1]$ satisfying
i) for {$p_1,p_2,...$}, $p_i \in L$ a
pairwise ...
- 207
14
votes
15
answers
28k
views
What does it mean for a mathematical statement to be true?
As I understand it, mathematics is concerned with correct deductions using postulates and rules of inference. From what I have seen, statements are called true if they are correct deductions and false ...
3
votes
3
answers
484
views
Ultrafilters containing the image of a filter
Suppose $f:X \to Y$ is a map of sets and $F$ a filter on $X$ such that its image filter is contained in an ultrafilter $G$ on $Y$. Can I find an ultrafilter $H$ on $X$ whose image is $G$?
If this ...
- 15.5k
169
votes
1
answer
17k
views
Ultrafilters and automorphisms of the complex field
It is well-known that it is consistent with $ZF$ that the only automorphisms of the complex field $\mathbb{C}$ are the identity map and complex conjugation. For example, we have that $\vert\...
- 8,298
4
votes
5
answers
12k
views
What is the difference between the biconditional iff. and equality = ?
Hello,
I've been used to writing logical transformations using equality, but the other day it struck me that perhaps I should be using the biconditional $\iff$?
So my question is:
What is the ...
143
votes
12
answers
30k
views
Solutions to the Continuum Hypothesis
Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? ; Completion of ZFC ; Complete resolutions of GCH How far wrong could the Continuum Hypothesis be? When was ...
- 24.7k
10
votes
2
answers
1k
views
A question about open induction
An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
- 6,199
13
votes
3
answers
1k
views
Reducing ACA₀ proof to First Order PA
According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA.
http://en.wikipedia.org/wiki/Reverse_Mathematics
First of all I have a few questions about the proof:
a - What ...
- 1,659
31
votes
4
answers
4k
views
Is "all categorical reasoning formally contradictory"?
In the December 2009 issue of the newsletter of the European Mathematical Society there is a very interesting interview with Pierre Cartier. In page 33, to the question
What was the ontological ...
- 33.3k
1
vote
0
answers
264
views
A question about set theory and Frege logic
Does there exist a very weak axiomatic theory of arithmetic-weaker than (but possibly a sub-theory of)
Robinson's theory Q-which can be interpreted in the first order fragment of Frege logic? If so, ...
- 6,215
14
votes
1
answer
502
views
A decision problem concerning polynomial rings
Let $f_1,f_2, \ldots ,f_n$ be polynomials in any number of variables with algebraic coefficients. Is there algorithm to determine whether the ring $\mathbb{Z}[f_1,f_2,\ldots ,f_n]$ contains a non-...
- 6,199
5
votes
1
answer
364
views
Conservation of Hyperarithmetic Sentences over AC and CH.
I know that arithmetic sentences are conserved under the addition of the axiom of choice and the continuum hypothesis to ZF (i.e. ($ZF+AC \vdash \phi$ iff $ZF \vdash \phi$) and ($ZF+CH \vdash \phi$ ...
- 1,439
28
votes
4
answers
7k
views
Are $\mathbb{C}$ and $\overline{\mathbb{Q}}_p$ isomorphic?
There is a famous passage on the third page of Deligne's second paper on the Weil conjectures where he expresses his dislike of the axiom of choice, as manifested in the isomorphism between $\mathbb{C}...
2
votes
1
answer
647
views
Reference: Countable Models of (Non-)Euclidean Geometry
Has there been a survey written on the model theory of first-order (non-)Euclidean geometry in the spirit of Hilbert and Tarski? I'm especially interested in two aspects of the model theory:
...
user2529
47
votes
5
answers
10k
views
Set theory and Model Theory
This question probably doesn't make any sense, but I don't see why, so I ask it here hoping someone will illuminate the matter:
There is this whole area of study in Set Theory about the consistency, ...
- 1,219
7
votes
4
answers
1k
views
What is the intuitive meaning of star and box in a pure type system?
The systems of the λ-cube have the axiom $\star:\square$.
I've listed a few meanings that the Curry-Howard isomorphism gives to $t : T$ below. What are the intuitive meanings of $\star$ and $\...
- 303
10
votes
2
answers
2k
views
The egg and the chicken
After posting this question (in particular after Carl's and Peter's answers) I have realized that the answer seems to depend on a basic problem in foundations.
Most mathematicians accept as given the ...
- 14.7k