25 votes
Accepted

Uncountably many subsets of the natural numbers with certain natural density condition

Amazingly, the answer to the main question is yes. For each $n$ let $I_n = [2^{2^n}, 2^{2^{n+1}})$. Then let $\mathcal{C}$ be an uncountable family of infinite subsets of $\mathbb{N}$ any two of which ...
user avatar
  • 38.1k
16 votes

Ultrafilter subtraction and "zero"

For question 1, both your guesses are correct. To see this, it's helpful to reformulate the way you're thinking about the subtraction operator on $\beta \mathbb Z$. Beginning with subtraction on $\...
user avatar
13 votes

Is the theory of a partial order bi-interpretable with the theory of a pre-order?

They are not one dimensional bi-interpretable. The pre-order on $\{a,b,c,d\}$ given by $a\equiv b$ and $c\equiv d$ (and $a, b$ not related to $c, d$) is homogeneous in the sense that for any ...
user avatar
13 votes
Accepted

Is the equational theory of this "orthocentrish" algebra finitely based?

This algebra is finitely based. In fact, if you choose any bijection from $\{a,b,c,d\}$ to $\mathbb Z_2\times \mathbb Z_2$, then you can transport the operation $F(x,y,z)$ to $\mathbb Z_2\times \...
user avatar
9 votes
Accepted

Difference between provability and the existence of a proof?

First note this isn't a constructive logic, so it's wrong to think of "$X$" as "there is a proof of $X$". (Even in constructive logic I find that dubious.) Second note that if $X$ ...
user avatar
  • 117k
9 votes
Accepted

Can we write Tangled Type Theory without reference to type sequences?

No it is not the same. The type sequences are absolutely needed, in some form. --Randall Holmes (author of the theory in question) The theory you describe is provably inconsistent. The formula has to ...
user avatar
7 votes

Can we write Tangled Type Theory without reference to type sequences?

As Randall Holmes’ answer already says, your comprehension scheme is more general than the comprehension scheme of TTT. To illustrate this with a concrete example: Your scheme gives comprehesion for ...
user avatar
7 votes
Accepted

Can there be no complexity bound on the definable elementary $V\rightarrow M$?

Yes, this is possible. If there is a proper class of measurable cardinals and $V = \text{HOD}$, then any class of ordinals $A$ is definably encoded by the iterated ultrapower $j_A : V\to M$ that hits ...
user avatar
5 votes
Accepted

Is there a maximal fragment of FOL with "no negation at all?"

There is a simple characterization that $\def\LL{\mathcal L}\LL$ is nowhere negative iff all $\LL$-theories have the disjunction property: Proposition. For any $\LL\subseteq\mathrm{FO}$, the ...
user avatar
4 votes
Accepted

Is this theory equivalent to Tangled Type Theory?

It is not. It is very important, very awful, and quite intended that the membership relation between the same two types is the same in different sequences of types.
user avatar
3 votes
Accepted

An extension of Woodin's star axiom

This principle is inconsistent, even if we just look at $(H_{\omega_2};\in)$. This is because - for example - the continuum hypothesis is expressible as a sentence in this structure ("There is an ...
user avatar
2 votes
Accepted

About external automorphism on non-well founded model of Finite ZF?

The answer is no, there cannot be even a single instance of this for an automorphism $j:M\to M$. The reason is that if $j(V_{n+1})=V_n$ for some (possibly nonstandard $n$), then we would have $j(n+1)=...
user avatar
2 votes

Is all ordinary mathematics contained in high school mathematics?

In 2011, the paper "An Upper Bound on Reidemeister Moves" gave an upper bound for knot manipulation: given two equivalent knots with $<n$ crossings, an upper bound on the number of ...
user avatar
  • 439
2 votes
Accepted

Ordering patterns of projecta by least witness

$<_\rho$ is a wellorder essentially by definition. The ordertype is $\omega^{\omega}$ (ordinal exponentiation of course). In fact $s<_\rho t$ iff either $\mathrm{lh}(s)<\mathrm{lh}(t)$, or $\...
user avatar
  • 5,174
1 vote
Accepted

Can $\mathsf{TNT}$ be modeled in non-well-founded models of $\mathsf{ZF}$?

Per comments, the above conditions might not be enough to ensure the result of interpreting $\sf TNT$, however, the following line would work to answer the first quetion: Suppose we work in $\sf ZF−...
user avatar
1 vote
Accepted

Alternative proof of Tennenbaum's theorem

It turns out that the same proof idea can be found in the fifth edition of Computability and Logic by Boolos, Burgess and Jeffrey:
user avatar
  • 201

Only top scored, non community-wiki answers of a minimum length are eligible