first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, ...

learn more… | top users | synonyms (1)

31
votes
3answers
799 views

On sentences true in all finite groups

Let $w$ be a group word with two variables $x$ and $y$. Is the sentence $(\forall x)(\exists y)w=1$ true in every group if it is true in every finite group? The same question about the sentence ...
5
votes
1answer
86 views

Do non-normal states exist in the Solovay model?

Let H be an infinite dimensional Hilbert space. Then there exist non-normal states on B(H) in ZFC (i.e. states that are not represented by a density operator). Is this also true in the Solovay model ...
1
vote
1answer
85 views

Are monoids with zero and partial homomorphisms related?

Context: Let $\Sigma=\{U,C,A,G\}$ and $L\subset\Sigma^*$, i.e. $L$ is a language over the alphabet $\Sigma$. Let $\Sigma'=\{0,1\}$ and define a homomorphism $f:\Sigma^*\to\Sigma'^*$ by extending $U ...
-5
votes
0answers
423 views

What is the single and double derivative of following equation? [on hold]

d/dt(e^ (-0.06 pi t))(sin(2t-pi)) using product rule fine the double and single derivative.please help me to solve this?
5
votes
1answer
265 views

A property of the Frechet filter and every ultrafilter

(Joint question with Piotr Szewczak.) Definitions and notation. By filter we mean a filter on $\omega$ containing the cofinite sets at least. For a filter $\mathcal{F}$, let ...
4
votes
1answer
130 views

Induction and nonstandard halting times of standard machines

For a nonstandard model of enough arithmetic - say, $\mathcal{N}\models I\Sigma_1$ - we can define the set of halting times of standard machines relative to $\mathcal{N}$: ...
0
votes
0answers
21 views

Lists of sets as objects of ZF axiomatics [migrated]

I have a naive question about foundations of mathematics. A common opinion of most mathematicians is that the essential part of mathematics can be reduced to ZF(C) axioms. I do not quite understand ...
34
votes
5answers
3k views

Does “compact iff projections are closed” require some form of choice?

There are many equivalent ways of defining the notion of compact space, but some require some kind of choice principle to prove their equivalence. For example, a classical result is that for $X$ to be ...
-2
votes
0answers
56 views

Formulating conditional constraints in optimization [closed]

In an optimization problem, is it possible to formulate the following conditional constraint: If $y > x_1$ then $x_2 \ge y - x_1$, else $x_2=0$. Here are $x_1$ and $x_2$ are to be determined by ...
7
votes
0answers
256 views

Godel's second incompleteness theorem for non-r.e. theories

R. Jeroslow in this paper proves that a non-recursively enumerable theory whose set of theorems is $\Delta_2$-definable may prove consistency of itself but it can not prove 2-consistency of itself. ...
18
votes
2answers
2k views

Should there be a true model of set theory?

As I understand it, there is a program in set theory to produce an ultimate, canonical model of set theory which, among other things, positively answers the Continuum Hypothesis and various questions ...
28
votes
0answers
668 views

Bidi: A new cardinal characteristic of the continuum?

This question assumes familiarity with combinatorial cardinal characteristics of the continuum. Identify an infinite set $a\subseteq\mathbb{N}$ with its increasing enumeration. Thus, for each natural ...
3
votes
2answers
119 views

${\frak b}$ and ${\frak d}$ defined with $\leq$ instead of $\leq^*$

Let $\omega^\omega$ denote the collection of all functions $f:\omega\to\omega$. For $f,g\in\omega$ we define $f\leq g$ if $f(n)\leq g(n)$ for all $n\in\omega$; $f\leq^* g$ if there is $N\in\omega$ ...
0
votes
0answers
35 views

Logic and Metamath book recommendation [migrated]

Recently, I got interested in Mathematical Logic and now I am looking for good introductory books on Mathematical Logic for beginners. In fact, I plan to read some good books on Metamathematics also. ...
5
votes
1answer
286 views

Elementary equivalence of the direct product and direct sum of groups

It is well-known that the direct product of any family of abelian groups is an elementary extension of the direct sum of the family (see e.g. Lemma A.1.6 in the book `Model Theory' by W. Hodges, ...
-1
votes
0answers
12 views

Expressing conditional statements using quantifiers and predicates in Predicate Logic: how to recognize the hypothesis and conclusion in statement [migrated]

I was solving questions of Discrete Mathematics and Its Applications By Kenneth H. Rosen Chapter 1 The foundations: Logic and Proofs , when i got stuck at this problem; two similar problems are ...
5
votes
1answer
95 views

Minimal degrees of structures

For this question, a structure means a first-order structure in a computable language with domain $\omega$; a copy of a structure $\mathcal{A}$ is a structure $\mathcal{B}\cong\mathcal{A}$. Given a ...
10
votes
2answers
446 views

History of Tarski's problems on free groups

As is known, Tarski posed his questions about first-order theories of non-abelian free groups around 1945. However, the questions were not published in his papers or books. What is the original ...
6
votes
1answer
253 views

If two structures are elementarily equivalent, is there a zigzag of elementary embeddings between them?

Fix a first-order signature $\Sigma$. There is an equivalence relation $\sim$ on the class $\Sigma\mathrm{-Str}$ of all $\Sigma$-structures given by $M \sim N$ iff $M$ and $N$ are elementarily ...
2
votes
1answer
79 views

Explanation of the definition of Saturated Sets in Lambda Calculus

I have a question on the definition of Saturated Sets, as particular subset of the set of strongly normalizing terms in lambda calculus. Here is the definition: a set $S$ of strongly normalizing ...
129
votes
27answers
16k views

What are some reasonable-sounding statements that are independent of ZFC?

Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC." For example, suppose A is an abelian group such that every ...
1
vote
1answer
262 views

Is second-order ZFC categorical with regard to its proper class models

Second-order ZFC offers partial categoricity in the sense that, given any two models, one of them must be isomorphic to an initial segment of the other [1]. However, this leaves questions regarding ...
2
votes
1answer
167 views

Is there a 'largest' second-order categorical axiomatization of set theory, extended from ZFC2

While it's possible to obtain categorical second-order axiomatizations of set theory by extending ZFC2 with additional axioms (see [1]), these axioms tend to be somewhat arbitrary (e.g. adding an ...
4
votes
0answers
102 views

Is the lowenheim-skolem number of nth order logic larger than the corresponding number for 2nd order logic

According to this paper, by Vaananen, the $LS$ number for $2^{nd}$ order logic is given by "the supremum of $Π_{2}$-definable ordinals", where "The Lowenheim-Skolem number $LS(L)$ of $L$ is the ...
1
vote
1answer
88 views

PA proves that functions are total

Is there a total recursive function $f:N \to N$ such that for no $\Sigma_1$ formula $\phi(x,y)$ which defines it (i.e., defines its graph), is it true that PA proves that "$\phi$ defines a total ...
7
votes
1answer
303 views

Canonical functions in set theory and their applications

Given regular cardinal $\kappa>\omega,$ we can define the canonical functions $f_\alpha: \kappa\to \kappa,$ for $\alpha<\kappa^+.$ Some of their properties are presented in Chapter 22 of the ...
4
votes
1answer
193 views

What consistency results follow the assumption: $\forall\alpha(\aleph_{\alpha+1}\nleq2^{\aleph_\alpha})$?

In a recent question on Math.SE it was asked whether or not For every infinite cardinal $\mathfrak m$ there is no $\aleph$ number, $\kappa$, such that $\mathfrak m<\kappa<2^{\mathfrak m}$. By ...
16
votes
4answers
638 views

Is there a Leibnizian model with no definable elements, in a finite language?

A first-order structure $M$ is Leibnizian, if any two distinct elements $a,b\in M$ satisfy different $1$-types; that is, if there is some formula $\varphi$ such that $M\models\varphi(a)$ and ...
99
votes
13answers
20k views

Knuth's intuition that Goldbach might be unprovable

Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really ...
2
votes
2answers
302 views

System of boolean equations, Satisfiability

Are there any methods to "solve" large systems of boolean equations? $$x_{i1}\vee x_{i2}\vee x_{i3} = b_i, \quad\text{for}\quad i=1,\dots,N,$$ where $x_i, b_i \in\{0, 1\}$ For example $$x_{1}\vee ...
3
votes
1answer
119 views

when is the property “being algebraically maximal” a first order property ?

A valued field is said to be algebraic maximal if all its algebraic extension have either a bigger value group or a bigger residue field. Do you know for which field this is a first order property ? ...
15
votes
1answer
425 views

Whatever happened to $L(j)$?

So this question probably shows my inner model theoretic ignorance, but: In "Two remarks on elementary embeddings of the universe" (http://projecteuclid.org/download/pdf_1/euclid.pjm/1102969567), ...
9
votes
1answer
287 views

Are there trees for $(\Sigma^2_1)^{\text{uB}}$?

If there is a proper class of Woodin cardinals, then Woodin showed (using stationary towers) that $(\Sigma^2_1)^{\text{uB}}$ statements are generically absolute, where $\text{uB}$ denotes the ...
55
votes
13answers
10k 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 half of ...
-1
votes
0answers
213 views

Comparing the Kolmogorov complexity of theories - Part 2

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...
1
vote
0answers
122 views

What can be said about a Boolean-valued structure from what the Boolean-valued forcing extension thinks about it?

Suppose that $\phi$ is a formula in the language of set theory such that there are some $n_{1},...,n_{k}$ such that if $V\models\phi(x)$, then $x=(X,R_{1},...,R_{k})$ and ...
6
votes
2answers
621 views

A question on rank-to-rank embeddings

Consider a non-trivial elementary embedding $j:V_\lambda\to V_\lambda$ and, for each $A\subset V_\lambda$, set $j(A)=\bigcup_{\delta<\lambda}j(A\cap V_\delta)$. In Implications between strong ...
11
votes
0answers
318 views

Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that ...
6
votes
0answers
244 views

Reference for “if the set $A$ is Suslin, then every $\Sigma^1_1(A)$ set is Suslin”

Does anyone know of a reference for one or both of the following facts (in $\mathsf{ZF}$)? If the set of reals $A$ is Suslin, then every $\Sigma^1_1(A)$ set of reals is Suslin. If $T$ is a tree on ...
0
votes
0answers
33 views

How can nontrivial elementary embeddings of the universe to some inner model be surjective? [migrated]

Consider $\kappa$ to the least measurable cardinal, or equivalently $\kappa$ is the critical point for an elementary embedding $j:V \rightarrow M$ from the universe $V$ to an inner model $M$ (critical ...
5
votes
1answer
89 views

When is a formula preserved under taking factors in a reduced product or the stalk in a Boolean product?

I want to know if there is a nice characterization of when a formula is preserved under taking reduced factors. We say that a formula $\phi$ is closed under taking reduced factors if whenever $I$ is ...
5
votes
0answers
165 views

Universal anti-Horn classes?

Is there published work about universal anti-Horn classes? Anti-Horn formulas are also sometimes known as dual Horn. See also related question Is there any research of universal algebras ...
24
votes
4answers
1k views

Forcing as a replacement of induction and diagonal arguments

Let me give some examples motivating the question. The use of forcing instead of induction: For this consider Cantor's theorem: Theorem 1. Any two countable dense linear orders $I, J$ without end ...
13
votes
2answers
877 views

When does Vopěnka's principle hold?

Vopěnka's principle (VP) is the statement that, given any proper class $\{\mathcal{A}_\eta: \eta\in ON\}$ of first-order structures in the same language, there are some $\alpha\not=\beta$ with ...
7
votes
1answer
351 views

Explicit counter example to Vopěnka's principle in the constructible universe?

Vopěnka's principle is a large cardinal axiom which has many equivalent formulations. One of them, which I find especially appealing, is the following: if the universe is satisfies Vopěnka's principle ...
13
votes
1answer
608 views

Analogues of Primitive Recursive Functions

Let $\mathbf{A}$ be an admissible set (possibly with urelements). I am wondering if there is some good notion of "primitive recursive arithmetic" relative to $\mathbf{A}$. More precisely, I would like ...
7
votes
1answer
86 views

Strongly minimal set with DMP

Recall that a strongly minimal theory $T$ has the Definable Multiplicity Property (DMP) if for all natural $k$, $m$ and $\varphi(\bar{x},\bar{b})$ of rank $k$, multiplicity $m$, there exists a formula ...
0
votes
0answers
100 views

A question on complexity notation

I am considering writing ''$\Pi^{n}_{i_{0},...,i_{n-1}}$-comprehension'' as abbreviation for ''$\Pi^{0}_{i_{0}}$-comprehension plus ... plus $\Pi^{n-1}_{i_{n-1}}$-comprehension'' in the context of an ...
3
votes
1answer
146 views

Maximality statements that cannot be proved using $\mathsf{ZL}$ [closed]

What are examples for maximality statements that cannot be proved using Zorn's Lemma?
11
votes
2answers
829 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 ...