All Questions
6,026 questions
14
votes
2
answers
4k
views
Consequences of technically proving anything in Coq (on at least Linux) exploiting a bug? [closed]
Technically, it is possible to prove anything in Coq proof assistant [1] (on at least Linux) due to a programming feature (or bug). This seems tractable when validating large proofs. Human analysis ...
- 25.4k
3
votes
2
answers
2k
views
Prenex normal form vs. quantifier rank
Consider first-order logic with some fixed, relational vocabulary $\tau$. A sentence is a formula in this logic with no free variables.
A sentence is in prenex normal form, if all quantifiers are ...
user10891
6
votes
2
answers
603
views
Are undecidable consequences of Con recursively enumerable?
Let $X\subset\Pi_1^0$ be the set of statements which are
provable in PA$+$Con(PA) but independent of PA.
Is $X$ recursively enumerable?
- 6,891
20
votes
3
answers
4k
views
Cohen reals and strong measure zero sets
A set of reals $X$ is $\textit{strong measure zero}$ if for any sequence of real numbers $ ( \epsilon_n ) _{n \in \omega }$ there is a sequence of open intervals $ ( a_n ) _{n \in \omega }$ which ...
- 540
128
votes
13
answers
24k
views
Checkmate in $\omega$ moves?
Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...
- 5,492
14
votes
1
answer
2k
views
Martin's "Philosophical Issues about the Hierarchy of Sets"
Some months ago (October 2010), in the context of the Workshop on Set Theory and the Philosophy of Mathematics, Professor Donald A. Martin gave a talk entitled "Philosophical issues about the ...
- 1,465
18
votes
3
answers
2k
views
What are "maps" between proper classes?
When defining a functor (between categories), I am usually told that it assigns to each object of the source category an object of the target category. I do not find this very satisfactory since we ...
- 4,902
4
votes
1
answer
713
views
Constructible universe within constructible universe
Let $\langle L_\alpha \rangle$ denote the hierarchy of constructible sets namely
$$L_0 = \emptyset$$
$$L_{\alpha+1} = \text{def}(L_\alpha)$$
$$L_{\gamma} = \bigcup_{\alpha<\gamma}{L_\alpha}$$
for $\...
- 347
5
votes
1
answer
861
views
$\Sigma_1$ elementary substructure
This is a question I was given in the exam: show that if $\lambda, \kappa$ are uncountable cardinals then
$$(H_\lambda,\in) \prec_1 (H_\kappa,\in)$$
where $H_\lambda$ is the class of all sets $x$ such ...
- 347
14
votes
4
answers
1k
views
The disjunction property in Peano Arithmetic?
Let $\phi,\psi\in\Pi_1^0$ be independent of PA.
Is the disjunction $\phi\vee\psi$ independent of PA?
- 6,891
44
votes
3
answers
5k
views
"Simpler" statements equivalent to Con(PA) or Con(ZFC)?
Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
- 9,833
43
votes
9
answers
5k
views
The sets in mathematical logic
It is well known that intuitive set theory (or naive set theory) is characterized by having paradoxes, e.g. Russell's paradox, Cantor's paradox, etc. To avoid these and any other discovered or ...
- 764
8
votes
8
answers
5k
views
probability and math puzzle books/references [closed]
Hi All,
I'd like to solve some math puzzles, especially in the context of probability theory, but I'm open to other areas too. The kind of problems that does not require much knowledge of mathematics, ...
13
votes
3
answers
8k
views
$fgf = f$, $gfg = g$, $fg$ not necessarily identity, what is this called?
A very simple question, I just totally forgot how it was called, and Google is not helping.
There's a pair of functions $f:X\to Y$, $g:Y\to X$.
$fgf = f$, $gfg = g$, but $fg$ and $gf$ don't need to ...
- 241
34
votes
23
answers
29k
views
Textbook recommendations for undergraduate proof-writing class
I am teaching the proof-writing class (for the 3rd time) in the Fall and plan to buck the party line and use a different text than the default Bond and Keane. My parameters are as follows:
Logic, ...
0
votes
2
answers
625
views
A non-associative three-valued logic
There are three elements: x, y, z and a relation C:
x C y, y C z, z C x, x C x, y C y, z C z.
Let us introduce two binary operations with respect to the C: "the leftmost" (L) ...
- 211
2
votes
1
answer
212
views
$2$-variable segment of FO over ordered, finite structures
Let $FO$ be first-order logic and $FO^k$ be $k$-variable segment of $FO$, i.e. $FO^k$ has only $k$ variables.
To my understanding, for every sentence $\varphi\in FO$ there exists a sentence $\psi\in ...
user10891
72
votes
13
answers
19k
views
Logic in mathematics and philosophy
What are the relations between logic as an area of (modern) philosophy and mathematical logic.
The world "modern" refers to 20th century and later, and I am curious mainly about the second ...
- 24.7k
20
votes
3
answers
4k
views
Propositions equivalent to the completeness of the real numbers
Can anyone point me to a reasonably comprehensive article (or book chapter) explaining which basic theorems of calculus are equivalent to the completeness axiom of the reals and which ones aren't?
...
- 19.7k
11
votes
2
answers
3k
views
Are the Millennium Prize Problems all decidable? [closed]
I am an inexperienced logician, so I may be completely missing something major in this question. I also may be misconstruing the idea of decidability. However, I was wondering if all 6 of the ...
1
vote
2
answers
608
views
FOPL and equational logic
Hi,
I am trying to convert First Order Predicate Logic (FOPL) sentences to sentences in Equational Logic (EL). I am using Skolem constants and function to represent FOPL existential quantification in ...
2
votes
2
answers
492
views
Model Theoretic Localization
This is a re-post on a previous question I asked. My first question was too vague to warrant detailed responses. Really, I have two specific questions to ask.
1) Let $\sigma = (A; \{0,1\}; +, \times)...
- 761
-2
votes
1
answer
371
views
Localization of Formulas [closed]
Can someone point me to an article concerning the "inversion" of formulas?
- 761
5
votes
2
answers
3k
views
Do you believe P=NP? [closed]
Do you believe P=NP?
I've seen some mathematicians say that if P=NP their work would be worthless and restricted to enunciating theorems. They seem to believe that there exist an almost philosophical ...
- 349
2
votes
1
answer
259
views
Nuclearity of certain semigroup crossed product C*-algebras
This question is related to this question link.
Suppose we have an (abelian) semigroup $S$ acting by endomorphisms on a $C^*$-algebra A giving rise to a semigroup crossed product $B = A\rtimes S$. ...
- 2,029
5
votes
7
answers
6k
views
Ask for recommendations for textbook on mathematical logic
I studied mathematical logic using a book not written in English. I would now like to study it again using a textbook in English. But I hope I can read a text that is similar to the one I used before, ...
- 764
9
votes
2
answers
1k
views
Non-Standard Prime
Hello,
My question is about the non-standard models of the integers. If we add to the Peano's axioms $P$ of arithmetic the following axioms for a fixed constant $c$:
$c \neq 0$, $c \neq 1$, $c \neq 1+...
- 663
65
votes
16
answers
8k
views
What is the high-concept explanation on why real numbers are useful in number theory?
The utopian situation in mathematics would be that the statement and the proof of every result would live "in the same world", at the same level of mathematical complexity (in a broad sense), unless ...
3
votes
1
answer
392
views
Can cones (toric monoids) be built as colimits of their faces?
Suppose $L$ is a lattice (free abelian group) and $\sigma$ is a (pointed) spanning rational cone in $L\otimes\mathbb Q$. Then $M=L\cap \sigma$ is a monoid with $M^{gp}=L$. A monoid of this form is ...
- 24.1k
7
votes
1
answer
994
views
Is this a proper application of the Lowenheim-Skolem Theorem to a proper class?
Please don't get put off by the length, all the questions are quite simple, but given the quasi-mathematical context I tried to be precise with the formulation. The more mathematically interesting ...
- 497
5
votes
1
answer
655
views
an example of a semigroup with solvable word problem but unsolvable power problem
We say that a semigroup $S$ has solvable power problem if there is an algorithm that takes as input an element $s \in S$ and decides whether or not there exist $m,n \in \mathbb{N}$ with $m \neq n$ and ...
- 549
7
votes
1
answer
441
views
Looking for papers and articles on the Tarskian Möglichkeit
Some background: Łukasiewicz many-valued logics were intended as modal logics, and Łukasiewicz gave an extensional definition of the modal operator: $\Diamond A =_{def} \neg A \to A$ (which he ...
- 173
1
vote
1
answer
1k
views
Is there a language in $RE \setminus R$ which is not $RE$-complete?
If any recursively enumerable language can be reduced by a mapping reduction to a language $L$, then $L$ is called $RE$ complete. In that case, $L$ must be in $RE\setminus R$. But are there languages ...
- 87
13
votes
4
answers
3k
views
Is modern computability theory "really" about algorithms?
Apologies if my question seems overly naive, but I haven't seen/heard/read any good answers.
What is modern computability theory "really" about? The study of feasible(even remotely feasible) ...
- 141
4
votes
1
answer
1k
views
Questions on ultrafilters
Hi, I know that there are models in ZFC where don't exist p-points, but I can't find (neither on internet) a proof that I understand, some of you could help me please?
Another question: I know that ...
- 279
2
votes
1
answer
995
views
final step(s) for a proof that a function is not primitive recursive
My function is $f:\mathbb{N} \rightarrow \mathbb{N},\ f(n)=2\uparrow ^n 3$ , the Ackermann(-Péter) function, with the second argument fixed to 3 (and "$\uparrow$" the Knuth up-arrow), which I believe ...
- 429
2
votes
1
answer
436
views
Omega_1 Categorical Theory
Hi,
In Chang & Keisler "Model Theory" it is claimed that the theory of a one-to-one function of A onto A with no finite cycles is $\omega_1$- categorical (page 140). Why is that, and is there a ...
- 639
7
votes
1
answer
650
views
Cones, monoids, and the space of (very) ample divisors
An interesting and useful tool to study a projective variety is its ample cone. Understanding the structure of this cone reveals information about the variety, and it is an isomorphism-invariant so ...
- 1,871
1
vote
4
answers
1k
views
Condition of possibility = Co-Implication
Sorry, but I do not know another place to post this question.
Condition of possibility is an important philosophical concept. Naively, this concept could be formally defined this way:
$q$ is a ...
- 9,720
13
votes
7
answers
2k
views
(Non?)-linearity of the consistency strength ordering in ZF
Much of the research taking place in set theory, is related to the classification of sentences according to their consistency strength relative to ZF. In order to be more specific, we say that for all ...
- 360
22
votes
1
answer
1k
views
Concerning the rarity of provably transcendental real numbers
Does there exist any rubric where provably transcendental real numbers emerge, in a meaningful way, as rare among all the transcendental numbers?
Here are some of the things I'm worried about:
1) To ...
- 17.6k
39
votes
4
answers
6k
views
Completion of a category
For a poset $P$ there exists an embedding $y$ into a complete and cocomplet poset $\hat{P}$ of downward closed subsets of $P$. It is easy to verify that the embedding preserves all existing limits and ...
- 4,096
14
votes
2
answers
1k
views
Induction, the infinitude of the primes, and workaday number theory
There are various open problems in the subject of logical number theory concerning the possibility of proving this or that well-known standard results over this or that weak theory of arithmetic, ...
- 17.6k
26
votes
9
answers
5k
views
Proofs of Gödel's theorem
I am interested in different contexts in which Gödel's incompleteness theorems arise. Besides traditional Gödelian proof via arithmetization and formalization of liar paradox it may also be obtained ...
- 1,175
4
votes
0
answers
577
views
Tropical Properties From Algebraic Geometry
What properties of tropical geometry (Starting from a valued Field) can be proven to be true using their analogue in algebraic geometry? For example, using the valuation on the Puiseux series $\mathbb{...
- 345
1
vote
1
answer
654
views
Completeness of Algebraically Closed Valued Fields(ACVF) Theory
One can prove Elimination of Quantifiers of ACVF finding an extension of any partial embedding of a model $K$ into a $|K|^+$ Saturated one using the language $\mathcal{L} = ( 0,1,+,*, U, \mid )$. In ...
- 345
10
votes
1
answer
991
views
What is the "Physically Consistent" proper subset of arithmetic?
Suppose 1st-order arithmetic is inconsistent along with Voevodsky http://video.ias.edu/voevodsky-80th.
It nevertheless remains true that when you have 2 apples and 2 apples, you have 4 apples. ...
- 167
0
votes
1
answer
172
views
Equivalence of monadic axioms
Call two axioms equivalent if they imply the same set of theorems. I am interested in decidability of so defined equivalence. In this generality the problem is obviously undecidable since it can be ...
- 3
5
votes
0
answers
647
views
Adjunction between classic and intuitionistic logic
Let $\Sigma$ be a (classic, single-sorted) signature. Denote by $\mathit{Mod}\_H(\Sigma)$ the category of $H$-valued models over $\Sigma$, where $H$ is a complete Heyting algebra. Then for any first-...
- 4,096
3
votes
3
answers
620
views
Algebraically Closed subsets and strong amalgamation
I came accross the following
Theorem:
If $A$ is an $\aleph_0$- categorical structure, then the algebraically closed substructures of $A$ satisfy the strong amalgamation principle. (for definitions ...
- 2,882