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
0answers
73 views

How can I prove: If A is a subset of C and B is a subset of D, then the union of A and B is a subset of the union of C and D? [on hold]

How could I write a proof for the above statement, considering I'm studyng the first Enginnering math's course? (in other words, my math level is pretty basic) Thanks in advance
-1
votes
0answers
51 views

Fixed point combinator and functions with no fixed point [on hold]

In lambda calculus the fixed point combinator is defined as: $$Y=\lambda f.(\lambda x.f (xx))(\lambda x.f (xx)) $$ It is very easy to see how $Yg =g(Yg)$ for any $g$ by using $\beta$-reduction. ...
6
votes
1answer
208 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
207 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
318 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
301 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
214 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
254 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
321 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
397 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 ...
2
votes
0answers
92 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
569 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
511 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
245 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
138 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
133 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 ...
8
votes
0answers
144 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
227 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
100 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
472 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
149 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
177 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 ...
10
votes
0answers
210 views

Is there a “hereditary” construction for $L$?

Recall that $L$, Godel's constructible universe is constructed by defining the following hierarchy: $L_0=\varnothing$, for a limit ordinal $\delta$, $L_\delta=\bigcup_{\alpha<\delta}L_\alpha$, and ...
4
votes
0answers
138 views

Examples of unproven but likely true existential sentence (in the sense of incompleteness)

Some examples of universal statements that are unproven but likely true include the Riemann hypothesis (all non-trivial zeros of the zeta function have real part 1/2) and the Goldbach conjecture (all ...
0
votes
1answer
122 views

Definability of arithmetic functions and relations

Motivation: Many "weak" arithmetic functions and/or relations ("relations" for short) are equivalent with relations explicitly definable by relations which were recursively defined by them beforehand ...
10
votes
0answers
280 views

Ideas behind Gitik's solution of PCF conjecture

Recently Moti Gitik has refuted Shelah's PCF conjecture (see Short extenders forcings II ) by proving the following theorem: Theorem. Assuming the consistency of infinitely many strong cardinals, one ...
4
votes
4answers
943 views

How short can we state the Axiom of Choice?

How short can we state a principle which is equivalent with the Axiom of Choice under $ZF$? The principle should be a sentence in the language of set theory with only $\in$ and$=$ as extralogical ...
7
votes
1answer
257 views

Saturated Ultrapowers

I posted it on MSE and didn't receive any comments or answers, so I thought I would post it here. (See http://math.stackexchange.com/questions/895549/keisler-order-saturated-ultrapowers) Keisler's ...
8
votes
2answers
314 views

Ultracoproducts and Cartesian products

Let $X$ be a metrizable compact topological space, let $\mathcal U$ be an ultrafilter, and denote by $X^{\mathcal U}$ the ultracopower of $X$ with respect to $\mathcal U$. As a C$^*$-algebraist, I ...
4
votes
2answers
197 views

What is the status of the extreme value theorem in forms of constructive mathematics, such as Smooth Infinitesimal Analysis?

In certain intuitionistic frameworks the extreme value theorem cannot be proved. Depending on the exact framework, counterexamples can be constructed as well; see for example pp. 294-295 in ...
4
votes
2answers
638 views

Salvaging Leibnizian formalism?

Can one justify Leibniz's formalism in a suitable algebraic or topological context? We have published some papers recently where we argue that Leibniz's formalism for the calculus wasn't ...
7
votes
1answer
237 views

Inaccessible becomes successor of singular

Is it possible, starting from any large cardinal assumption, to find a countably closed forcing $\mathbb{P}$ such that for some inaccessible $\kappa$, $\Vdash_\mathbb{P} "\kappa = \lambda^+$ and ...
1
vote
1answer
302 views

Is there any current development of a first order formalization of metamathematics?

I hope that this post isn't off topic, but I already asked math.stackexchange about first order formalizations of first order logic. There are provability logics and extensions in modal logic's that ...
4
votes
2answers
151 views

Question about higher inductive types and computational rules

I have been trying to make my way through the homotopy type theory book, slowly but surely, and I just finished reading this introductory series of 3 articles on hott on ScienceForAll. ...
-4
votes
1answer
155 views

Universal quantifier in Russell's Theory of descriptions - Who is the UNIVERSE? [closed]

To moderators: Please don't delete or migrate this thread: It's by no means PURE PHILOSOPHICAL, but mostly a mathematical logic question! In Russell's 1905 paper "on denoting" in which he introduces ...
1
vote
0answers
51 views

LTL - Büchi-automaton Translation [closed]

I need some help in Generalized Büchi automaton .. I do understand the translation of a LTL-formula ϕ into Generalized Büchi automaton A= (Q, Δ, I, F), with F= {F1,...,Fn} My problem is F .. I know ...
6
votes
1answer
168 views

continuum many mutually generic filters

Given a countable model $M$ of set theory and an atomless, separative partial order $\mathbb{P} \in M$, can we construct (in the real universe) $2^\omega$ many pairwise mutually $\mathbb{P}$-generic ...
5
votes
0answers
105 views

A question about ordinal definable sets of real numbers revisited [duplicate]

Citing (almost) A question about ordinal definable real numbers If ZFC (Zermelo-Fraenkel set theory with the Axiom of Choice) is consistent, does it remain consistent when the following statement is ...
6
votes
0answers
101 views

Can $Ded(\kappa)$ be a supremum?

Definition If there is a dense linear order w/o endpoints of size $\lambda$ with a dense subset of size $\kappa$ then write $D(\kappa,\lambda)$. $Ded(\kappa)=\sup_\lambda \{D(\kappa,\lambda)\}$. It ...
2
votes
1answer
150 views

The word problem of the free left distributive algebra on one generator

A left distributive algebra is a set $A$ together with a binary operation, $\cdot$, satisfying $a\cdot(b\cdot c)=(a\cdot b)\cdot(a\cdot c)$. One important example of left distributive algebras arises ...
8
votes
1answer
312 views

The (un)decidability of Robinson-Arithmetic-without-Multiplication?

I asked this over at math.stackexchange, and though a number of people were interested enough to vote up the question, I didn't get an answer -- which makes me wonder whether it isn't quite so ...
7
votes
1answer
248 views

The definition of < in Robinson's Q

I recently had to explain how the basic axioms in Simpson's Subsystems of Second Order Arithmetic were interpretable in Robinson's Q. Most of the axioms are actually the same, except that Simpson ...
2
votes
1answer
142 views

References for the Keisler Order

Are there any good/modern references on the Keisler order. I have been reading Keisler's original paper, "Ultraproducts which are not Saturated", which introduces the order. However it is somewhat ...
4
votes
0answers
118 views

The (global) theory of Borel equivalence relations

What do we know about the complexity of the theory of Borel equivalence relations, with the Borel reducibility order $\leq_B$? That is, let $\mathcal{B}$ be the set of all Borel equivalence ...
4
votes
1answer
316 views

Set-theoretic tautologies

Let us consider unquantifed formulas of a set theory (for example, NBG), more precisely, the formulas, constructed from variables and the constants $\emptyset, V$ (the empty set and the class of all ...
0
votes
1answer
144 views

Refutation of $A \land \lnot\lnot\lnot A$ by resolution [closed]

$ A \land \lnot\lnot\lnot A $ this is a very simple example. Resolution is refutation complete. So it should be able to refute this formula. However, I don't see how would it do that without using ...
3
votes
1answer
85 views

Is quasivariety generated by all perfect graphs finitely axiomatizable?

Fix logic $L$ with equality and a binary relation symbol $E$. The class of graphs can be identified with the class of models of the universal first-order Horn $L$-sentences $\forall x,y\; E(x,y) ...
3
votes
1answer
125 views

Countable model theory for $\omega$-stable theories?

This is a bit of a fishing expedition, because I'm not sure what I'm looking for. Very vaguely stated, here's the driving question: What conditions on an $\omega$-stable theory make the class of ...
4
votes
1answer
254 views

How do we know if Vaught's Conjecture is Absolute?

Please note that this might be some confusion on my part about the work surrounding Vaught's conjecture. First of all, Vaught Conjecture states that if a first-order complete theory $T$ in a ...
4
votes
1answer
265 views

Question about “Coding the universe”

The following is a result which I know as a weak form of Jensen's coding lemma$^*$ (first published in the book "Coding the universe"; also see http://www.jstor.org/stable/2273986): For any class ...