Tagged Questions

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)

3
votes
2answers
231 views

A Question related to the Formula Hierarchy

Let large Latin symbols as $X$ and $Y$ denote sets of natural numbers and small symbols as $n$ and $n´$ denote natural numbers and small Greek letters stand for formulas. Suppose $\alpha$ is ...
-3
votes
0answers
49 views

Computability Theory [on hold]

If $A\equiv_T B$ then $A^{\omega}\equiv_1 B^{\omega}$. Odifredi in his book says hint $A\leq_T B$ implies that $A\leq_1 B'$, but don't know how this helps.
1
vote
0answers
113 views

Concept of synchronizability

This thread is about the concept of synchronizability. It's a concept I tried to formalize in its most general sense but without success. The goal of this thread is therefore to try to formalize it in ...
5
votes
2answers
535 views

Decidability of decidability

The questions I'm going to ask are non formal because they concern decidability of decidability, and I couldn't find any references on that after some quick searches. I hope that this thread is still ...
2
votes
2answers
213 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 ...
6
votes
1answer
414 views

Does Nelson try to prove PA inconsistent directly?

Edward Nelson is known for his serious attempts to show that Peano axioms, and sometimes even weaker theories, are inconsistent. I wasn't able to find Nelson's papers anywhere, so I wanted to ask a ...
10
votes
1answer
303 views

Is there an $L$ like inner model for $\sf Z$?

Godel proved the consistency of the axiom of choice with the axioms of $\sf ZF$ by showing that given any model of $\sf ZF$, there is a definable class which satisfies $\sf ZFC$. The proof uses a lot ...
9
votes
0answers
168 views

Reinhardt cardinals and iterability

Work in $ZF$. Let $j:V\to V$ be a non-trivial elementary embedding which is iterable, so that we can iterate it and form models $M_\alpha, \alpha\in ON,$ with $M_0=V,$ and elementary embeddings ...
7
votes
0answers
140 views

Countable choice in $L(\mathbb{R}^*_G)$

Let $\lambda$ be a singular strong limit cardinal and let $G \subset \text{Col}(\omega,\mathord{<}\lambda)$ be a $V$-generic filter. Let $\mathbb{R}^*_G = \bigcup_{\alpha < \lambda} ...
-3
votes
0answers
121 views

About Gödel's incompleteness theorems [closed]

I think maybe I found the mistake of Gödel's incompleteness theorems first,these are something I suppose 1、the content of Proof must be able to be transformed to formal logic So my point is ...
5
votes
1answer
138 views

O-minimal Theories with Non-Dense Order Type

I asked this question on MSE, but I haven't received any comments or responses (also, it has a very low view count), so I thought I would also ask it here. In this paper, Knight, Pillay, and ...
7
votes
1answer
244 views

On $V$-decisive and weakly homogeneous forcings

Suppose that $\Bbb P$ is a forcing in $V$, we say that $\Bbb P$ is $V$-decisive if whenever $\varphi(x_1,\ldots,x_n)$ is a statement in the language of forcing, and $u_1,\ldots,u_n\in V$ then $1_{\Bbb ...
6
votes
0answers
194 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 ...
10
votes
3answers
415 views

The continuum hypothesis for packing shapes without overlapping

Consider the finite cross $C$ (=union of line segments $\overline{(0, -1)(0, 1)}$ and $\overline{(-1, 0)(1, 0)}$) and the unit half-circle $H$. It is easy to see that we may pack continuum-many ...
13
votes
1answer
298 views

Is the regularity of finitely generated rings decidable?

Q: Is there an algorithm to decide whether a given finitely generated (over $\mathbb{Z}$) commutative ring is regular? I mean by regular that the localization at every prime ideal is a regular local ...
10
votes
2answers
389 views

Is every order type of a PA model the \omega of some ZFC model?

Let $N$ be a model of first-order Peano arithmetic, and let $\sigma$ be its order-type. Does it follow that there is a (non-transitive, expect when $M$ is the standard model) $ZFC$-model $M$ such that ...
2
votes
2answers
96 views

proof that “small” sets in an extension by iterated forcing already appear in an earlier stage

In Kunen's book (introduction to independence proofs, ) the following lemma is proved (chapter 8, lemma 5.14): Assume that in M, $\alpha$ is a limit ordinal, $( ( \mathbb{P}_\xi : \xi \leq \alpha) , ...
12
votes
4answers
1k views

Is it possible to formulate the axiom of choice as the existence of a survival strategy?

Consider the following situation: There is an infinite set $G$ of giraffes. A lion comes and announces a set $C$ of all possible colours and an infinite cardinal $\kappa$. The hungry lion ...
3
votes
1answer
194 views

How to change the successor of a singular with a Woodin?

I'm looking for references on how to change the successor of a singular cardinal from "more or less" minimal assumptions. If possible, then without adding bounded subsets to the singular either. In ...
5
votes
1answer
172 views

Consistency of Weak Diamond with a Weak Version of Martin's Axiom

If $S \subset \omega_1$ is stationary, then the weak diamond principle $\Phi(S)$ states that for any $F: 2^{<\omega_1} \to 2$, there is a $g: \omega_1 \to 2$ such that for all $f: \omega_1 \to 2$, ...
4
votes
1answer
296 views

Forcing is intuitionistic

The main idea of why it´s necessary a generic filter $G$ to extend a countable transitive $\epsilon$-interpretation (not necessarily a model) $M$ is given by the condition (for which $G$ being a ...
-1
votes
3answers
164 views

About “absolute proof” of Arithmetic consistency [closed]

Ok so as Godel's theorems states, you cant prove that Peano arithmetic is consistent by using only the axioms within Peano model. You need to use axioms or rules of inferations beyond the model you ...
9
votes
4answers
463 views

Boolean Valued Models of PA

O.K, a massively naive question. I've never really studied any non-standard models of PA before. I was just wondering if there's ever been any attempt to use the kind of Boolean valued model theory ...
-2
votes
1answer
250 views

What is the Shortest Axiom of Classical Conditional-Negation Propositional Calculus? [closed]

Suppose that we only have propositional variables and connectives. Suppose our rules of inference are detachment {C$\alpha$$\beta$, $\alpha$} $\vdash$ $\beta$, and uniform substitution. Suppose that ...
0
votes
1answer
94 views

Models of BL$\forall$

What results are known about the construction of models for a theory $T$ of the logic BL$\forall$ for languages of higher cardinality? The construction for the countable case relies on 1) The fact ...
5
votes
2answers
376 views

complexity of proof of p(n) grows greater with n if for all x P(x) is unprovable?

Is it true that if "for all x P(x)" is unprovable in pA then the complexity of the proof of P(n) becomes greater as n grows bigger?
9
votes
1answer
305 views

Sets computable from enough hints

Is there a non-computable set $X\subset\omega$ such that, for some $Y\subset\omega$, any infinite subset or cosubset (=subset of the complement) of $Y$ computes $X$? More generally, call a set $X$ ...
3
votes
1answer
205 views

On fast-growing hierarchy

Is there exists a recursively enumerable set of computable total fast-growing functions $(\mathbb N \rightarrow \mathbb N)$ such, that this set has no upper boundary in the set of all such functions ...
1
vote
0answers
71 views

Real algebraic groups and pseudo-finiteness

What is the relationship between pseudo-finite groups and real algebraic groups? Could you provide an example of a pseudo-finite real algebraic group and of a non pseudo-finite one, if any? Thank ...
1
vote
2answers
230 views

An interpretation of not-Con(PA)

Edit After Andreas Blass answer below and comments below the original post I have changed it to accommodate posters' remarks. I hope it is clear and makes more sense now. Let $\mathrm{PA}$ be the ...
6
votes
1answer
251 views

higher-order reflection

In the first-order context, "reflection" of a formula $\varphi(x)$ below $\kappa$ refers to the the following situation: There are many ordinals $\alpha<\kappa$ such that for all $a \in ...
6
votes
1answer
328 views

Groups and pregeometries

Definition. For an infinite structure $\mathcal{A}$ and $cl : P(dom(\mathcal{A})) \longrightarrow P(dom(\mathcal{A}))$ , we say that $(\mathcal{A}, cl)$ is a structure carrying an $\omega$-homogeneous ...
5
votes
1answer
358 views

Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?

This question arises from an issue arising in user38200's recent question concerning models of set theory in which every definable set has a definable element. In my answer to that question, with ...
6
votes
1answer
341 views

Different approaches to forcing

There are many different approaches to the forcing method, and I am looking for all known such approaches. So my question is: Question 1. Which different approaches to set theoretic forcing are ...
6
votes
0answers
223 views

Silver's unpublished work on reverse Easton iteration

Silver was the first person who used the method of reverse Easton iterations in connection with large cardinals, and used it to force the failure of $GCH$ at some measurable cardinal. At most papers ...
5
votes
3answers
271 views

Does this property of a first-order structure imply categoricity?

Let $\mathfrak{A}$ be a first-order structure over a relational language and let $\kappa$ be an infinite cardinal. Lets say that $\mathfrak{A}$ has the $\kappa$-property if for every structure ...
6
votes
1answer
332 views

A “good scale” that is not really a scale

I don't know much about singular cardinal combinatorics, so I apologize in advance if I write something that is wrong or looks funny. First let me recall some basic definitions. Let $\lambda$ be a ...
16
votes
1answer
468 views

Three old questions on the Sacks forcing

I came across the two following Qs in 1970. Find reals $a,b$ such that $a$ is Sacks over $L[b]$ and vice versa $b$ is Sacks over $L[a]$. Note that a Sacks $\times$ Sacks generic pair definitely does ...
1
vote
0answers
93 views

reference on aperiodicity and cluster [closed]

From this image: I believe there is a message relating those clusters drawn in picture and aperiodic tiling. Does anyone have some reference on this? Thank you :)
14
votes
2answers
594 views

Are the quaternions not uncountably categorical?

Boris Zilber has argued that the field of the complex numbers is "logically perfect". For one thing, the theory of an algebraically closed field of characteristic zero is uncountably categorical: it ...
11
votes
3answers
538 views

Can Suslin (or Aronszajn) lines ever be orderings of abelian groups?

I am interested in realizing linear orders as orderings of abelian groups. In particular, can Suslin lines (and other classes of line) be realised in this way? Let $\mathcal{C}$ be a class of ...
-3
votes
1answer
260 views

When are two algorithms essentially the same? [closed]

Inspired by Blass/Dershowitz/Gurevich's paper When are two algorithms the same? (which was referenced in another context here) I tried to boil down the question to the following situation: Consider ...
5
votes
0answers
143 views

A variant of Chang's model with choice

Let $M_n$, $n < \omega$, be a models of $ZFC$ with the same ordinals, closed under countable sequences. Let $\alpha_n$ be an ordinal which is a regular cardinal in $M_n$. Question 1: Is it ...
5
votes
2answers
138 views

Algorithm for determining when polynomial iteration is bounded?

Let $f: \mathbb{Q}\to \mathbb{Q}$ be a polynomial map with rational coefficients. Let $p\in \mathbb{Q}^n$. Is there a known algorithm that given this data determines whether or not the iterates ...
9
votes
0answers
157 views

Which forcing types preserve the axiom of determinacy?

Do we have some rudimentary understanding of some properties that a forcing can have in order to guarantee that it doesn't violate the axiom of determinacy? To be more specific, in Which forcings ...
4
votes
1answer
234 views

“Is it possible to give a restricted set-theoretical definition of addition of natural numbers in terms of successor?” [Tarski]

In his paper "Restricted set-theoretical defintions in arithmetic" Raphael Robinson cites a problem posed by Tarski: Is it possible to give a restricted set-theoretical definition of addition of ...
4
votes
1answer
106 views

When are the congruence lattices nicer?

This is a purely idle question, but one I'm increasingly interested the more thought I put into it: For $\mathcal{A}$ a universal algebra (that is, nonempty set together with some named functions), a ...
12
votes
1answer
506 views

Time in Girard's Geometry of Interaction

Jean-Yves Girard writes at the end of his paper "Towards a Geometry of Interaction", page 105, that we have three intuitions about the nature of time: time is logic modulo the order of rules, time ...
6
votes
1answer
157 views

Slim Kurepa tree at a singular strong limit cardinal of uncountable cofinality

For a strong limit cardinal $\kappa$ the notion of $\kappa$-Kurepa tree is trivial: the full binary tree is a $\kappa$-Kurepa tree. Accordingly, we consider the following strengthening: A slim ...
-4
votes
1answer
191 views

An algorithm and symbolic manipulation for IF-THEN-ELSE [closed]

CONCLUSION (so far)  Look at the parentheses theorem and at the comments below the question(s) :-) As for now, only Dan Peterson has truly addressed the issue. Q1   Does there exists an ...