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.
5,254
questions
10
votes
1
answer
841
views
What gets to be called a "proper class?"
ZFC has no formal notion of "proper class," but informally, everyone uses the term anyway. $V$, $Ord$, etc are said to be proper classes. Similarly, although in ZFC, one can only take the &...
- 4,847
10
votes
0
answers
238
views
Open problems in complete theories
It is well-known that every complete recursively enumerable first-order theory is decidable. Does that mean that such theories are "trivial", or are there still interesting open problems ...
user507115
2
votes
0
answers
43
views
Chromatic number of the dual hypergraph [duplicate]
Let $H = (V,E)$ be a hypergraph. For $v\in V$ we set $E_v = \{e\in E: v\in E\}$. The dual of $H$ is defined by $H^* =(E, V^*)$ is, where $V^* = \{E_v:v\in V\}$.
If $\kappa>0$ is a cardinal, a map $...
4
votes
2
answers
239
views
Axiomatic strength of the cumulative hierarchy
In the 2021 paper Level Theory Part I: Axiomatizing the Bare Idea of a Cumulative Hierarchy of Sets by Tim Button, a first order theory of the cumulative hierarchy is explored. Initially no axioms ...
- 9,189
12
votes
2
answers
979
views
Proof/Reference to a claim about AC and definable real numbers
I’ve read somewhere on this site (I believe from a JDH comment) that an argument in favor of AC (I believe from Asaf Karagila) is that without AC, there exists a real number which is not definable ...
- 223
13
votes
4
answers
761
views
What is a "general" relation algebra?
I'm trying to understand why (or if) the axioms of relation algebras are "the right ones." For example, we can back up the idea that the group axioms exactly capture the notion of "...
- 20.6k
15
votes
2
answers
804
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is ...
- 229k
3
votes
0
answers
131
views
Is the Tarski–Seidenberg theorem constructively provable?
The Tarski–Seidenberg theorem asserts that the projection of a semialgebraic set is also a semialgebraic set. My question is whether this is provable in constructive mathematics.
First, let me ...
- 6,220
10
votes
0
answers
134
views
Closed sets versus closed sublocales in general topology in constructive math
This question is set in constructive mathematics (without Choice), such as in the internal logic of a topos with natural numbers object, or in IZF.
Short version of the question: if $X$ is a sober ...
- 30.7k
10
votes
1
answer
600
views
Infinitary logics and the axiom of choice
Suppose we want to enhance ZF by allowing for infinitary formulas instead of just first-order ones in our axiom schema of separation and/or replacement. It seems that we don't need much power in our ...
- 4,847
3
votes
0
answers
163
views
Examples of Grothendieck ($\infty$-)topoi which do / do not satisfy the law of excluded middle
I would like to create a big list of Grothendieck topoi (or Grothendieck $\infty$-topoi) which do / do not satisfy the law of excluded middle. That is, let’s list some examples of topoi whose internal ...
-1
votes
0
answers
94
views
Is it consistent to have comprehension with mere restriction of $\in$ to occur with a parameter?
Language: mono-sorted first order logic with equality, with the extra-logical primitive $\in$, and axioms:
Extensionality: as in ZF
Define: $\operatorname {set}(x) \iff \exists y: x \in y$
...
- 10.1k
2
votes
0
answers
40
views
Is the class of strongly Kripke complete normal modal logics closed under sums?
Given an arbitrary set of normal modal logics $\mathcal{L}$, one can define their sum $\bigoplus \mathcal{L}$ (or $\bigoplus_{L \in \mathcal{L}} L$ if you prefer) to be the least normal modal logic ...
- 21
3
votes
1
answer
121
views
Is existence of this function on nonempty sets of Quine atoms consistent with ZF-Regularity?
Working in $\sf ZF \text { - Regularity}$
Let $A $ be the set of all Quine atoms.
Let $f$ be a partial injective function from $\mathcal P(A)\setminus \{\emptyset\}$ to $A$.
Lets postulate the ...
- 10.1k
3
votes
0
answers
124
views
Inevitable consistency strength, take 2
This is an attempt to repair this old question of mine.
Say that a good candidate is a first-order sentence $\varphi$ in a language $\{<,...\}$ containing a distinguished binary relation symbol $&...
- 20.6k