User nick thomas - MathOverflow

Constructible models of New Foundations?

2012-12-27T22:37:15Z

Hi all! Is there anything like Gödel's constructible universe for New Foundations?

More precisely, I would like a process for taking a model $M$ of NF, and using it to build a model $L \subseteq M$ of NF with the property that every set in $L$ is defined by a (stratified) first-order formula with quantifiers ranging over $M$. (Edited; see the comments for a discussion of some issues surrounding this definition.)

Anything not exactly that, but along those lines, would also be of interest. I would also be interested in hearing about such results for non-well-founded set theories other than NF. Has this been done? Is it possible?

I'm wondering because I am trying to build this sort of constructible model for a naïve set theory that I am studying. I haven't figured out how to apply the methods used for models of ZF to models of naïve set theory. I'm guessing that similar issues might apply in working with NF, because both theories are primarily distinguished by their use of a powerful comprehension axiom.

Thank you!

Answer by Nick Thomas for Status of the 196 conjecture?

2013-02-12T11:29:48Z

Here are some extensions to Aaron Meyerowitz's comments. (Edit: As Aaron points out in the comments, my primary claim here is actually wrong.)

As Aaron points out, it is clear that if computing the sum $s(x) = x + r(x)$ involves no carries, then $s(x)$ is a palindrome. In this case we call $x$ "special." If computing $s(x)$ does involve carries (i.e., $x$ is not special) but $s(x)$ is nonetheless a palindrome, we call $x$ "exceptional." Aaron asks how common exceptional numbers are.

I claim that exceptional numbers only occur in one very specific situation, and that this gives us a necessary and sufficient condition for $s(x)$ to be a palindrome. Specifically, I claim that a carrying computation of $s(x)$ results in a palindrome if and only if the carry happens in the first and last place of the number, and results in the first two digits and the final two digits all being one. So basically, the rule is that $s(x)$ is a palindrome iff there are no carries in its computation, except in one very specific situation. This applies in all bases.

Given a nonnegative integer $n$ and a base $b \geq 2$, we shall write $\bar{n}$ to denote the number of digits in $n$'s base $b$ representation. We write $n_i$ to denote the $i$th digit from the left, with $n_1$ being the first (least significant) digit, and $n_{\bar{n}}$ being the last (most significant) digit.

We shall write $n_{-i}$ to abbreviate $n_{\bar{n} - i + 1}$. This is the digit "corresponding" to $n_i$ in the reverse of $n$. We have $n_{-i} = r(n)_{i}$.

Given a number $n$, a "carry" is an index $1 \leq i \leq \bar{n}$ such that $n_i + n_{-i} \geq b$. It is a location where a carry happens in computing $s(n)$. If $n$ has no carries, then $s(n)$ is a palindrome.

Define an "inner carry" as a carry $i$ where $1 < i < \bar{n}$. An "outer carry" is a carry $i$ where $i = 1$ or $i = \bar{n}$. An "exceptional outer carry" is an outer carry is an outer carry where, letting $m = s(n)$, we have

$ m_{\bar{m}} = m_{\bar{m}-1} = m_{\bar{n}} = m_2 = m_1 = 1. $

That is, in an exceptional outer carry, the first two digits and the last two digits of $s(n)$ are all $1$.

Proposition. $s(n)$ is a palindrome iff every carry for $n$ is an exceptional outer carry.

(Left to right.) Let $m = s(n)$, and suppose $m$ is a palindrome. Suppose there is an outer carry. Then $m_{\bar{m}} = 1$. Then $m_1 = 1$. Then

$m_{\bar{m}-1} = m_{\bar{n}} = n_1 + n_{\bar{n}} - b = m_1 = 1.$

Then $m_2 = m_{\bar{m}-1} = 1$. So if there is an outer carry, it is exceptional. Now suppose there is an inner carry, and let $i$ be the smallest inner carry. (Observe that $i \leq \lceil \frac{\bar{n}}{2} \rceil$, since if $i$ is a carry, then $-i$ is also a carry.)

To begin, suppose there is no outer carry. Then $i$ is the smallest carry. Then

$m_{i-1} = n_{i-1} + n_{-(i+1)}.$

$-i$ is also a carry, so there is a carry into $-i+1$. But $-i$ is the largest carry, so there is no carry from $-i+1$. So

$m_{-i+1} = m_{-(i-1)} = n_{-(i-1)} + n_{--(i-1)} + 1 = n_{i-1} + n_{-(i-1)} + 1 \neq m_{i-1},$

so $m$ is not a palindrome. So in the case where there is no outer carry, there is no inner carry. Now suppose there is an outer carry. The outer carry is exceptional, and then

$m_{\bar{m}} = m_{\bar{m}-1} = m_{\bar{n}} = m_2 = m_1 = 1.$

If $i \geq 3$, then we can argue as in the case where there is no outer carry, since we have that there is no carry into the $i$th place. $i \neq 1$, since $i$ is inner. Suppose $i = 2$. Then there is a carry from $m_{\bar{n}-1}$ into $m_{\bar{n}}$. $n_1 + n_{\bar{n}} = b+1$, (i.e., 11 in base $b$), since there is an outer carry and $m_1 = 1$. So

$m_{\bar{n}} = n_1 + n_{\bar{n}} - b + 1 = b + 1 - b + 1 = 1 + 1 = 2,$

contradicting $m_{\bar{n}} = 1$. So there is no inner carry, and we are done with the left to right case.

(Right to left.) Suppose every carry for $n$ is an exceptional outer carry. If there are no carries, then $m = s(n)$ is a palindrome. Suppose there is an exceptional outer carry. Then $m_i = m_{-i}$ for all $i \in {1,2,\bar{m},\bar{m}-1}$ by definition, and $m_{i} = m_{-i}$ for all $2 < i < \bar{m}-1$ by the absence of inner carries.

Comments and criticisms are welcome; I suspect the proof could use refining, and it might actually be wrong!

Answer by Nick Thomas for Math major at 36

2013-02-12T12:15:41Z

Follow your dreams!

One thing you should be aware of is that there is a disconnect between the math that non-mathematicians are familiar with --- everything in calculus and below --- and the stuff that comes after. A lot of people are surprised when they get there.

The stuff that comes after calculus is very abstract. There's no simple procedure to get the answer. Every problem is different, and you are expected to be clever and figure out how it's done. This does not adequately express what it's like. Some people find it beautiful and hypnotic, and it's easily enough to keep a person occupied for the rest of their life. But for other people it is terrifying.

If you are really "in the groove of it," then doing higher math is an extremely gratifying experience, unlike anything else in life. But a lot of people find that math is more than what they bargained for, and if you struggled in your college math classes, this might be something to think about. I do not wish to discourage you; just to convey some idea of what you are signing up for. Whatever you decide, I wish you great success!

Compactness-like property for universal generalization?

2013-01-19T07:31:05Z

Hi all! I have the following problem. Suppose I have a sequence of models $M_1,M_2,...$, all of which have the same countable domain (call it $D$). $x_1,x_2,...$ is a well-ordering of $D$. $\phi(x)$ is a formula. For each $n$, I have $M_n \models \phi(x_1),...,\phi(x_n)$. I wish to construct a model $M'$, ideally again having the same domain $D$, such that $M' \models \forall x (\phi(x))$.

You can see that what I want here is similar to an argument by compactness; but as far as I understand, the compactness theorem doesn't apply here. I've also done some fiddling with ultraproducts; but the problem I run into there is that the ultraproduct expands the universe. I don't have any objection to expanding the universe, but it keeps me from concluding $\forall x (\phi(x))$, because (at least in the approach I took, with the ultrafilter being the set of cofinite subsets), Los's theorem only gives me $\phi$ for objects of the form $(x_i,x_i, x_i, ...)$, modulo the equivalence relation.

Any ideas? Thank you!

Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-22T05:39:04Z

Hi all! I am trying to understand Specker (1953)'s proof (found here) that the axiom of choice is false in New Foundations. I am stuck on the following point. At 3.5 Specker writes:

3.5. The cardinal numbers are well ordered by the relation "there are sets $a,b$ such that $a \in n, b \in m$ and $a \subseteq b$" (axiom of choice).

I am assuming that this is a consequence of the axiom of choice, which he is using to derive a contradiction. Is that true? If so, how is it a consequence of the axiom of choice?

Another, broader question: can anybody give an intuitive explanation of why AC fails in NF?

Thank you!

Answer by Nick Thomas for Understanding Specker's disproof of the axiom of choice in New Foundations

2012-12-23T00:31:16Z

Thanks to Andreas Blass for answering my first question. Here's an attempt at my second question: an intuitive explanation of Specker's proof. Can anybody improve on it, or correct any mistakes?

Work in NF, and assume the axiom of choice. Then we can prove that in general, the cardinality of a set $A$ has greater or equal cardinality than the set of singletons drawn from $A$. For instance, the cardinality of the set of singletons is strictly less than the cardinality of the universe. The proof essentially proceeds by playing with this oddity to get a contradiction.

We define a nonincreasing function on cardinals $T(m)$, which goes from the cardinality of the set $A$ to the cardinality of the set of singletons drawn from $A$. We define an increasing function on cardinal numbers, $2^m$, which goes from the cardinality of the set of singletons drawn from $A$ to the cardinality of the power set of $A$. Thus $2^m$ is similar to the usual cardinal exponentiation, but in general it grows more quickly.

$2^m$ is not defined everywhere; in particular, $2^{|V|}$ is undefined, where $|V|$ is the cardinality of the universe, since $|V|$ is not the cardinality of a set of singletons, since the largest set of singletons (the set of all singletons) is strictly smaller. More generally, $2^m$ is undefined if and only if $m$ is strictly larger than the cardinality of the set of all singletons. This characterizes a certain final segment of the cardinals.

We define $\phi(m)$ as the set of cardinals ${m, 2^m, 2^{2^m}, ...}$, as far out as those are defined. Because $2^m$ is not defined everywhere, there are cardinals such that $|\phi(m)|$ (i.e., "the number of times we can use our modified power set operation before we fall off the egde of the universe") is finite. In particular, Specker proves that if $|\phi(m)|$ is finite, then $|\phi(T(m))| = |\phi(m)| + (1\ \text{or}\ 2)$.

Now we construct a paradoxical set. Let $c$ be the smallest cardinal number such that $|\phi(c)|$ is finite. Then $|\phi(T(c))|$ is also finite. Since $T$ is a nonincreasing function, we have $T(c) \leq c$, and since $c$ is the smallest cardinal with $|\phi(c)|$ finite, $c = T(c)$. Then $|\phi(c)| = |\phi(T(c))|$, but by the previous paragraph $|\phi(T(c))| = |\phi(c)| + (1\ \text{or}\ 2)$. By contradiction, the axiom of choice is false.

Existential instantiation in Hilbert-style deduction systems

2012-12-18T01:16:38Z

In some deduction systems there is a rule* that given $\exists x (\phi(x))$, we can infer $\phi(y)$, where $y$ is a fresh variable (i.e., one we haven't yet mentioned in this context). Call this rule "EI."

(Edit: in the opening sentence I originally said "in natural deduction systems there is typically a rule that..." Andrej Bauer has kindly informed me that natural deduction systems typically do not have this rule. In this post I am, I have learned, using a somewhat unusual set of conventions regarding the treatment of free variables.)

Let $M$ denote a model, $A,B$ variable assignments, and $T,U$ theories. Let $\text{fv}(T)$ denote the set of variables free in $T$. Let $A|_{\text{fv}(T)}$ denote $A$ restricted in its domain to $\text{fv}(T)$.

Call this the "simple definition" of semantic entailment: $T \models U$ iff, for all $M,A$, if $M,A \models T$ then $M,A \models U$. We can't use the simple definition in a system with EI, because $A$ might not contain an appropriate value in a fresh variable we instantiate into.

For contrast, call this the "complicated definition" of semantic entailment: $T \models U$ iff, for all $M,A$, if $M,A \models T$ then $M,B \models U$, for some $B \supseteq A|_{\text{fv}(T)}$. That is, we can change the values of unused variables across semantic entailments. This definition is compatible with EI.

My questions:

Does a typical Hilbert system (e.g., the one on Wiki) allow for anything like EI? Can we actually infer $\phi(y)$ (with $y$ fresh) from $\exists x (\phi(x))$? If not, how do we make up for the lack of this feature?
Can a typical Hilbert system be interpreted by the simple definition of semantic entailment?
The Henkin-style completeness proofs with which I am familiar (e.g., this one) make essential use of EI in the step of constructing a maximal, consistent superset with witnesses. If Hilbert systems don't have EI, how do we fulfill the function of this step? If Hilbert systems don't have EI, is it even possible to prove them complete using a Henkin-style proof, or do we need to use a completely different method?

I'm asking because I'm trying to write a completeness proof for a non-classical logic (a variant of LP), with a Hilbert-style deduction system.

Thank you for your help!

Comment by Nick Thomas

2013-02-22T05:18:07Z

Aaron: Sorry I missed your comment! That's an exciting idea! Could you possibly state your conjecture more explicitly? Are you trying to give a necessary and sufficient condition for $s(x)$ to be a palindrome?

Comment by Nick Thomas

2013-02-12T22:58:26Z

Aaron: Shoot! I will try to see where I have gone wrong.

Comment by Nick Thomas

2013-02-12T12:49:05Z

Thank you, Andre!

Comment by Nick Thomas

2013-01-19T22:17:17Z

Goldstern: Ah, I understand. That's a useful insight; thank you!

Comment by Nick Thomas

2013-01-19T21:17:09Z

Goldstern: My trouble is figuring out what other relations between the models might be relevant here. (Obviously I'll post if I figure that out.) Unfortunately, I do not understand the part in quotation marks. :-/ (Care to explain more?) $\phi$ does not mention the well-order. Francois: Thanks for the suggestion! I am going to play with it and see if it gets me anywhere.

Comment by Nick Thomas

2013-01-19T08:01:28Z

Andres: That's an excellent question, and it shows that what I'm asking for can't be done in general. In my specific problem, $\phi(x)$ has a form which excludes that case. But it seems clear that I haven't asked the right question, because I haven't included enough constraints to yield a solvable problem. I will see if I can repair my question; and in the meantime, thanks for your help!

Comment by Nick Thomas

2012-12-30T02:06:52Z

Andreas: Excellent, thanks!

Comment by Nick Thomas

2012-12-30T01:43:04Z

@Andreas: Thanks; I'll edit the question. I'd like to use the trick you described for eliminating parameters in a proof I'm writing. Is it something you thought of in this thread, and if so may I cite your comments here? Thank you!

Comment by Nick Thomas

2012-12-29T00:15:39Z

@Andreas: That looks right to me. Thank you for working this out with me. So perhaps what I really want to ask for is simply a model of NF wherein every set is definable by a stratified formula without parameters. Does that seem sensible?

Comment by Nick Thomas

2012-12-28T22:30:55Z

@Andreas: So your thought is that every definable set would already be defined in the first stage? That seems like a distinct possibility. If $a$ is a definable parameter defined by $\psi(x)$, replace $x \in a$ with $\psi(x)$, and $a \in x$ with... ? Let me know if you have an answer there. As for your question about stratification, truly no clue.

Comment by Nick Thomas

2012-12-28T03:13:55Z

Also (sorry about the fourth comment!): can anybody explain what Holmes' result (if correct) says (if anything) about the relative consistency of NF and, say, ZF or ZFC? (Should this be a new question?)

Comment by Nick Thomas

2012-12-28T03:06:20Z

The iterative conception here is as follows. Stage 0 is sets definable by formulas without parameters. Stage $n+1$ is sets definable by formulas with parameters from stage $n$.

Comment by Nick Thomas

2012-12-28T03:05:20Z

@Andreas and @Francois: You both raise similar and important issues with the way I've framed my question. In particular, you're right, Andreas, that the requirement I stated is trivially fulfilled. Thanks for pointing that out. Here's a possible alternate formulation. Given a model $M$, call a set $x \in M$ "definable" iff $x$ is defined by a (stratified) formula, with quantifiers ranging over $M$, whose parameters are definable. Do you think that makes sense of the question?

Comment by Nick Thomas

2012-12-28T03:00:40Z

@Andres: it sounds like you've essentially answered my question, with the answer being "nobody's done it;" correct? Also, thanks for sharing the announcement of that exciting result! @Ben: Yeah, but you can assume that a model exists and then play with it to make new models. Maybe you already know this, and maybe I'm missing something. But e.g., assume that a model of ZFC exists, and use said model to build a model where the continuum hypothesis fails, and you've effectively proven that if ZFC is consistent (a model exists) then ZFC doesn't prove CH (there is a model of ZFC where CH fails).

Comment by Nick Thomas

2012-12-27T04:15:50Z

Thanks for the correction! I believe Randall Holmes suggested the same thing, so this is an error on my part. Thanks also for your other correction.