Questions tagged [lo.logic]

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, theories of truth, truth revision, consistency.

Filter by
Sorted by
Tagged with
1 vote
0 answers
49 views

Systems of elementary embeddings

Recently I've been thinking about elementary embeddings, partition cardinals, etc. as part of my never-ending quest for understanding of consistency strength :p I came up with this idea, called I* ...
  • 532
1 vote
0 answers
49 views

Is "strongly unbounded logics are unbounded" equivalent to "no descending sequence of cardinals"?

This question is motivated by Vaananen's paper Generalized quantifiers in models of set theory. Say that a (set-sized, regular) logic $\mathcal{L}$ is unbounded if there are $\mathcal{L}$-sentences $\...
3 votes
2 answers
226 views

Automatically generating combinatorial conjectures

It very often happens that one reduces a problem to a bunch of combinatorial data, and need to sift through this data for patterns, which form conjectures on which to do "real" mathematics. ...
  • 259
1 vote
1 answer
71 views

Are there known general tuple implementations that are 2 types high and withstand absence of extensionality and infinity?

Is there a general $\alpha$-tuple implementation that is of height $2$, that both doesn't require infinity of the naturals, and is at the same time stable under lack of Extensionality? My own try to ...
1 vote
0 answers
67 views

How to express Kunen's inconsistency, Reinhardt and Wholeness axioms, by single sentences?

Working in $\sf NBG, $ can we express the property of a class being set theoretically definable, by a single sentence? Like for example, the following way: $$\operatorname {std}(X) \iff \exists x_1 \...
3 votes
0 answers
76 views

Formal and informal proofs: Is there any "bilingual corpus"?

There are extensive libraries of formalized mathematics like those of Lean, Coq or Isabelle/HOL. What I am interested in is documents of formalized mathematics that closely follow certain informal ...
2 votes
1 answer
97 views

Do the heights of an acute triangle intersect at a single point (in neutral geometry)?

A well-known result of the Euclidean planimetry says that the heights of any triangle have a common point called the orthocentre of the triangle. This result is not true in neutral geometry (i.e., ...
  • 36.5k
18 votes
2 answers
810 views

Statements in differential geometry independent from ZFC

It is well known that some problems in functional analysis and in general topology are independent from ZFC: to name a few, Kaplansky's conjecture, the existence of outer automorphisms of the Calkin ...
4 votes
1 answer
86 views

Are lists in homotopy type theory free $A_\infty$-spaces?

Traditionally in dependent type theory with axiom K or uniqueness of identity proofs, every type $A$ is 0-truncated, and thus the type of lists on $A$, $\mathrm{List}(A)$, is 0-truncated and the free ...
0 votes
1 answer
74 views

Computation over non-reflexivity

The principle of induction over identity families, do not prohibit instances different from refl: x == x but its computation rule is only defined for this instance, ...
2 votes
1 answer
146 views

Axiomatic system made just for playing

The formalization of mathematics is based on axioms and theorems logically concluded from them. This way we construct solid structures to model different areas of the human knowledge: different branch ...
2 votes
0 answers
130 views

Can we have full choice prior to Reinhardt cardinals?

Working in $\sf ZF + Reinhardt \ cardinal$, can we have full choice over all stages $V_{\alpha < \kappa}$ where $\kappa$ is the Reinhardt cardinal, i.e., the critical point of the elementary ...
1 vote
0 answers
46 views

Can this method let choiceless large cardinals be smaller than cardinals compatible with choice?

Recall question "Can we have this sequence where choice fails and returns?" Can that theory be extended with requiring the $\mathcal V_n$'s to fulfill a choiceless large cardinal extension ...
4 votes
1 answer
175 views

Can we have this sequence where choice fails and returns?

Can we have a sequence of transitive sets $\langle\mathcal V_0, \mathcal V_1, \mathcal V_2,...\rangle$, all modeling $\sf ZF$, such that $\mathcal P(V_n) \subset \mathcal V_{n+1}$, and the cardinality ...
3 votes
1 answer
115 views

Intuition behind Kleene's “second algebra” $\mathcal{K}_2$

The “second Kleene algebra” $\mathcal{K}_2$ is defined, e.g. here on nLab, or in section 1.4.3 of van Oosten's book Realizability: an Introduction to its Categorical Side (2008), or as example 3.4 of ...
  • 24.5k
8 votes
3 answers
926 views

Dedekind-Peano axioms, but numbers have at most one successor

One can consider a variant of the Dedekind-Peano axioms in which one replaces the assumption that every number has exactly one successor by the assumption that every number has at most one successor, ...
  • 17.9k
22 votes
8 answers
2k views

Simpler proofs using the axiom of choice [duplicate]

I am looking for examples of results which may be proven without resorting to the axiom of choice/Zorn lemma/transfinite induction but whose proof is quite simplified by the use of the axiom. For ...
1 vote
0 answers
172 views

Harvey Friedman: The expanding mind

In reference 1, Friedman writes: I discuss my efforts concerning 3 crucial issues in the foundations of mathematics that are deeply connected with the great work of Kurt Gödel. [...] B. Are there ...
  • 1,661
2 votes
0 answers
186 views

Can we interpret Reinhardt cardinals this way?

To the language of set theory add a primitive unary predicate $\operatorname {Universe}$ and a primitive total unary function $j$. Add all axioms of $\sf ZF$ in the language of this theory, i.e. the ...
5 votes
0 answers
134 views

Moduli all the way down

The notion of modulus of continuity is well-known from constructive mathematics, reverse mathematics, and computability theory. Intuitively, such a modulus is a function that returns the '$\delta>...
  • 2,629
-1 votes
0 answers
77 views

Reinhardt cardinals in Paraconsistent Set Theory

The current developments in paraconsistent set theory have resolved Russell's paradox and maintained sufficient consistency strength, which leads to the following interesting questions. Is there a ...
6 votes
0 answers
121 views

Can we have a 'universal class' for elementary embeddings $j\colon V\to V$

Work over $\mathsf{GB}$, Gödel-Bernays set theory (without choice). My question is the following: Question. Is the following statement consistent with $\mathsf{GB}$? There is a universal class for ...
  • 1,900
1 vote
2 answers
223 views

Can we iteratively reflect on self elementary embeddable stages of the cumulative hierarchy?

Is it possible to iterate elementary embeddability and reflect on those stages that are elementary embeddable to themselves? The following is a formal capture of that idea: To the language of $\sf ZF$...
7 votes
1 answer
179 views

Does $\mathit{Aut}(\mathbb{R};+)$ have a copy in $L(\mathbb{R})$ granting large cardinals?

Throughout, work in $\mathsf{ZFC}$ + large cardinals (let's say a proper class of Woodin limits of Woodins but I'm happy to go higher if that would help). Let $\mathcal{R}=(\mathbb{R};+)$ be the ...
8 votes
0 answers
253 views

What is the relationship (if any) between constructivism, finitism and predicativism?

The terms “constructivism”, “finitism” and “predicativism” refer to ideas / currents in the philosophy of mathematics (or loosely defined conditions on a system of logic) that I think I understand ...
  • 24.5k
0 votes
0 answers
153 views

Can acyclicity manage to elude Cantor's theorem?

A formula $\phi$ is acyclic if we can associate with its open expansion an non-directed acyclic graph, whose nodes are the terms of the formula and the edges are: if $\text{“}{\mathcal F}(v_1,\ldots,...
8 votes
0 answers
74 views

Is the hypotenuse operation associative in every Tarski plane?

By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
  • 36.5k
7 votes
1 answer
223 views

Complexity of infinitary satisfiability, part 2

This question is a follow-up to this one, which was almost entirely answered by Farmer S. Throughout, we work in $\mathsf{ZFC+V=L}$. Given a "pre-admissible" (= admissible or limit of ...
5 votes
0 answers
88 views

Is an equilateral triangle constructible in a Tarski plane?

By a Tarski space I understand a mathematical structure $(X,\mathsf B,\equiv)$ consisting of set $X$, a betweenness relation $\mathsf B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\...
  • 36.5k
8 votes
1 answer
840 views

Is there a form of choice that can elude Kunen's inconsistency theorem?

When it is said that Kunen inconsistency theorem proves that given $\sf ZFC$ no elementary embedding can exist from the universe to itself. Most references quote full choice in stating that result, ...
6 votes
0 answers
132 views

Does every Tarski plane embed into a 3-dimensional Tarski space?

By a Tarski space I understand a mathematical structure $(X,B,\equiv)$ consisting of set $X$, a betweenness relation $B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\times X^2$ ...
  • 36.5k
3 votes
0 answers
63 views

Algebraic logical structure

Let $M=(W,R)$ be a Kripke frame, $A=(f_1,...,f_m)$ is a tuple of operations $f_i:W^{n_i}\to W$, and $\Phi=(\varphi_1,...,\varphi_m )$ is a tuple of first-order logic formulas in vocabulary $\sigma=\{=...
  • 107
8 votes
2 answers
827 views

What theories are larger than the real closed field but still decidable?

It's well known that sentences about the real closed field can be decided by algorithm and the complexity of this is about $d^{2^{O(n)}}$ where $d$ is the product of the degrees of polynomials in the ...
11 votes
1 answer
289 views

What is the "iterated definability" limit of first-order logic?

Roughly speaking, given a set-sized logic $\mathcal{L}$ let $\mathcal{L}'$ be gotten by adding to $\mathcal{L}$ the ability to quantify over $\mathcal{L}$-definable relations. (The details are a bit ...
2 votes
1 answer
129 views

Computability of fillability of unit cube in $\mathbb{R}^n$ by $k$ $\varepsilon$-balls

Let $\mathbb{N}$ denote the set of positive integers. We define a relation $R \subseteq \mathbb{N}^4$ in the following way: $(p,q,n,s)\in R$ if and only if there is $S\subseteq [0,1]^n$ with $|S| = s$...
0 votes
1 answer
110 views

Is a right triangle with the given cathetus and the opposite angle constructible in the absolute plane?

Question. Is it possible to construct a right triangle with a given cathetus $a$ and a given opposite angle $\alpha$ using only compass and ruler in the absolute geometry (so without the axiom of ...
  • 36.5k
4 votes
1 answer
181 views

Is ordinal definability in terms of stages of cumulative size hierarchy equivalent to the usual one?

Working in $\sf ZF$ Define: $W_0 = \emptyset \\ W_{\alpha+1} = H_{\leq |W_\alpha|} =\{x \mid \forall y: y \in \operatorname {trcl} (\{x\}) \ |y| \leq |W_\alpha| \} \\ W_\lambda= \bigcup W_{\alpha < ...
17 votes
3 answers
822 views

Minimum transitive models and V=L

Is there a c.e. theory $T⊢\text{ZFC}$ in the language of set theory such that the minimum transitive model of $T$ exists but does not satisfy $V=L$? You may assume that ZFC has transitive models. ...
3 votes
0 answers
168 views

Which arxiv-category should computability theory be submitted to?

There are two categories on the arXiv that seem like a potential fit for computability research to me, although none of them explicitly lists it in the description. These would be: cs.LO Covers all ...
  • 3,864
1 vote
0 answers
36 views

Is stratified sorted rendering of naive set theory equivalent to tangled type theory?

I think the most important point in stratification is to have what may be called a fixed membership type distance per variable. What I mean is that if a variable $x_i$ occurs in a stratified formula $\...
5 votes
2 answers
334 views

Replacement axiom and the von Neumann hierarchy

Within ZFC, the von Neumann hierarchy consists of sets $V_\alpha$ indexed by ordinals, subject to the following conditions: $V_0=\varnothing$. $V_{\alpha+1}=\mathcal P(V_\alpha)$. $V_\lambda=\bigcup_{...
  • 247
17 votes
5 answers
2k views

What are some interesting applications/corollaries of Kleene's Recursion theorem?

Lately I became very interested in the theory of computability and a fundamental early result you learn is the Recursion Theorem also known as the Fixed point theorem. At first sight you can see it's ...
  • 505
3 votes
1 answer
223 views

If we add stratified\acyclic replacement to the wholeness axiom, would that increase its consistency strength?

If we add to the wholeness axiom, the axiom of stratified\acyclic replacement, what would be the consistency state and strength of the resulting theory? The wholeness axiom $\sf WA$, introduced by ...
3 votes
1 answer
136 views

If a theory speaks of sets that cannot be forced to be parameter free definable, then does this entail a large cardinal property?

If we say that an effectively generated first order theory $\sf T$ extends $\sf ZF$, such that every countable model of $\sf T$ doesn't have a class forcing extension that is pointwise definable. ...
7 votes
1 answer
304 views

Can we have mutual elementary embeddability between distinct transitive sets?

Is it consistent with $\sf ZFC$ to have mutual elementary embeddability between distinct transitive sets? Formally, is the following theory consistent? $${\sf ZFC} + \exists M \exists N: M,N \text { ...
1 vote
1 answer
131 views

Is there a model of each of the following kinds of theories in the first transitive model of ZFC?

The question of whether the minimal transitive model $M$ of $\sf ZFC$ have a model of each consistent extension $\sf T$ of $\sf ZF$, is answered to the negative, basically because $M$ is countable and ...
10 votes
2 answers
680 views

Does every consistent extension of ZF have a model in the minimal transitive model of ZFC?

Suppose there exists a transitive model of $\sf ZFC$. Is it the case that every consistent theory that extends $\sf ZF$ must have a model that is an element of the minimal transitive model of $\sf ZFC$...
1 vote
1 answer
74 views

Are externally pointwise definable models of ZFC subject to the same limitations of the internally pointwise definable ones?

By pointwise definable models, it's meant that every element of those models is definable after a formula in a parameter free manner, but that defining formula is in the language of that model, i.e., ...
6 votes
1 answer
270 views

Which model is the minimal pointwise definable model of $\sf ZFC$?

Is the minimal transitive model of $\sf ZFC$ pointwise definable? If not, then what is the minimal pointwise definable model of $\sf ZFC$? Can we define that using Hamkins result for existence of ...
9 votes
0 answers
213 views

Feferman's universes for proof assistants?

This question was prompted by a discussion from another MO question about the consistency of ZFC. There are some mathematicians who are comfortable with ZFC but uneasy with large cardinals. For them,...
  • 69.6k

1
2 3 4 5
94