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)

2
votes
1answer
150 views

Meaning of notation $\mathbb{Q}^\wedge k$, $-\infty^\wedge \mathbb{Q}$ for linear orders

I am reading Friedman & Stanley A Borel reducibility theory for classes of countable structures (J. Symbolic Logic 54 (1989), 894–914; MR1011177) and a caret (${}^\wedge$) appears as notation in ...
2
votes
1answer
193 views

Forcing Language

I asked the following question (slightly paraphrased) about a week ago in Stack exchange but no one knew the answer to the particular question. I was hoping someone here might be able to help me. ...
14
votes
4answers
1k views

A New Continuum Hypothesis (Revised Version)

Define $N_n$ as $n$ th natural number: $N_0=0, N_1=1, N_2=2, ...$. What happens after exponentiation? We have the following equation: $2^{N_n}=N_{2^{n}}$. (Which says: For all finite cardinal $n$ ...
5
votes
1answer
193 views

$\Sigma_1$ Statements and Forcing Extensions

Assuming consistency of $\text{ZFC}$ (with some large cardinal axiom), is the following statement consistent with $\text{ZFC}$? Any $\Sigma_1$ statement with parameters $\omega_1,\omega_2$ which ...
5
votes
1answer
393 views

Original proof of Gödel's completeness theorem compared to Henkin's proof

May I have some clarification about original proof of Gödel's Completeness Theorem compared to "standard" Henkin's proof based on Model Existence Lemma ? My understanding of Gödel's original proof is ...
6
votes
4answers
1k views

Interactions of number theoretic conjectures and other fields of mathematics

There are many interesting open conjectures in number theory. My question is not about partial results or possible ways to prove them. It is about their interactions with the other fields of ...
8
votes
3answers
343 views

Formulas in a Field and in a Field Extension

Let $\mathbb F$ be a field and let $a, b, c, d$ be fixed elements in the field $\mathbb F$. Consider the formulas 1) $\exists\;x\;\;:\;\;x^2=-1.$ 2) $\exists\;x\;\;:\;\;(xa=c\land xb=d).$ Formula ...
3
votes
3answers
164 views

Turing Functional and $\Sigma_1^0$-formulas in models of fragments of PA

In models of PA with restricted induction power (for example, only $I\Sigma_n$ is present), the failure of higher induction scheme is characterised by the existence of definable cuts (like $\Sigma_2$ ...
4
votes
1answer
244 views

Consistency Strength of the Failure of Square on Singular Cardinals

Q1. What is the consistency strength of the failure of square on singular cardinals? Q2. What are known as partial results in this direction?
6
votes
2answers
223 views

Possible Choices for Cofinality of $\aleph_n$ without Choice

$\text{ZFC}$ proves that each $\aleph_{n}$ for $n\in \omega$ is a regular cardinal. But it seems without the Axiom of Choice there are many consistent possible choices for cofinality of such ...
8
votes
2answers
510 views

Intuitionistic algebraic topology?

Are there results in algebraic topology -- preferably relating to homology or homotopy or phraseable in simplicial sets -- that are not true in an intuitionistic logic? In other words, are there ...
9
votes
1answer
298 views

Ackermann's function over the reals

Ackermann's function is defined over integers $x$, $y$, $A(x,y)$, with conditions for when $x{=}0$ or $y{=}0$, and otherwise uses recursive definitions involving arguments $x{-}1$ and $y{-}1$. Is ...
10
votes
2answers
403 views

Ways to define “definability”

The notion of a definable set is not expressible in the language of set theory: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y)$ such that $x = \lbrace y : ...
3
votes
1answer
168 views

Failure of GCH at indescribable cardinals

Can $\Pi^m_n$ indescribable cardinal be the first one where $\text{GCH}$ fails? Hauser showed in Hauser,K.: Indescribable cardinals and elementary embeddings. J. Symb. Logic 56, 439457 (1991) that ...
4
votes
1answer
228 views

Interpreting the Galois theory of finite extensions of $\mathbb{Q}$ in PA

Any finite extension of the rationals, along with its Galois group, can be interpreted in Peano arithmetic by straightforward means. For a fixed bound $n$ in the degree this is uniform in the ...
4
votes
1answer
223 views

Proving decidability of formula without deciding it

I am looking for a theory $T$ and a formula $p$ such that there is a metaproof which establishes that either $T \vdash p$ or $T \vdash \neg p$, but which does not enable us to decide which of these ...
11
votes
3answers
554 views

The interplay between certain aspects of interpretability, model theory and category theory

I have some questions about the interplay of interpretability, model theory and category theory. Since I had difficulties in finding literature or other helpful information about this topic, it would ...
1
vote
3answers
381 views

Another adjoint pair: Definable sets and set-builder formulas

I see adjointness between the two concepts of "being a definable set" and "being a set-builder formula": A set $X$ is definable when there is a formula $\phi(x)$ such that $X = \lbrace x : ...
6
votes
0answers
159 views

Vaught conjecture for uncountable languages

Recall Vaught conjecture: the number of countable models of a first-order complete theory in a countable language is finite or $\aleph_0$ or $2^{\aleph_0}.$ Now let $\lambda$ be an uncountable ...
3
votes
1answer
92 views

Disobedience of some complete r.e. set to some additive cost function

An additive cost function is defined as $c: \omega\times \omega \to \mathbb{Q}_2$ such that it is recursive, monotonic (i.e. $c(x+1,y)\leq c(x,y)\leq c(x,y+1)$ and $c(x,y)=0$ whenever $x\geq y$, the ...
3
votes
4answers
225 views

What is the role of absoluteness in existence of a non-trivial self elementary embedding on an inner model?

ِDefinition (1): Call an inner model M "rigid" if there are no non-trivial elementary embeddings $j: M\longrightarrow M$. It is possible that $L$ is not rigid, while the problem is open for $HOD$. ...
7
votes
2answers
191 views

Natural $\Pi^1_2$ (or worse) classes of structures?

(To clarify, my interest is mainly lightface, that is, $\Pi^1_2$ instead of $\bf \Pi^1_2$, although it doesn't particularly matter.) This is just an idle curiosity. In logic, I find myself frequently ...
6
votes
1answer
521 views

A Hot Betting On HOD

Remark: This question is based on an open question at the end of a paper by Hamkins, Kirmayer, and Perlmutter: "Generalizations of the Kunen Inconistency". $HOD$ as an inner model of $ZFC$ lies ...
8
votes
1answer
276 views

Categorical Semantics for Second-Order Logics

I am currently doing some work using a categorical semantics of first-order logic. The specific semantics I am using is due to Andrew Pitts, as described in: Categorical Logic, Andrew M. Pitts, ...
5
votes
1answer
175 views

Is the consistency of $\mathcal{L}_{\infty\omega}$-sentences absolute?

The question is exactly that of the title. Suppose $\varphi\in V$ is an $\mathcal{L}_{\infty\omega}$-sentence, and $W$ is an inner model of $V$ such that $\varphi\in W$. Is the statement ...
11
votes
1answer
630 views

Can one cover the plane with less than continuum of lines?

I will be working in ZFC, but I am not assuming the Continuum Hypothesis (or Martin's Axiom). I know that it is consistent with ZFC that one can cover the real line with less than continuum of meager ...
4
votes
1answer
206 views

Nondeterministic Turing machines and the recursion theorem

This is almost certainly a silly question, but: I am currently reading Moschovakis' article "Kleene's amazing second recursion theorem" (http://www.math.ucla.edu/~ynm/papers/1602-002-1.pdf) and there ...
4
votes
2answers
241 views

On wild behavior of $\omega_{1}$ in the absence of some essential axioms of $ZFC$

The regularity of $\omega_{1}$ is one of the most well known facts of set theory. But it seems that in order to prove this simple fact we need the "full power" of mathematics! For example by an ...
2
votes
1answer
185 views

Are measures of a measurable cardinal measurable? (Edited and Updated Version)

Update: Regarding to Prof. Hamkins's guidance I restricted the questions to the "normal" measures to avoid trivial answers. Definition: Let $\kappa$ be a measurable cardinal. Define: ...
18
votes
0answers
313 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
-1
votes
1answer
170 views

A question about whether impredicative formulae always lead to (paradoxical) inconsistencies in formalized theories

Are there any examples of mathematical theories T1,T2 which satisfy the following conditions? T1 and T2 have the same "vocabulary" and are both formalized in the classical first order predicate ...
1
vote
1answer
170 views

Is elementary equivalence absolute?

Assume we have two objects $M_1$ and $M_2$ models of respective $L_{\omega_1,\omega}$-sentences $\Sigma_1$ and $\Sigma_2$. Assume $M_1$ and $M_2$ are elementarily equivalent in some model of set ...
7
votes
0answers
289 views

What is known of the reverse math of Riemann-Roch?

I hope this is not too trivial, but I think this may be well known to someone (not me).
23
votes
3answers
730 views

Does every set of reals contain a measure-zero set of the same cardinality? Does it contain a meager set of the same cardinality?

This question arises from an issue in my post on Ashutosh's excellent question on Restrictions of the null/meager ideal. Question 1. Does every set of reals contain a measure-zero subset of the same ...
11
votes
1answer
305 views

Is the inclusion version of Kunen inconsistency theorem true?

The relations $\in$ and $\subsetneq$ seem so similar in some sense. For example they are equal on ordinal numbers. So there is a natural question about their possible similar behaviors on the ...
3
votes
2answers
241 views

Is There An Algorithmic Complexity Of A Random Distribution

Has anyone studied an equivalent to algorithmic complexity for probability distributions? This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
3
votes
2answers
405 views

Are descriptive and ontological notions of equality equal? [closed]

‎Let ‎$‎‎a$ ‎and ‎‎$‎‎b$ ‎are ‎two "‎objects". ‎What ‎is ‎the ‎meaning ‎of‎ ‎‎$a=b‎‎$‎? This is one of the deepest problems of philosophy and logic because one needs a complete information about ...
9
votes
1answer
297 views

Does existence of a proper class model imply the consistency?

The fundamental theorem of model theory says that: Theorem: A first order theory is consistent if and only if it has a model. In the above theorem we assume that the domain of any model is a ...
5
votes
2answers
256 views

Can we force with Fraisse filters to solve Vaught's conjecture?

Around the classic Fraisse amalgamation theorem in model theory we have the following notions: Definition (1): If $M$ be an $\mathcal{L}$-structure then define: $age(M):=\lbrace N~|~N~\text{is ...
2
votes
1answer
192 views

What is the order type of $L$ with Godel's well ordering?

In some sense $Ord$ is a "proper class" ordinal. Unfortunately the notion of a proper class ordinal is not a straight forward generalization of the notion of "set" ordinals because the proper classes ...
2
votes
0answers
146 views

Is there a non-trivial consistency preserving transformation?

In ‎set ‎theory ‎"equiconsistency" (and not "consistency") ‎of ‎the ‎theories ‎is the‎ ‎main ‎part ‎of ‎researches. ‎So ‎we ‎usually ‎try ‎to ‎construct a‎ ‎new model ‎using a‎ ‎given ‎one. ‎In ‎the ...
7
votes
1answer
115 views

Is there a notion of Skolemization for continuous logic?

Is there a notion of Skolemization for continuous logic (that of Ben Yaacov)? It seems to me that a Skolem function would be a minimizer, and minimizers are not continuous (from the parameters of the ...
6
votes
1answer
206 views

the choice of representing formulas and Gödel's second incompleteness theorem

In Rautenberg's book (A Concise Introduction to Mathematical Logic, Universitext, Springer 2006), Gödel's second incompleteness theorem is stated: Theorem 3.2 (Second incompleteness theorem). PA ...
15
votes
2answers
1k views

Hilbert's 10th problem and nilpotent groups

I am asking this question on behalf of a colleague of mine who does not have an MO account. Nevertheless I am also interested in the answer. The question concerns relationships between Hilbert's ...
1
vote
0answers
177 views

Are there two mutually incompatible consistent sentences in the language of PA, neither of which is true in the standard model? [closed]

Are there sentences $\phi$ and $\psi$ in the language of PA and models $\mathcal{M}_\phi$ and $\mathcal{M}_\psi$ of PA such that $\mathcal{M}_\phi\models\phi$ and $\mathcal{M}_\psi\models\psi$, but ...
1
vote
0answers
204 views

Logical and alphabetological variant?

The notion of alphabetical variant is well known, so that a formula $x=x$ is an alphabetical variant of $y=y$ if $x$ and $y$ are distinct variables. One may want to consider the set term $\{x:x \neq ...
1
vote
0answers
148 views

A question on definable categories

One way to define a category set-theoretically might be to give four $\in$-formulas (not sets!) $$\begin{array}{rl} \mathsf{O}(X)&\text{(“$X$ is an object”)}\\ \mathsf{M}(X,Y,z)&\text{(“$z$ ...
15
votes
0answers
368 views

Souslin trees on the first inaccessible cardinal

This may be well-known or simply deducible from the existing theorems, but I didn't find an answer in my set theory books: Is there a model of $ZFC$ in which there are no $\kappa$-Souslin trees where ...
13
votes
3answers
711 views

Where is the end of universe?

In some sense the empty set ($\emptyset$) and the global set of all sets ($G$) are the ends of the universe of mathematical objects. The world which $ZFC$ describes has an end from the bottom and is ...
3
votes
0answers
343 views

Is there a notion of “predicative given the real numbers”?

A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...