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)

4
votes
2answers
773 views

What lets the Square of Opposition fail in Intuitionistic Logic?

See moderator's note in the comments. I just came across the following. In intuitionistic logic and classical logic we have the following consequences: ...
9
votes
1answer
247 views

Countable group with uncountable number of subgroups $< 2^{\aleph_0}$

Is it consistent that there is a countable group $G$ such that the cardinality of the set of subgroups of $G$ is uncountable, but strictly less than $2^{\aleph_0}$?
10
votes
0answers
182 views

Generic $\mathbf{\Sigma}_3^1$-absoluteness for class forcings

In the paper "Generic Absoluteness" by Bagaria and Friedman (http://www.logic.univie.ac.at/~sdf/papers/bagfried.pdf) it is shown that in ZFC generic $\mathbf{\Sigma_3^1}$-absoluteness is false for ...
7
votes
2answers
298 views

Topological tameness beyond the Gandy-Harrington topology

The Gandy-Harrington topology on $\omega^\omega$ is the topology generated by all lightface $\Sigma^1_1$ sets; that is, all sets which are continuous-in-the-usual-sense images of $\omega^\omega$. ...
-1
votes
1answer
110 views

Non-standard naturals and goodstein sequences [closed]

By the Kirby–Paris theorem, Goodstein's theorem is independent of Peano arithmetic (PA). Therefore there are non-standard models in which every Goodstein sequence terminates. However, Tennenbaum's ...
9
votes
1answer
384 views

Just a little absoluteness might be cheaper?

Absoluteness is a wonderful thing, but expensive consistency-strength wise. My question is, when can we get large amounts of absoluteness in specific situations for much cheaper? Specifically, fix a ...
8
votes
1answer
192 views

Is the Jordan decomposition of a self-adjoint functional constructive?

Let $A$ be an abstract C*-algebra, and let $\varphi\colon A \rightarrow \mathbb C$ be a bounded linear function. Assuming the axiom of choice, there exist unique positive bounded linear functions ...
9
votes
0answers
183 views

The Chang model after collapsing an inaccessible limit of Woodins

If $\kappa$ is an inaccessible cardinal and $G \subset \operatorname{Col}(\omega,\mathord{<}\kappa)$ is a $V$-generic filter, then in $V[G]$ the Chang model $L(\text{Ord}^\omega)$ satisfies "every ...
19
votes
3answers
2k views

Who needs Replacement anyway?

The set theory ETCS famously comes without the Replacement axiom schema (or an equivalent) that is part of ZFC. One (to me, not apparently useful) set that one cannot build in ETCS is $\coprod_{n\in ...
4
votes
0answers
186 views

Primitive Closure Arithmetic

I am researching a system that was designed by myself and what I call PCA (Primitive Closure Arithmetic), because it looks like PRA. The differences are: - PRA uses recursive definition with a ...
0
votes
1answer
164 views

Definition of “Expected/Unexpected Event”

Background of my question is Martin Gardner's "unexpected hanging" paradoxon, which has once again be the subject of an article in a popular-scientific magazin (this time because this year it has been ...
11
votes
0answers
255 views

Adding a saturated ideal

Is it consistent that there is no $\omega_2$-saturated ideal on $\omega_1$, but one is introduced by an $\omega_2$-closed forcing? Some motivation: If $\delta$ is a Woodin cardinal, then it remains ...
10
votes
0answers
234 views

c.c.c forcing notions and adding minimal generic reals

Is the following statement consistent: ``There is no non-trivial c.c.c forcing notion adding a minimal generic real''? The question is related to Prikry's question: Is it consistent that any ...
7
votes
1answer
248 views

For a ring $k$ and a set $X$, what are the $k$-algebra homomorphisms $k^X \to k$?

Let $k$ be a commutative ring. Feel free to assume it's a field. Let $X$ be a set. This question is only interesting when $X$ is infinite. Write $k^X$ for the $k$-algebra of functions $X \to k$, ...
11
votes
3answers
516 views

The size of Lindelof space

Question. Suppose that $X$ is a Lindelof space such that every point of $X$ is a $G_{\delta}$-point. Then is it true that $|X| ≤ 2^{\omega}$?
9
votes
1answer
390 views

Is $\clubsuit_{\omega_1}$ enough to get Suslin tree?

This is problem 15.3 in Arnie Miller's problem list: (Juhasz) Suppose there exists $\langle A_{\alpha} : \alpha \in L \rangle$, where $L$ is the set of limit ordinals below $\omega_1$ and for each ...
2
votes
0answers
86 views

BL Algebras that allow for Compactness to hold

Say we have a model $M$ of a theory $T$ of some core fuzzy logic. When dealing with compactness, we run in to a situation where the new model being built (by the use of compactness over $M$), will ...
4
votes
1answer
173 views

Cohen algebra and $\mathcal P(\omega)/ \mathrm{fin}$

Let $C$ be the Cohen algebra, the boolean completion of the partial order of finite partial functions from $\omega$ to 2, ordered by reverse inclusion. Does there exist an ideal $I$ on $C$ such that ...
11
votes
1answer
202 views

Does Peano's existence theorem admits a constructive proof?

$$y(t)=y_0+\int_0^t b(y(s))ds$$ $b\in C(R^d)\cap L^\infty(R^d)$ The classical proof for Peano's existence theorem in ODE need use the Ascoli's theorem, so it's not constructive. When $d=1$, in the ...
8
votes
2answers
596 views

What does “simplification of proofs as evaluation of programs” mean?

I am currently going through Philip Walder's "Proposition as Types" and a passage of the introduction has struck me: for each way to simplify a proof there is a corresponding way to evaluate a ...
2
votes
0answers
202 views

Is there a $\Sigma^0_3$-complete ideal on $\omega$?

In Kechris's book "Classical Descriputive set theory" Chapter 23 (Exercise 23.4), it claim that there is a $\Sigma^0_\xi$-complete ideal on $\omega$ for each $\xi\geq 3$. There is a candidate ...
5
votes
1answer
308 views

Details for Woodin's forcing argument for a saturated ideal from the Levy collapse

Theorem 2.65 in Woodin's book shows that a saturated ideal on $\omega_1$ exists after Levy-collapsing a Woodin cardinal $\delta$ to $\omega_2$. I am confused about the part of the argument where he ...
9
votes
1answer
288 views

Can there be a tree of height $\omega_2$ having all levels countable, with no cofinal branch?

For many years I had the idea that if a well-founded tree is both very tall and very narrow, then it must have a cofinal branch. For example, it is a fun exercise to show that any $\omega_1$-tree ...
11
votes
0answers
301 views

On sentences true in all finite groups (revisited)

Let $w$ be a group word with variables $\bar x, \bar y$, where $\bar x=(x_1,\dots ,x_m)$ and $\bar y=(y_1,\dots ,y_n).$ I am interested in the following questions. (1) Is the sentence $(\forall\bar ...
7
votes
1answer
193 views

Introducing meets while preserving directed closure

A poset $\mathbb{P}$ is called well-met iff every pair of compatible conditions in $\mathbb{P}$ has a greatest lower bound. Question: Suppose $\mathbb{P}$ is a separative partial order which is ...
5
votes
0answers
95 views

O-Minimal sentences in $L_{\omega_1,\omega}$?

Is there any meaningful sense in which we can talk about o-minimal sentences of $L_{\omega_1,\omega}$? I can give a first attempt, easily; given a countable fragment $F$ and a sentence $\Phi$ in that ...
22
votes
1answer
938 views

How hard is it to destroy a diamond? (with a real)

If we start with $V\models\lozenge$, it is not hard to force the failure of diamond. You can blow up the continuum, or destroy all the Suslin trees. You can blow up the continuum of $\aleph_1$, and ...
7
votes
3answers
277 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
2answers
159 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 ...
38
votes
4answers
1k 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 ...
4
votes
1answer
172 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}$: ...
5
votes
2answers
135 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$ ...
7
votes
0answers
343 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. ...
5
votes
1answer
352 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, ...
5
votes
1answer
117 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 ...
6
votes
1answer
289 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
168 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 ...
29
votes
0answers
759 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 ...
1
vote
1answer
302 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
192 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 ...
1
vote
1answer
105 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 ...
4
votes
0answers
117 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 ...
4
votes
1answer
226 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 ...
17
votes
4answers
688 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 ...
15
votes
1answer
442 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), ...
1
vote
0answers
125 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 ...
11
votes
0answers
345 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
257 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 ...
13
votes
2answers
905 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
369 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 ...