New answers tagged

3

At the request of the OP, I’m writing a lengthy nonanswer showing that there are short proofs of inconsistency of similar theories where the “big number” is given by a term in the usual language of arithmetic $L_{PA}=\{0,S,+,\cdot\}$, possibly expanded by the exponential function. The argument does not work for languages including faster growing functions ...


1

Just in case anyone else is a mere mortal and takes a moment to understand Slaman's answer here is a more spelled out version of his argument. I'll just do the capping side as it's the same argument for cupping The construction of an r.e. minimal pair and an incompatible pair of r.e. degrees whose join is $0'$ is uniform. Therefore, there are hops $H_e$ ...


3

You could look at the Jockusch and Shore papers on pseudo jump operators. They showed that for every $e$ there is an r.e. $A$ such that $A+W^A_e$ is Turing equivalent to $0’$. So $0’$ can have the behaviors that you mentioned relative to r.e. sets.


6

Your setup doesn't provide any complexity restrictions on determining whether a formula is an axiom or not, beyond demanding that this is computable. Thus, you won't be able to limit the complexity of proof verification either. Determining the axioms is going to be the only issue, though. Any reasonable proof system will make verifiying proofs a polynomial-...


1

I’m not familiar with this paper, but what is wrong with just writing out the first-order definitions of the inner functions? That is, $f(a)=g(\mu x_{x<l(a)}f^x(f^a(h(a))))$ becomes $$\exists x\,(f(a)=g(x)\land\phi(a,x)),$$ where $$\begin{align*} \phi(a,x)&\iff(x<l(a)\land\psi(a,x,0)\land\forall y\,(y<x\to\neg\psi(a,y,0)))\\ &\qquad\quad\lor(...


1

The answer is no. Every properly n-REA set for n < 3 (I believe Peter Cholak and I have shown this fails at 3 but could always fall apart in write-up) can be extended to a properly n+1 REA set by adding a relative r.e. set. Now apply this result to a low r.e. set. You can find that result in a paper by Peter Cholak and Peter Hinman but the result for n=...


1

The full rank factorization of the 3x2 zero matrix is the product of a 3x0 matrix times a 0x2 matrix. There exist empty matrices with n>0 rows and 0 column. The 0x0 empty matrix is the only non nonsingular zero matrix.


2

Maybe it is not serious, but then in a sense none of the examples in this thread are. Jordan decomposition represents every operator on a finite-dimensional space in a unique way as $S+N$ where $S$ is a diagonalizable operator, $N$ is a nilpotent operator, and $SN=NS$. The Jordan decomposition of the zero operator is $0+0$. It thus is the only operator which ...


4

Here's a topological way to understand stability of a formula. Depending on your background, you might find it intuitive. Given a formula $\varphi(\bar x,\bar y)$, a model $M$ and a tuple $\bar b$ in $M$ of the same length as $\bar y$, you can define a formula $f_{\varphi,\bar b}\colon M\to \{0,1\}$ by putting $f_{\varphi,\bar b}(\bar a)=1$ if and only if $\...


6

If you are interested in homogeneous structures, then you might also be interested in the following (equivalent) formulation, using the notion of a half-graph: Let $V=\{v_1,v_2,\ldots, v_n\}$ be the vertex set of a graph $G=(V,E)$. We say that $G$ is a half-graph if $v_i\mathrel{E}v_j$ iff $i\leq j$. (Intuitively, this means just that the graph of $E$ as a ...


19

I am going to explain some motivation by relating this definition to stability to other definitions, and discussing some examples. For simplicity I am going to assume we are working in a countable language. An alternate definition of stability, for a complete theory $T$ is as follows. Definition. $T$ is stable if there is some infinite cardinal $\lambda$ ...


6

Let's first observe that any stable countable homogeneous structure in a finite relational language is $\aleph_0$-categorical and $\aleph_0$-stable. This is explained in A survey of homogeneous structures by Macpherson: $\aleph_0$-categoricity is Corollary 3.1.3 on p. 17, and $\aleph_0$-stability is in the paragraph just before Example 3.3.2 on p. 22. Then ...


10

Your intuition is finitary, and therefore wrong. Compare, for example, the two sequences: $\alpha_n=n$, and $\beta_n=2^n$. It is easy to see that $\alpha_n<\beta_n$ for all $n$. We even know from elementary calculus that the rate of change between them is growing very fast as well, so there is no possible way for $\alpha_n$ to be equal to $\beta_n$. ...


5

Without further requirements on $\tau$, this is trivial. Let $T$ be any first-order theory and let $\top$ be any tautology. Define $\tau(\phi)= \top$. If you want $\tau$ to be injective, then let $T$ be any first-order theory in the language of $TA$ and define $\tau(\phi)=\top\vee\phi$. If you also want equivalence, then take $T$ to be any first-order theory ...


0

In contrast to, for example, Lagrange's theorem: it contains the notion of the "order" of a group, which I guess cannot be defined in terms of morphisms and composition. Perhaps the "order" cannot be defined, but "order divisible by a prime p" can be defined by: there is a non-trivial map from the cyclic group of order p. The ...


8

Here's an argument that doesn't use ordinals, as an alternative to the nice proof described by Andrés and Andreas. Take $F: P(S) \to S$ satisfying your hypothesis. Define a function $\Phi: P(S) \to P(S)$ by $$ \Phi(X) = \{F(Y): Y \subseteq X\}. $$ Then $\Phi$ is an order-preserving map from the complete lattice $P(S)$ to itself, so there is a least $X \in P(...


1

The answer is YES! Let $\mathcal H_\alpha$ stand for the set of all sets hereditarily strictly subnumerous to ordinal $\alpha$. Now for any set $x$, $\mathcal H^x_{min}$ is meant to be the minimal $\mathcal H_\alpha$ such that there exists an iterative power of it that is supernumerous to $x$. Formally: Define: $\mathcal H^x_{min} = min \ \mathcal H_\alpha: \...


4

Just as the least fixed point is the intersection of all the sets $H$ such that $\forall x\,(A(x,H)\to H(x))$, so (dually) the greatest fixed point is the union of all the sets $K$ such that $\forall x\,(K(x)\to A(x,K))$. Alternatively, one can use duality to obtain the greatest fixed point of $A(x,G)$ as the complement of the least fixed point of $\neg A(x,\...


4

Note that $M=\bigcap_{\alpha}M_\alpha$ is just the $\mathrm{OR}^{\mathrm{th}}$ iterate $M_{\mathrm{OR}}$ cut off at height $\mathrm{OR}$, so we have for example $V_\kappa\preceq V_\lambda\preceq M$ where $\kappa=\mathrm{crit}(j)$ and $\lambda=\kappa_\omega(j)$, where $\kappa_0(j)=\mathrm{crit}(j)$ and $\kappa_{n+1}(j)=j(\kappa_n(j))$ and $\kappa_\omega(j)=\...


16

First-order logic does not provide for definitions of functions by recursion. For example, the transitive closure of a binary relation $R$, though definable from $R$ by recursion, is not in general first-order definable from $R$. Peano Arithmetic, though formulated in first-order logic, does have enough axioms to support some definitions by recursion. ...


13

No, this is not consistent. Todorčević has shown in ZF that, in fact, there is no function $F\!:\mathcal W(S)\to S$ with the property you require. Here, $\mathcal W(S)$ is the collection of subsets of $S$ that are well-orderable. This is corollary 6 in MR0793235 (87d:03126). Todorčević, Stevo. Partition relations for partially ordered sets. Acta Math. 155 (...


7

The answer is yes, and indeed, $Q$ is enough for Löb’s theorem: Theorem. Let $T\supseteq Q$, and let $\tau\in\Sigma_1$ define an axiom set for $T$ in $\mathbb N$. Then $$T\vdash(\Box_\tau\phi\to\phi)\implies T\vdash\phi$$ for all sentences $\phi$, where $\Box_\tau$ denotes the formalized provability predicate for $\tau$. This was proved by Pudlák [1], even ...


8

KP (Kripke-Platek set theory) is the most well-known fragment of $\sf{ZF}$ which suffices for the development of the rank function, thus $\sf{KPR}$ = $\sf{KP}$ + "for all ordinals $\alpha$, $V(\alpha)$ exists" is the usual minimal theory in which one can be assured of the stratification of the universe into $V(\alpha)$s. On the other hand, as ...


8

This answers complements Fedor Pakhamov's, who provided an example of a computable theory that is not axiomatizable by finitely many schemas. Following up on the comment by Andreas Blass to the question: Vaught proved that if a theory $T$ is computable and has "a modicum of coding", then $T$ is axiomatizable by a scheme. Vaught's result was ...


10

Let me give an example of a theory that is computably axiomatizable but isn't axiomatizable by finitely many schemas. Fix any finite signature $\Omega$ with equality. Further by finite $\Omega$-models I'll mean models encoded by binary strings in a natural way. Observe that for any $\Omega$-theory $T$ axiomatized by finitely many schemas the set of all ...


0

There are a number of algebraic theories (in equational logic specifically, no predicate symbols besides equality) which are of finite type (so the language has only finitely many function symbols) but not finitely axiomatizable. Often one demonstrates this with an infinite sequence of structures for the language, but in some cases one can establish this ...


0

Consider questions like whether $${\large{2^{2^{\sqrt{2^\phantom{o\!}}}}}}>\frac{19}{3}.$$ That inequality is true, but I think we don't know whether expressions like the left-hand side can be rational. So we don't know how accurately we need to compute towers of exponentials to see if inequalities hold. In terms of your phrasing, I don't think we have ...


2

You make an erroneous assumption in your question, as already in dimension 1 you need LLPO to know that the maximum is actually attained at some point. We work constructively. Theorem: LLPO is equivalent to the statement that every affine map $[0,1] \to \mathbb{R}$ attains its maximum Proof. The general form of an affine map on $[0,1]$ is $f_{a,b}(x) = a \...


29

Joel, I believe this was first explicitly stated and proved by E.V. Huntington in his classic paper: COMPLETE SETS OF POSTULATES FOR THE THEORY OF REAL QUANTITIES, Trans. Am. Math. Soc. vol. 4, No. 3 (1903), pp. 358-370. See Theorem II', p. 368. Edit (June 14, 2020): It is perhaps worth adding that in 1904, the year following the publication of ...


Top 50 recent answers are included