All Questions
6,026 questions
18
votes
1
answer
727
views
(Dis)similarity between groups and Lie algebras
There are many questions which sound similar or the same for groups and Lie algebras. Some (very few, actually) of those questions have identical solutions and answers. Some have identical answers but ...
- 2,804
0
votes
3
answers
1k
views
How different category theories relate
Continuing about this my question.
Mac Lane "Categories for the Working Mathematician" and "Abstract and Concrete Categories. The Joy of Cats" use different set theory foundations.
How one to ...
- 765
2
votes
2
answers
1k
views
Downgrading from ZFC with universes to ZFC
Is the following correct?
If something is provable for small sets in ZFC with Axiom of Universes ("For any set x, there exists a universe U such that x∈U.") then it is provable for any sets in ZFC (...
- 765
5
votes
1
answer
362
views
Sequences of projecta in the constructible hierarchy
For $n$ a natural number, $\alpha$ an ordinal, let $\rho(n,\alpha)$ be the $n$-th projectum of $J_\alpha$, where $J$ is the Jensen hierarchy for $L$.
Call a finite sequence $s:=(x_1,\dots,x_m)$ of ...
- 521
0
votes
3
answers
2k
views
Proofs that use Infinite/Finite Priority Injury Method
Can anyone point me to any proofs (pref. interesting ones!) that make good (or bad) use of the Finite or Infinite Priority Injury Argument?
Edit: I would suppose that my question could be put this ...
- 83
0
votes
3
answers
1k
views
Bijection of proper classes
I have two proper classes which intuitively are like bijectively equivalent, i.e. for every element of one of these two classes we can define an expression for the corresponding element of the other ...
- 765
1
vote
1
answer
3k
views
basic measure theory question - measure on the natural numbers [closed]
I am looking for a succinct way to describe a subset of the natural numbers which has ``measure zero" in the following sense: Let X_1 \subset X_2 \subset .... be any strictly nesting sequence of ...
4
votes
2
answers
923
views
Natural numbers of great kolmogorov complexity
Before I ask my question, let me give you a mini-preamble: in 2006, during an animated discussion on feasibility, ultrafinitism, and what else on FOM, I introduced (informally, and to speak the tuth, ...
- 7,853
4
votes
2
answers
608
views
Is there Ramsey Theorem for infinitary tuples?
I'm wondering if there's any sort of Ramsey relation that allows for the tuples to be of arbitrary infinite size $\mu$? This $\mu$ is below some strongly compact cardinal, so I'm not worried about ...
- 168
4
votes
0
answers
512
views
Homogeneous Structures
Let $M$ be a countable structure that is homogeneous, i.e. every isomorphism between finitely generated substructures of $M$ extends to an automorphism of $M$. Let $\phi_M$ be the Scott sentence of $M$...
- 2,882
5
votes
1
answer
821
views
Higher-order preservation theorems?
The Łos-Tarski preservation theorem states that a set of formulas $F$ of first-order language $L$ is preserved under substructures for models of theory $T$ in $L$ precisely when $F$ is equivalent ...
- 2,350
7
votes
1
answer
1k
views
categorifying induction in homotopy type theory
In trying to understand homotopy type theory, I stumbled upon the following silly question, which is likely to be trivial for the experts.
Let $B=\sqcup_{n\in\Bbb N} BS_n$, which I'd like to think of ...
- 5,575
1
vote
2
answers
326
views
Finite T-uples and the axiom of Regularity
Let V be the universe of sets (the class of all sets). Let U(0)=V, U(1)=V*V, the class that is cartesian product of the class V=U(0) with V, and for n>=1, let U(n+1)=U(n)*U(0);
For every natural ...
- 2,655
18
votes
3
answers
1k
views
Are there examples of nonconstructive metaproofs?
This came up in a question on the xkcd forums. Is it possible to have a nonconstructive metaproof, i.e. a proof that there exists a proof in some formal system which does not construct said proof? Are ...
20
votes
3
answers
5k
views
Pi1-sentence independent of ZF, ZF+Con(ZF), ZF+Con(ZF)+Con(ZF+Con(ZF)), etc.?
Let
ZF1 = ZF,
ZFk+1 = ZF + the assumption that ZF1,...,ZFk are consistent,
ZFω = ZF + the assumption that ZFk is consistent for every positive integer k,
... and similarly define ZFα ...
- 9,833
6
votes
3
answers
1k
views
Set theory inside arithmetics via the Ackermann yoga
Among the basic results of logic which, simple as they are, never fail to intrigue me, is Ackermann's interpretation of ZF-Infinity in PA (see for refs this MO question and here for an excellent ...
- 7,853
1
vote
2
answers
471
views
Is anyone aware of a good exposition of the Gauss-Kramer model of Integers?
In the Princeton Companion of Mathematics, the Analytic Number Theory section, the author mentions what he calls Gauss-Kramer model, which is simply modeling the integers on a countable sequence of ...
0
votes
2
answers
441
views
Would intuitionistic refutation method imply permutation of premisses?
Dear All
In the classical refutation method, one searches for a proof of $\Gamma, \lnot A \vdash \bot$ instead of $\Gamma \vdash A$. The method works, i.e. is complete and correct, since it is for ...
Countably Infinite
3
votes
1
answer
340
views
Any subset of Baire space is a union of a boldface $\Delta_2^0$ set and a set with no isolated points. Anybody know how to prove this?
I'm trying to do due diligence and determine whether this is known, trivial, original, etc. I have a proof of:
Theorem: If $S\subseteq \mathbb{N}^{\mathbb{N}}$ then $S=X\cup Y$ for some $X$ which is ...
- 121
7
votes
2
answers
736
views
Sets as Combinatorial Games
Just a few days ago my seemingly eternal and recurrent fascination for Conway's combinatorial game theory (CGT) & surreal numbers had a recrudescence, so I grabbed this excellent survey, and began ...
- 7,853
6
votes
1
answer
286
views
Definitions of definable compactness
We have an o-minimal structure M with the order topology. $X \subseteq M^n$ with the induced topology. The article "Definable compactness and definable subgroups of o-minimal groups" by ...
- 61
21
votes
5
answers
2k
views
Alternative Arithmetics
Although, beyond any doubts, $ZFC$ is by and large the predominantly accepted theory of sets, there have been a few attempt to establish some serious competitors in town.
I just quote two of them (...
- 7,853
-2
votes
1
answer
270
views
Complete proof system
How do I prove that a proof system is complete? I mean what are the guidelines to such proof?
- 1
10
votes
2
answers
566
views
Destroying the P-filter-property
It is known that if a forcing notion is proper, then every P-filter will generate a P-filter in the generic extension (see, e.g., Shelah, Proper and Improper Forcing, VI.5)
On the other hand, if we ...
8
votes
0
answers
2k
views
Why is definable compact equivalent to bounded and closed for sets with o-minimal structures?
We have $M$ an o-minimal structure. $X \in M^n$ with the induced topology.
I'm reading an article which shows that $X \in M^n$ is definable compact is
equivalent to $X$ being bounded and closed.
...
- 81
5
votes
2
answers
754
views
Do all finitely generated nilpotent semigroups have polynomial growth?
The notion of nilpotency passes nicely from groups to semigroups. Define $q_1(x,y)=xy$ and $$q_{i+1}(x,y,z_1,\cdots,z_i)=q_i(x,y,z_1,\cdots,z_{i-1})z_iq_i(y,x,z_1,\cdots,z_{i-1})$$ inductively for all ...
- 1,437
7
votes
1
answer
433
views
Powers of maps on finite sets
Let $X_n$ be a set with $n$ elements. Write $F(X_n,X_n)$ for the set of maps from $X_n$ to itself. It is a monoid under the operation of composition. Let $m$ be a positive integer. How many maps in $...
- 385
4
votes
0
answers
570
views
Is this observation about the Borel Hierarchy trivial?
Hello, consider the following theorem. Is it trivial? Is it interesting? Is it worth including in a paper if I can prove it in 1 line as a corollary?
Theorem: Suppose $n>0$ is a natural. ...
- 121
1
vote
1
answer
494
views
Is forward chaining also a form of focusing?
Dear All
Lets restrict ourselfs to logical theories which consist only of formulas $P_1 \supset \quad ... \quad P_n \supset Q$, i.e. propositional horn clauses expressed with implication. Lets only ...
Countably Infinite
32
votes
11
answers
11k
views
Is PA consistent? do we know it?
1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...
2
votes
1
answer
520
views
A Dedekind (pseudo) finite set
Quoting the wiki:- a set A is Dedekind-infinite if some proper subset B of A is equinumerous to A. Explicitly, this means that there is a bijective function from A onto some proper subset B of A. -.
...
- 7,853
3
votes
2
answers
1k
views
Lindenbaum algebras and models
Sorry for this question out of the blue (especially if its answer should be trivial, obvious, or folklore):
(When and how) can we construct models of a consistent
first order theory $T$ from its
...
- 9,720
6
votes
2
answers
1k
views
What are the models of Peano Arithmetic plus the negation of the corresponding Gödel sentence like?
Since the Godel sentence for PA (G henceforth) is independent of PA, if PA is consistent, so is PA plus not-G. Thus, since PA is a first-order theory, if PA is consistent, PA plus not-G has some ...
- 61
-6
votes
1
answer
779
views
De-Lifting Lemma, does it hold? [closed]
Let $\sigma$ denote an independent simultaneous substitution. Now I wonder if the following holds:
If $\Gamma \vartriangleright (A\ (\sigma\ \tau))\ \rho$ then there are $\psi$, $\phi$ such that $\...
Countably Infinite
2
votes
1
answer
824
views
How establish conversion of cut-free proof into uniform proof?
Dear All
Gentzen (*) claimed that through cut-elimination, he can normalize proofs. It is well known that cut-eliminated proofs might still contain some unnecessary noise. I am trying to show that ...
Countably Infinite
32
votes
0
answers
2k
views
Peano Arithmetic and the Field of Rationals
In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, +,...
- 17.7k
4
votes
2
answers
586
views
Formulaic definitions
In Jech's Set Theory, p. 194, I read - as a comment on the definition of ordinal-definable sets ("A set X is ordinal-definable if there is a formula such that [...]") -:
It is not immediate clear ...
- 9,720
11
votes
0
answers
2k
views
Can any formal system prove its own consistency? [closed]
My curiosity was piqued by this discussion:
Presburger Arithmetic
I'll state this question loosely (rather than formally in terms of first-order logic or another formal framework) but I think it's ...
- 2,895
13
votes
2
answers
2k
views
How quickly did Gödel's Incompleteness Theorem become known and heeded throughout mathematics
Does anyone know how news of Gödel's incompleteness theorem spread? Did it do so little by little, or was it shouted in dramatic headlines throughout mathematical literature? If anyone can point me to ...
- 1,161
11
votes
4
answers
1k
views
Why is alpha-equivalence in untyped $\lambda$-calculus substitutive?
This is something all introductory texts seem to avoid proving, and many even avoid stating.
We consider untyped $\lambda$-terms on some countably infinite alphabet. If $x$ is a variable and $p$ is ...
- 33.8k
4
votes
1
answer
452
views
M.A.D family question
I come up with the following set-theoretic question that has the flavor of Maximal Almost Disjoijnt (M.A.D.) families, although it is a bit different than the usual setting:
Let $\kappa$ be an ...
- 2,882
22
votes
3
answers
3k
views
Half Cantor-Bernstein without choice
I had a discussion with one of my teachers the other day, which boiled to the following question:
Assume ZF. Let $A,B$ be sets such that there exist $f\colon A\to B$ which is injective and $g\colon A\...
- 39.8k
27
votes
2
answers
2k
views
Are any natural examples of Gödel speed-up known?
In 1936 Gödel announced a theorem to the effect that proofs of certain theorems $T_1,T_2,\ldots$ become dramatically shorter when one passes from a formal system, such as Peano arithmetic PA, to a ...
- 12.4k
7
votes
3
answers
3k
views
incompleteness in real analysis
Godel's theorem tells us that any sufficiently powerful consistent formal theory of the integers is incomplete; but what about formal theories of the real numbers? More precisely, what about theories ...
- 19.7k
7
votes
0
answers
2k
views
Is there a chess position equivalent to the Collatz conjecture?
Suppose we have an infinite board with a finite number of chess pieces. The question is whether white can checkmate black (without the after 50 moves it is a draw rule). Can you give an explicit ...
- 19k
4
votes
1
answer
330
views
Defining computability for functionals of partial oracles
I believe a recursive (partial) functional $F:\mathbb{N}^\mathbb{N}\to\mathbb{N}$ is ordinarily defined as one for which the "graph" relation $F(\alpha)=n$ is recursively enumerable, which means it ...
- 5,992
2
votes
1
answer
873
views
Feferman's extensional and intensional applications of the method of arithmetization
At the very beginning of Feferman's Arithmetization of metamathematics in a general setting it can be read:
The method of arithmetization, as developed by Gödel[10], exploits the possibility of ...
- 1,465
5
votes
1
answer
1k
views
Characterization of infinite paths in graphs
First an introduction.
A directed graph we all know what is, and a graph is serial whenever
every vertex has a successor. I do not consider the empty graph. A
pair $(\mathcal{G},s)$ is called a ...
- 126
18
votes
2
answers
774
views
Dual Borel conjecture in Laver's model
A set $X\subseteq 2^\omega$
of reals is of strong measure zero (smz) if $X+M\not=2^\omega$
for every meager set $M$. (This is a theorem of Galvin-Mycielski-Solovay,
but for the question I am going to ...
- 14k
3
votes
1
answer
552
views
Universal Objects in Big Categories
Let $\mathcal{A}$ be a category whose collection of object forms a proper class. Then, to be able to formulate the concept of a terminal object in $\mathcal{A}$, do we have to leave ZFC? In other ...
- 805