**2.994 lo.logic questions.**

The extensionality axiom states that sets are the same if they contain the same elements, or conversely, sets are different if there is an element of one that is not an element of the other. This ...

One of the very common notations for syntactic substitution is $[\ /\ ]$.
However, there seems to be an inconsistency in the literature about its usage.
Many write $[t/x]$ for "substitute $t$ for $x$...

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...

Below, I've focused on PA when lots of other theories would do. If replacing PA with a different theory leads to a more answerable question, feel free to do so.
The standard system of a nonstandard ...

First note that there exists a natural measure $\mu$ on $P(\omega \times \omega)$, inherited from the Lebesgue measure on the reals (by identifying the reals with $P(\omega)$ and $\omega$ with $\omega ...

Harvey Friedman is well known for investigating concrete mathematical statements that requires strong assumptions, i.e. those that can only be interpreted in a strong extension of $\text{ZF(C)}$. My ...

In Realizability: A Historical Essay [Jaap van Oosten, 2002], it is said that recursive realizability and HA provability do not concur, because although every HA provable closed formula is realizable, ...

The following is a theory that extends mono-sorted first order logic with identity and membership, with the following axioms:
Extensionality: Classes having the same members are identical
$\forall x,...

Let $\lambda\geq \omega_2$ be a regular cardinal. The weak reflection principle for $[\lambda]^\omega$ ($WRP([\lambda]^\omega)$) asserts that for any stationary $S\subset [\lambda]^\omega$ there ...

Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? ; Completion of ZFC ; Complete resolutions of GCH; How far wrong could the Continuum Hypothesis be?; When was ...

The good intuitive reasons that the Axiom of Choice (AC) for arbitrary sets-- that a function f with f(i) in S(i) for each i in {i}, for any non-empty sets {i} and all S(i), exists-- doesn't follow ...

It is just my curiosity about this question where we have an infinite game and (according to the answers) winning strategies for both players. I am familiar with terminating games only, and I am ...

Let $M$ be a nonstandard model of $PA$.
Q1. Is there any way to get a submodel $N\subset M$ such that $N\models Th_{\Pi_2}(PA)$, but $N\not\models PA$?
Q2. Especially, what combinatorial ...

(Prompted by reflection on this old answer, and its suggestion of the “harmlessness” of the axiom of regularity.)
In ZFC, one may justify the axiom of foundation (AF, aka the axiom of regularity) as ...

I have been thinking the following problem proposed by my friends for a long time.
Let $\mathcal{L}$ be the first-order language of theory of rings and let $K$ be the class of algebraic number ...

Are there r.e. sets $B >_T 0$ and $C >_T 0$, $C \not\geq_T B$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$. The explanation for the title is because one can ...

This question follows up on an issue arising in Peter LeFanu
Lumsdaine's nice question: Does foundation/regularity have any
categorical/structural consequences, in
ZF?
Let me mention first that my ...

Does the fact that, assuming the consistency of $ZFC$, no proof that the consistency of "$ZFC$ implies the consistency of '$ZFC$ + There exists a weakly inaccessible cardinal'" can be formulated in $...

System U is an inconsistent PTS in that one has a term of type $\bot = \forall p\colon \ast \ldotp p$, and such a term is explicitly constructed in Hurkens' A Simplification of Girard's Paradox.
One-...

The search for a neat Theory of Everything (ToE) which unifies the entire set of fundamental forces of the universe (as well as the rules which govern dark energy, dark matter and anti-matter realms) ...

As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...

Today I started reading Maddy's Believing the axioms. As I knew beforehand, it includes some discussion of ZFC axioms. However, I really hoped for a more extensive discussion of axiom of foundation/...

(1) Some typical inclompleteness proofs use a kind of fixed point argument - for certain $\Phi$ you find a $\varphi$ with $\Phi(\mathrm{code}(\varphi))\leftrightarrow\varphi$.
(2) Some independence ...

Is there a known result to the effect that it cannot be the case that for some natural $n$, there is a formula of length $n$ such that all cardinals can be defined by a formula whose length is shorter ...

I am teaching the proof-writing class (for the 3rd time) in the Fall and plan to buck the party line and use a different text than the default Bond and Keane. My parameters are as follows:
Logic, ...

Let $\mathcal{E}$ be a topos, and let $\top\colon1\to\Omega$ be its subobject classifier. We refer to global elements $P\colon 1\to\Omega$ as propositions; they form a poset, denoted $(|\Omega|,\leq)$....

What is the shortest definition of "$x$ is a finite class" that can be formulated in the class theory presented at:
Is it possible to derive the rules of set theory as transfers from the pure finite ...

Informally the idea of this question is about whether the rules of set theory can be derived as a transfer of some rules from the hereditarily finite set realm, and whether this transfer principle ...

Let $Z_2$ and $Z_3$ be second and third order arithmetics respectively.
In $Z_2$'s language, $\text{AD}$ (the axiom of determinacy) and $\text{PD}$ (projective determinacy) are stated the same way (...

Jeremy Avigad and Erich Reck claim that one factor leading to abstract mathematics in the late 19th century (as opposed to concrete mathematics or hard analysis) was the use of more abstract notions ...

I included this footnote in a paper in which I mentioned that the number of partitions of the empty set is 1 (every member of any partition is a non-empty set, and of course every member of the empty ...

Recently two formerly unknown articles by Errett Bishop (1928-1983) were posted online by Martín Escardó. One is entitled "A general language", deals with constructive type theory, and ...

I am preparing to teach a short course on "applied model theory" at UGA this summer. To draw people in, I am looking to create a BIG LIST of results in mathematics that have nice proofs using model ...

KG (the Kleene Getaway) is the name I improvised (in my answer to a question on MO on constructive Perron-Frobenius) for a constructive principle which enables the direct constructive use of a ...

For the purpose of this post, I will say that the Gale-Stewart game is the infinite two-player game of perfect information where players I and II alternate playing natural numbers, with I going first. ...

The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...

Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...

In their 1985 paper "Arithmetic Transfinite Induction and Recursive Well-Orderings", Friedman and Ščedrov prove that the theory $\mathbf{ZFI}$ is conservative over $\mathbf{HA}^*$ (see here, Theorem ...

We start with $ZF$.
The axiom of countable choice, $AC_\omega$, says that any set product of nonempty sets with a countable index set is nonempty. For any $ZF$-definable set $A$, we should be able ...

Classes are often informally thought of as being "larger" than sets. Usually, the notion of "larger" is formalized via an injection: $B$ is "at least as large" as $A$ iff there is an injection from $A$...

Ten years ago, when I studied in university, I had no idea about definable numbers, but I came to this concept myself. My thoughts were as follows:
All numbers are divided into two classes: those ...

It seems that Moti Gitik has recently refuted some variants of Shelah's weak hypothesis. For this see the title and abstract of his talk at the Set Theory, Model Theory and Applications conference.
I ...

For any set $X$ we set $[X]^2 = \big\{\{x,y\}: x,y \in X, x\neq y\big\}$.
Consider the following statement (S):
Statement (S) : Let $G=(V,E)$ be a finite undirected graph and $V_1, \ldots, V_n\...

Suppose $0^\sharp$ exists, and let $\langle \alpha_i : i \in \text{Ord}\rangle$ be the Silver indiscernibles for $L$. Let $j : L \to L$ be the embedding generated by mapping $\alpha_n$ to $\alpha_{n+...

This question is for example: from the godel imcomplete theorem there is Turing machine M, M(n)=1 for all n, but we cannot proved or disprove it in ZFC,i.e., it is independant of ZFC, therefore from ...

Let $T$ be a given turing machine. We say that $T$ decides $\operatorname{Con}(PA)$ if $PA + \operatorname{Con}(PA) \vdash T \text { accepts}$ and $PA + \lnot \operatorname{Con}(PA) \vdash T \text { ...

1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...

While studying topos theory I was wondering if there is something like internal logic of an abelian category. Aparently the answer is yes
(by 7º slide in https://www.mimuw.edu.pl/~gael/xxi/files/...

Question. Does $\text{GCH}$ imply the existence of a non-special $\aleph_2$-Aronszajn tree ?
Remark 1. By a result of Jensen, it is consistent that $\text{GCH}$ holds and all $\aleph_1$-Aronszajn ...

- set-theory
- model-theory
- reference-request
- computability-theory
- forcing
- large-cardinals
- proof-theory
- ct.category-theory
- axiom-of-choice
- descriptive-set-theory
- mathematical-philosophy
- peano-arithmetic
- foundations
- nt.number-theory
- computational-complexity
- soft-question
- reverse-math
- computer-science
- ho.history-overview
- constructive-mathematics
- gr.group-theory
- co.combinatorics
- gn.general-topology
- topos-theory
- modal-logic