**0**

votes

**1**answer

208 views

### A question regarding extendible cardinals and a result of M. Magidor

The following definitions and Theorems come from M. Magidor's paper "On the Role of Supercompact and Extendible Cardinals in Logic" (Israel J. Math., Vol. 10, 1971):
"Definition: Logic is called ...

**-1**

votes

**1**answer

104 views

### recursively enumerable sets [closed]

A set $S$ said to be recursively enumerable if There is an algorithm that enumerates the members of $S$. That means that its output is simply a list of the members of $S$: $s_1$, $s_2$, $s_3$, ... . ...

**8**

votes

**1**answer

446 views

### Why is the set-theoretic principle $\diamondsuit$ called $\diamondsuit$?

A shallow answer would just point to theorem 6.2 in Jensen's 1972 paper "The fine structure of the constructible hierarchy", where Jensen introduces this property. Or was this symbol used already ...

**17**

votes

**1**answer

875 views

### the true reason of the incompleteness of formal systems

A 3/4 year ago, I read Gödel's beautiful paper "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme 1". There is one thing, I never understood.
In a footnote, Gödel ...

**2**

votes

**1**answer

219 views

### Classification Theory

It is often said that unsuperstable theories do not admit a classification in the sense of Shelah. Why exactly is this so? And also what exactly does in the sense of Shelah mean? It is hand waved in a ...

**-2**

votes

**1**answer

87 views

### Reconciling undecidability of FOL with Soundness and Completeness of Hilbert Proof Systems [closed]

I am reading Logic and Declarative Languages by Michael Downward, where he describes Hilbert's Proof System for First Order Logic and states that it is both sound and complete, he then adds that:
...

**5**

votes

**1**answer

275 views

### Diagonalizing against a non stationary set of functions

Suppose $\kappa$ is regular uncountable (assume $2^{< \kappa} = \kappa$ and $\kappa$ is weakly Mahlo if needed). Is the following true?
For every sequence $\langle f_i: i \to 2 \mid i \in A ...

**3**

votes

**1**answer

194 views

### Number of non-isomorphic models

I had this question up on Math stackexchange: http://math.stackexchange.com/questions/1349247/number-of-non-isomorphic-models/1350763#1350763 . While it was answered partially there, I'm posting here ...

**0**

votes

**0**answers

319 views

### Set as a (strict) infinite-category?

First, let me say that I have no idea if such a post has its place here. However, I believe that the ideas I'm going to present are important. The goal of this thread is three fold:
1) trying to ...

**8**

votes

**0**answers

266 views

### preserving saturated ideals

A reliable source made the following claim:
Suppose CH there is an $\omega_2$-saturated ideal on $\omega_1$. Then this is preserved by $\mathrm{Add}(\omega_1,\omega_2)$.
Question 1: How do you ...

**29**

votes

**3**answers

3k views

### What is the reverse mathematical strength of the fundamental theorem of algebra?

Reverse mathematics (RM) is that area that tries to pin down exactly which axioms are necessary to prove theorems, given some weak base theory. Harvey Friedman has pointed out several times (on the ...

**5**

votes

**1**answer

139 views

### On an automatic translation of typed lambda calculus in untyped lambda calculus

I have a question regarding the "compilation" of typed lambda calculus in untyped lambda calculus.
Take for example the inductive definition of lists, with introduction rules:
and:
We can ...

**1**

vote

**0**answers

96 views

### Type theory: can multiple elimination rules be defined, in principle?

I'd like to ask a question on type theory:
Consider the usual type theoretical definition of the natural numbers. We could give an elimination rule in the form:
or in the form:
I called the ...

**2**

votes

**2**answers

163 views

### Pseudo-decision procedures for first order arithmetic

I was reading this paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.2911&rep=rep1&type=pdf in which the author describes an algorithm, based on Groebner basis, ...

**5**

votes

**0**answers

101 views

### Lascar strong types in fragments of arithmetic

Are Lascar strong types (definition below) in models of fragments of arithmetic always type definable? (They trivially are, in models of full induction.)
Definition Given a saturated model ${\cal M}$ ...

**4**

votes

**2**answers

794 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:
...

**6**

votes

**1**answer

273 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}$?

**11**

votes

**0**answers

197 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

**2**answers

335 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

**1**answer

134 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

**1**answer

400 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

**1**answer

213 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

**0**answers

195 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 ...

**20**

votes

**3**answers

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

**0**answers

193 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

**1**answer

176 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

**0**answers

273 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

**0**answers

258 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 ...

**8**

votes

**1**answer

259 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

**3**answers

524 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

**1**answer

411 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

**0**answers

105 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

**1**answer

180 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

**1**answer

223 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 ...

**10**

votes

**2**answers

628 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

**0**answers

210 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

**1**answer

325 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

**1**answer

310 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

**0**answers

307 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

**1**answer

200 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

**0**answers

106 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 ...

**23**

votes

**1**answer

1k 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

**3**answers

300 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

**2**answers

165 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

**4**answers

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

**1**answer

188 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}$: ...

**2**

votes

**2**answers

139 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

**0**answers

366 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

**1**answer

455 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,
...

**6**

votes

**1**answer

137 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 ...