User amit kumar gupta - MathOverflow

How much of ZFC does Quine's New Foundations prove?

2010-11-26T01:35:38Z

Main Question: Does anyone know of a reference that can tell me which axioms of ZFC Quine's New Foundations prove, disprove, and leave undecided?

Secondary Question: I've read that diagonal arguments don't go through in NF and thus can't be used to prove that the reals are uncountable. Does NF manage to prove the uncountability of the reals by some other means or does that fact (normally rendered as "$P _1(\mathbb{N}) < P(\mathbb{N})$" in order to make sense in NF) turn out to be undecidable in NF?

Answer by Amit Kumar Gupta for A “mother of all groups”? What kind of structures have "mother of all"s?

2013-04-01T08:15:39Z

Let $\mathcal{G}$ denote the class of all groups. Define

$$\mathcal{M} = \left\{ f : \mathcal{G} \dashrightarrow \bigcup\mathcal{G} : \left(\forall G \in \mathrm{dom}(f)\right)\left(f(G) \in G\setminus\{\mathrm{id}_G\}\right)\right\}$$

In other words, $\mathcal{M}$ consists of all set-sized partial choice functions on the class of all groups, excluding choice functions that ever pick the identity. The empty function is the identity of this class group, the inverse of a function in $\mathcal{M}$ is its point-wise inverse, and multiplication is defined as follows:

$\mathrm{dom}(fg) = \mathrm{dom}(f) \cup \mathrm{dom}(g) \setminus \{G \in \mathcal{G} : f(G)g(G) = \mathrm{id}_G\}$
$(fg)(G) = f(G)g(G)$ if $G\in\mathrm{dom}(f)\cap\mathrm{dom}(g)$ and $f(G)g(G)\neq\mathrm{id}_G$
$(fg)(G) = f(G)$ if $G \in \mathrm{dom}(f)\setminus\mathrm{dom}(g)$
$(fg)(G) = g(G)$ if $G \in \mathrm{dom}(g)\setminus\mathrm{dom}(f)$

The intuitive idea here is you want to take the Cartesian product of all the groups. In other words, your mother group would consist of all the class-sized choice functions on $\mathcal{G}$. Of course, a class can't have class-sized elements, so we try to settle for taking the class of all set-sized partial choice functions on $\mathcal{G}$. The problem with that boils down to what to take as the identity element? Or in other words, how do you differentiate a partial choice function from one that is similar, but additionally picks out some identity elements from groups in its domain? The solution is to "disallow" choosing the identity. This leads us to make the identity of this mother group the empty choice function, and to define multiplication essentially like point-wise multiplication, except that we remove any identities in the result.

Answer by Amit Kumar Gupta for Is there a name for the smallest ordinal $\alpha$ such that $X \subseteq \alpha$

2012-12-26T01:24:24Z

$\mathrm{rank}(X)$

Answer by Amit Kumar Gupta for How many well orderings of $\aleph_0$ are there?

2012-11-17T06:18:32Z

Consider the tree of finite partial attempts to build a well-ordering, and notice that it has size continuum.

More rigorously, let:

$$T = \{ f : n \to \omega\ |\ n \in \omega, f \mbox{ injective } \}$$

ordered by extension. This is clearly an $\omega$ branching tree of height $\omega$, and its branches are precisely the injections $\omega \to \omega$. But we're interested in the set of well-orderings of $\omega$. Now, those injections which are bijections give us distinct well-orderings, but perhaps there are too few of them. What about the branches that aren't surjections? We can create distinct well-orderings out of them too: if a branch $b$ is not surjective and $X$ is the set of naturals missed by its range, consider the well-ordering obtained by taking $b$, then concatenating on to its end the numbers in $X$, ordered naturally.

So the branches of our tree are in bijection with a set of well-orderings of $\omega$, and there are continuum many branches, so there are continuum many well-orderings. Note that the set of well-orderings we get is not even the set of all well-orderings. In particular every well-ordering we get has order type $\leq \omega + \omega$.

Does the fact that this vector space is not isomorphic to its double-dual require choice?

2010-12-14T04:38:51Z

Let $V$ denote the vector space of sequences of real numbers that are eventually 0, and let $W$ denote the vector space of sequences of real numbers. Given $w \in W$ and $v \in V$, we can take their "dot product" $w \cdot v$, and for any give $w \in W$, this defines a linear functional $V \to \mathbb{R}$. In fact, under this association, we see that $W \cong V^{\ast}$. Assuming choice, $W$ has a basis and has uncountable dimension, whereas $V$ has countable dimension. So $\mathrm{dim} (V) < \mathrm{dim} (V^{\ast}) \leq \dim(V^{\ast \ast})$ so $V$ is not isomorphic to its double-dual. In particular, the canonical map $\widehat{\cdot} : V \to V^{\ast \ast}$ defined by $\widehat{x} (f) = f(x)$ is not an isomorphism.

Question 1: Can you explicitly write down an element of $V^{\ast \ast}$ that isn't of the form $\widehat{x}$?

Question 2: What's the situation if we don't assume choice? (i.e. might the canonical map be an isomorphism, might $W$ not even have a basis, might $V$ be isomorphic to its double-dual but not via the canonical map, etc?)

In light of Daniel's and Yemon's comments, and Konrad's related question here, I'd like to reorganize my question(s). So consider the following statements:

The canonical map $\widehat{\cdot} : V \to V^{\ast \ast}$ is injective but not surjective.
The canonical map is not an isomorphism.
There is no isomorphism from $V$ to its double-dual.
The double-dual is non-trivial.
$V^{\ast}$ has a basis.

This is the question I'm really interested in, and which clarifies and makes more precise my original Question 1:

Revised Question 1: Are there models without choice where (1) holds? If so, can we find some $x \in V^{\ast \ast}$ witnessing non-surjectivity to describe a witness to non-surjectivity in choice models? Are there models of choice where (1) fails?

The following question is a more precise version of Question 2.

Revised Question 2: Under AC, all 5 statements above are true. There are $2^5 = 32$ ways to assign true-false values to the 5 sentences above that might hold in some model of ZF where choice fails. Not all 32 are legitimate possibilites, some of them are incompatible with ZF since, for instance, (1) implies (2), (5) implies (4), and the negation of (4) implies (1) through (3), etc. Which of the legitimate possibilites actually obtains in some model of ZF where choice fails?

This second question is rather broad, and breaks down into something on the order of 32 cases, so seeing an answer to any one of the legitimate cases would be cool.

Generalizations of pcf theory

2011-10-10T22:02:31Z

Does anyone know of generalizations of pcf theory where we might consider products of the form:

$$\aleph_1 \times (\aleph_2 \times \aleph_2) \times (\aleph_3 \times \aleph_3 \times \aleph_3) \dots$$

$$(\aleph_1 \times \aleph_2 \times \dots) \times (\aleph_1 \times \aleph_2 \times \dots) \times \dots$$

or, more abstractly:

$$P_1 \times P_2 \times P_3 \times \dots$$

where each $P_i$ is a $\mathrm{cof}(P_i)$-directed partial order. My motivation is that I'm interested in what the relationship between $$\max\mathrm{pcf}\langle \aleph_1,\aleph_2,\aleph_2,\aleph_3,\aleph_3,\aleph_3,\dots\rangle$$ and $$\max\mathrm{pcf}\langle\aleph_n\rangle_{0 < n < \omega }$$ might be because it might help me understand the relationship between $$\max \mathrm{pcf} \langle \aleph_n \rangle_{0 < n <\omega }$$ and $$\max \mathrm{pcf} \langle \aleph_{2n} \rangle_{0 < n <\omega }$$

Claim: The $\mathrm{pcf}$ structure on $(\aleph_1 \times \aleph_2 \times \dots) \times (\aleph_1 \times \aleph_2 \times \dots) \times \dots$ gives nothing new.

Proof: For notational convenience, let $A : \omega \to \mathrm{Reg}$ be defined by $A(n) = \aleph_n$ and let $B : \omega \cdot \omega \to \mathrm{Reg}$ be defined by $B(\omega\cdot m + n) = \aleph_n$. Define

$$\mathrm{pcf}(A) = \{\mathrm{cf}(\Pi_{n<\omega}A(n)/U)\ :\ U \in \beta \omega\}$$ $$\mathrm{pcf}(B) = \{\mathrm{cf}(\Pi_{\alpha<\omega\cdot\omega}B(\alpha)/U)\ :\ U \in \beta (\omega\cdot\omega)\}$$

Where $\beta X$ denotes the set of all ultrafilters on $X$. It's not hard to see that $\mathrm{pcf}(A) \subseteq \mathrm{pcf}(B)$ and since $\mathrm{pcf}(A)$ is an interval of regular cardinals, it suffices to show that $\max \mathrm{pcf}(B) = \max \mathrm{pcf}(B)$. We know that we can find an everywhere-pointwise-dominating family on $\Pi A$ of size $\lambda := \max\mathrm{pcf}(A)$. If we can find a dominating family on $\Pi B$ of that same size, we'll be done.

So, given a dominating family $\mathcal{F}$ on $\Pi A$ of size $\lambda$, just let $\mathcal{F}^\ast \subseteq \Pi B$ consist of functions of the form: $$f^\ast (\omega\cdot m + n) = f(n)$$ for each $f \in \mathcal{F}$. Now given $g \in \Pi B$, define: $$g'(\omega\cdot m + n) = \sup_{m' \in \omega}g(\omega\cdot m' + n)$$ We see that $g' \geq g$ everywhere pointwise, and $g' \in \Pi B$ since we're always taking countable suprema within uncountable regular cardinals. Since $g'$ has the same value at any of its coordinates that correspond to the same $\aleph_n$, it's clear that there's some $f \in \mathcal{F}$ such that $f^\ast \in \mathcal{F}^\ast$ dominates $g'$ everywhere, and hence $g$ everywhere.

Bounds on $\max \mathrm{pcf}(A)$ if $\Pi A$ is big

2011-10-10T21:43:20Z

For concreteness, let $A = \{\aleph_n : n < \omega\}$ . We know $\max \mathrm{pcf}(A) \in [\aleph_{\omega+1},\Pi A]$. My question is, if $\Pi A$ is big (say, $\aleph_{\omega_1+1}$), then which cardinals in that interval can $\max \mathrm{pcf}(A)$ really be?

My second question, which motivates the first, is: Let $E = \{\aleph_{2n} : n < \omega\}$ and $O = \{\aleph_{2n+1} : n < \omega \}$ ; then is it possible for $\max \mathrm{pcf}(A) = \max \mathrm{pcf}(E) \gg \max \mathrm{pcf}(O)$ (where $\gg$ means "much larger than" in any way you care to make precise)?

If the answer to the first question is that $\max \mathrm{pcf}(A)$ can never really be that big, then the second question doesn't matter. But if it can be big, and the answer to the second question is that the even alephs and the odd alephs can have very different $\max\mathrm{pcf}$'s, I would find that somewhat disturbing.

Answer by Amit Kumar Gupta for Is there an easy description of the structure of this infinite group?

2011-09-20T07:47:17Z

Not an answer, just a series of observations which will hopefully be of some use, and too long for a comment. The last observation might be relevant to your question about whether $G$ is the direct sum of countably many copies of $S_\infty$, unless I've over-simplified something.

For each weight $w$, we may associate the collection $$I_w = \left\{A \subseteq \omega\ |\ \sum_{n \in A}w(n) < \infty\right\}$$
Then $I_w = P(\omega)$ iff $\sum_{n \in \omega} w(n) < \infty$. If the series is divergent, then $I_w$ is a non-principal ideal extending the ideal $\mathrm{Fin}$ of finite sets, and moreover this ideal is not maximal, i.e. its dual filter is not an ultrafilter.
$S_{\infty}(w) = \bigcup _{A \in I_w}S_A$ where $S_A$ is the subgroup of $S_{\infty}$ which fixes $\omega \setminus A$ pointwise, i.e. it's the set of permutations of $A$.
The map $(I_w,\subseteq) \to ($subgroups of $S_\infty,\leq)$ defined by $A \mapsto S_A$ is an injective homomorphism of posets. We're essentially interested in the union of the range of this map, but unfortunately this is not equal to the image of the union of the domain of this map.
Also note that $(I_w,\subseteq)$ is a lattice and a directed set, as is the range of the above map.
If $\lim_{n\to\infty}w(n) = 0$ but $\sum_{n\in\omega}w(n) = \infty$, then there is no partition of $\omega$ into countably many infinite sets $A_n (n \in \omega)$ such that $S_\infty(w)$ is isomorphic to the direct sum of the $S_{A_n}$ in the "obvious" way. That is, $S_\infty(w)$ doesn't consist merely of those permutations which can be expressed as a finite product of elements from finitely many of the $S_{A_n}$. [Proof: For each $n$, pick some $m_n \in A_n$ such that $w(m_n) < 2^{-n}$. Set $A = \{m_n : n \in \omega\}$ . Then $S_A \leq S_{\infty}(w)$ but there are elements of $S_A$ which can't be written as a finite product of elements of the $S_{A_n}$.]

PFA and the compactness/incompactness of $\omega_2$

2011-09-07T00:21:50Z

There are many consequences of the Proper Forcing Axiom (PFA) which essentially say that $\omega_2$ has a lot of compactness.

For instance, Matteo Viale and Christoph Weiss have a few papers in which the combinatorial properties $\mathrm{SP}(\kappa)$ and $\mathrm{ISP}(\kappa)$ (which can be seen as generalizations of the tree property) are isolated, and the following theorems (which are modification of older results of Jech and Magidor, respectively) are stated:

$\kappa$ is strongly compact iff $\kappa$ is inaccessible and $\mathrm{SP}(\kappa)$
$\kappa$ is supercompact iff $\kappa$ is inaccessible and $\mathrm{ISP}(\kappa)$

They also show that $\mathrm{PFA} \rightarrow \mathrm{ISP}(\omega_2)$ (and $\mathrm{SP}(\omega_2)$), so one can read this as saying PFA implies $\omega_2$ is as "compact" as a supercompact, minus the inaccessibility.

On the other hand, there are consequences of PFA (including the statement of PFA itself) which seem to say that $\omega_2$ is very much incompact. For instance, consider Rado's Conjecture (RC). RC is the statement: If $T$ is a tree such that every subtree of size $< \omega_2$ can be decomposed into countably many antichains, then so can $T$. It's not hard to see how RC is, in some sense, saying that $\omega_2$ is compact: If we replace $\omega_2$ with a compact cardinal $\kappa$ in the statement of RC, then the statement is true by the "compactness of the language $\mathcal{L}_{\kappa,\kappa}$" characterization of $\kappa$. But PFA contradicts RC. Nonetheless, both PFA and RC are usually obtained by proper forcings which collapse a supercompact to $\omega_2$.

PFA itself seems to say $\omega_2$ is incompact: Let $\mathbb{P}$ be a proper forcing, and consider the language which has a constant symbol for every element of $\mathbb{P}$, a binary relation symbol (for the relation on $\mathbb{P}$), a unary predicate for each dense subset of $\mathbb{P}$, and a unary predicate which will stand for a generic filter. Consider the theory consisting of the positive diagram of $(\mathbb{P},\leq,p\ (p\in \mathbb{P}), D\ (D \subseteq \mathbb{P}\mbox{ dense}))$ together with formulas saying that $G$ is a filter and $G$ meets every $D$ (a new formula for each $D$). PFA says that any subtheory of size $< \omega_2$ has a model, but there's no filter meeting every dense set in the ground model, so loosely speaking, this theory doesn't have a model (although I suppose there could be a model which adds unnamed elements to each dense subset and has a generic meeting each dense subset at an unnamed condition).

My question is:

Is there some way to reconcile the fact that PFA seems to simultaneously say that $\omega_2$ has properties strongly indicative of some sort of compactness, and also has properties strongly indicative of some sort of incompactness?

Answer by Amit Kumar Gupta for Examples where it's useful to know that a mathematical object belongs to some family of objects

2011-09-03T20:51:20Z

I don't think this fits the specific criteria you've set out, but I believe it is in the right spirit. It involves using a mathematical concept all undergrads learn to give an elegant solution to a very down to earth puzzle that anyone can understand.

Background

The puzzle is about the game of SET. If you know how the game is played, don't bother reading this paragraph or the next. In the game of SET, you have a number of cards, and on each card there's a simple image. The image consists of 1, 2 or 3 identical shapes. These shapes can be one of three shapes: diamonds, squiggles, and ovals (on a given card, all the shapes are the same, but different cards may have different shapes). On a given card, all the shapes are coloured the same, in one of three possible colours: red, green, and purple. And finally, on a given card, all the shapes are shaded in the same manner, in one of three different possible manners: outlined, filled in, or hatched.

The game involves multiple players, and the goal for each player is to collect the greatest number of sets, where a set is a collection of three cards such that for each category (shape, number, colour, shading), all three cards are either the same or all different. So for example if you have three cards, all three of which are made up of 2 squiggles, but are three different colours and shaded in the three different ways, then this is a set. At the beginning of the game, the cards are all laid out, and then players form sets as quickly as the can until all the cards are gone, and the winner is the one who has made the most sets.

The Puzzle

Suppose you're playing Set, and as you're approaching the end of the game, you notice there are only 11 cards remaining. There ought to be a multiple of three remaining, so you figure one card must have gone missing from your deck. Looking only at the 11 remaining cards, can you figure out which card is missing?

Alternatively, draw up an example of some 11 cards, and ask the student to solve the same problem. When presented with a specific example, the student may not think that there is a general solution, and so making the problem more concrete actually adds an interesting twist to the problem, it makes it a nice test of analytical thinking.

The Solution

The set of all cards can be regarded as a 4-dimensional vector space over $\mathbb{F}_3$ in an obvious way. Why give it this vector space structure? Because a collection of three cards is a set iff, regarded as vectors in this vector space, their sum is the zero vector. Also, since you're supposed to be able to make sets until you've eliminated all the cards, you know that the sum of all the cards is 0. So:

0 = sum of cards put into sets so far + sum of remaining 11 cards + missing card

Clearly the sum of the cards put into sets is 0, and so:

missing card = -(sum of remaining 11)

And that's about it!

Answer by Amit Kumar Gupta for Other Ring Structures on $\mathbb{Q}$

2011-08-31T19:00:03Z

Given any bijection $f : \mathbb{Q} \to R$ where $(R,\oplus,\otimes)$ is some (necessarily countable) ring, you'll be able to get a new ring structure $(\mathbb{Q},\boxplus,\boxtimes)$ isomorphic to $(R,\oplus,\otimes)$, by setting:

$a \boxplus b = f^{-1}(f(a)\oplus f(b))$
$a \boxtimes b = f^{-1}(f(a)\otimes f(b))$

The nicer $f$ is, the nicer the expressions for $\boxplus$ and $\boxtimes$ will be. Perhaps the simplest examples are if $p \in \mathbb{Q}^\times,\ q\in \mathbb{Q}$, $R = \mathbb{Q}$, then $f(x) = px+q$ will work. This generalizes Neil's and Pace's answers.

The "converse" is trivially true, in that if $f : (\mathbb{Q},\boxplus,\boxtimes) \to (R,\oplus,\otimes)$ is an isomorphism from some ring structure on $\mathbb{Q}$ to a ring $R$, then $f$ is a bijection $\mathbb{Q} \to R$ and

$a \boxplus b = f^{-1}(f(a)\oplus f(b))$
$a \boxtimes b = f^{-1}(f(a)\otimes f(b))$

So in some sense, the above method for getting a ring structure on $\mathbb{Q}$ is the only way to do it. The question (more or less) boils down to, "for which rings $(R,\oplus,\otimes)$ is there a 'nice' bijection $\mathbb{Q} \to R$?" It depends, of course, on what you think "nice" means.

Why is this theorem (about $L(P(\omega_1))^V$ and $L(P(\omega_1))^{V[G]}$) nice?

2011-07-10T18:12:00Z

I was recently told that the following (due to M. Viale) is a nice theorem:

Suppose there are arbitrarily large supercompacts, and $\mathrm{MM}$ holds in $V$. Let $G$ be generic for a proper forcing and $V[G] \vDash \mathrm{MM}$. Then $L(P(\omega_1))^V$ is elementarily equivalent to $L(P(\omega_1))^{V[G]}$.

My question (borne of ignorance, not skepticism) is:

Why is this theorem nice, and how does it fit into the bigger picture?

Some slightly-more-specific questions that refine my main question are: Do the hypotheses of this theorem often come up in natural settings? What's the upshot of the conclusion? Is it that proper forcing which preserves $\mathrm{MM}$, leaves the theory of a small but not-that-small chunk of the universe unchanged?

Reference letters for teaching positions

2011-07-09T03:03:16Z

I've been told that when applying for a teaching position, your reference letters can be written by anyone who is familiar with your teaching capabilities in detail. I feel that this primarily just means students, but I wonder if there's some unspoken rule that reference letters should come from people in positions of authority, e.g. professors for whom I've served as TA, administrative staff in the math department, etc. In reality, it's the students who know my teaching capabilities in detail, and perhaps to a lesser degree my friends, whereas professors and administrators have no direct knowledge my teaching abilities whatsoever, and might only have heard things here or there from students, or have read my student evaluations and seen the scores.

So should reference letters predominantly come from authority figures, or is it okay to have them all come from students?

Answer by Amit Kumar Gupta for Characterization of infinite paths in graphs

2011-05-12T03:11:49Z

(Not an answer, but too long for a comment)

One way to look at what you're asking for is a theory in some appropriate language which axiomatizes that we have a serial directed rooted graph, and a collection of subsets of the graph which behaves like $N(\mathcal{G},s)$, where the part of the axiomatization that dictates the behaviour of $N(\mathcal{G},s)$ doesn't say anything about the graph relation on $\mathcal{G}$. I'll give an axiomatization where the part that talks about $N(\mathcal{G},s)$ does mention the graph relation, and I'll set it up in such a way that it'll seem unlikely that it can be redone without mentioning the graph relation. I'm not sure about this, it's just an idea, but it's too long for a comment.

The Language

Consider the language $(\bar{V}, \bar{N}, \bar{E}, \bar{s}, \bar{\epsilon})$ - two unary relation symbols, one binary relation symbol, one constant symbol, and another binary relation symbol, respectively. I'm going to set up a theory whose finite models will be precisely (sort of) those in which $(\bar{V}, \bar{E})$ is interpreted as a directed serial graph $\mathcal{G}$, $\bar{s}$ gets interpreted as a member $s$ of $\bar{V}$, $\bar{N}$ gets interpreted as $N(\mathcal{G},s)$, and $\bar{\epsilon}$ gets interpreted as the membership relation, a subset of $\bar{V} \times \bar{N}$. Setting up the right theory is easy, the only part that will require a little explanation is how we ensure $\bar{N}$ gets interpreted correctly.

Axiomatizing $N(\mathcal{G},s)$ when we're allowed to mention the edge relation

Consider a formula like: $$x_1 = \bar{s} \wedge x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge x_2 \neq x_3$$ $$\wedge \bar{E}(x_1,x_2) \wedge \bar{E}(x_2,x_1) \wedge \neg \bar{E}(x_1,x_3) \wedge \neg \bar{E}(x_3,x_1) \wedge \neg \bar{E}(x_2,x_3) \wedge \neg \bar{E}(x_3,x_2)$$ It "says" we have three distinct $x_i$, the first one is $s$, and it tells you exactly which pairs stand in edge relation to one another and which don't. You can also tell by looking at it that it defines a set $\{ x_1, x_2, x_3\}$ which contains an infinite path starting at $s$, namely $x_1, x_2, x_1, x_2, \dots$.

Let's define $\mathcal{R}$ to be the set of formulas in the language $(\bar{s}, \bar{E})$ of the form $\phi(x_1, \dots , x_n)$ which say that the $x_i$ are distinct, and which tell you precisely which pairs of the $x_i$ stand in $\bar{E}$ relation to one another, and which don't. Define $\mathcal{R}^+$ to be those formulas $\phi \in \mathcal{R}$ such that for any rooted directed graph $((V,E),s)$, we have that:

$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \in N((V,E),s)$ .

$\mathcal{R}^-$ will be those $\phi$ such that:

$(V,s,E)\vDash \phi(v_1, \dots , v_n) \rightarrow \{v_1, \dots , v_n\} \not\in N((V,E),s)$ .

Alright, now here's our theory:

(Rooted serial directed graph) $\bar{V}(\bar{s}) \wedge \forall x \bar{V}(x) \rightarrow [\neg \bar{E}(x,x) \wedge \exists y (\bar{V}(y) \wedge \bar{E}(x,y))]$
(Schema for what goes in $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^+$: $\forall \vec{x} \exists Y \forall x \left (\phi(\vec{x}) \rightarrow \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$
(Schema for what stays out of $N$) As $\phi(x_1, \dots ,x_n)$ varies over $\mathcal{R}^-$: $\forall \vec{x} \forall Y \exists x \left (\phi(\vec{x}) \rightarrow \neg \left[ \bar{N}(Y) \wedge \bigwedge _i (x_i \bar{\epsilon} Y) \wedge \left (x \bar{\epsilon} Y \rightarrow \bigvee _i (x = x_i)\right )\right ]\right )$

Checking this axiomatization works

It's clear that if $\mathcal{G} = (V,E)$ is a finite directed serial graph and $s \in V$, then $(V,N(\mathcal{G},s),E,s,\in)$ is a model of this theory. Conversely, if we have a finite model $(V,N_0,E,s,\epsilon)$ of this theory, then $(V,E)$ forms a directed serial graph with $s \in V$. Now let $N_1$ consist of those $Y \in N_0$ such that $\forall x (x \epsilon Y \rightarrow V(x))$. I claim that:

$N((V,E),s) = \{ \{x : x \epsilon Y\} : Y \in N_1\}$

But I won't prove this.

A remark about some "unnaturalness"

It should seem like I could have done things differently so that things looked more natural and the above claim could be proved more easily. The way I've written 2 and 3 are not the most natural, but I've done it for a reason. 2 says that if $\vec{x}$ is a tuple which is sure to contain an infinite path starting at $s$, then there's a member of $N$ consisting precisely of the members of $\vec{x}$. 3 says that if $\vec{x}$ is sure to not contain an infinite path starting at $x$, then there's nothing in $N$ consisting precisely of the members of $\vec{x}$. The formulas in 2 and 3 are in prenex normal form, where the matrix is a conditional where the left side only involves the symbols $\bar{E}$ and $\bar{s}$, and the right side only $\bar{N}$ and $\bar{\epsilon}$. Moreover, the antecedents have variables $\vec{x}$ and the consequents have variables $\vec{x}, Y, x$.

The point

You want a theory equivalent to axiom 1 and schemas 2 and 3 above, but you want to replace 2 and 3 with (probably finitely many) axioms which don't mention the symbol $\bar{E}$. I feel like there ought to be some interpolation-type theorem (along the lines of Craig Interpolation or Lyndon Interpolation) which says this can't happen, i.e. something which says that a theory in which each axiom mention either only $\bar{V}, \bar{E}, \bar{s}$ or only $\bar{V}, \bar{N}, \bar{s}, \bar{\epsilon}$ can't prove a theory which has axioms like those in schemas 2 or 3.

Is every p-point ultrafilter Ramsey?

2011-04-19T18:28:12Z

A non-principal ultrafilter $\mathcal{U}$ on $\omega$ is a p-point (or weakly selective) iff for every partition $\omega = \bigsqcup _{n < \omega} Z_n$ into null sets, i.e each $Z_n \not \in \mathcal{U}$, there exists a measure one set $S \in \mathcal{U}$ such that $S \cap Z_n$ is finite for each $n$.

A non-principal ultrafilter $\mathcal{U}$ on $\omega$ is Ramsey (or selective) iff for every partition as above, there exists a measure one set $S$ such that $|S \cap Z_n| = 1$ for each $n$.

Clearly, every Ramsey ultrafilter is a p-point. What is known about the converse?

I couldn't find anything, not even a consistency result, in any searches I've done or sources I've checked. Is very little known/published about the converse?

Is the set of cube-free binary sequences perfect?

2011-04-15T06:47:01Z

This question is inspired by this one. In that thread, it's established that there are uncountably many cube-free infinite binary strings (where $x \in 2^{\omega}$ is cube-free iff $\forall \sigma \subset x,\ \sigma \sigma \sigma \not \subset x$). Here $\subset$ denotes "substring" which should be distinguished from "initial segment" which I'll denote by $\sqsubset$ if the need arises.

So let $C \subset 2^{\omega}$ be the subset of Cantor space consisting of all cube-free sequences. It's uncountable, and easily seen to be closed, hence it contains a perfect set.

Question 1. Is $C$ perfect?

Let's define:

$T_C = \{ \sigma \in 2^{<\omega} : (\exists x \in C)(\sigma \sqsubset x)\}$
$\ \ \ \ \ = \{ \sigma \in 2^{<\omega} : (\forall n > |\sigma|)( \exists \tau \in 2^n )(\sigma \sqsubset \tau,\ \tau$ cube-free$)\}$
$T_P = \{\sigma \in 2^{<\omega} : (\forall \tau \sqsupset \sigma, \tau \in T_C)(\exists \rho_1, \rho_2 \sqsupset \tau$ both in $T_C)(\rho_1 \perp \rho_2)\}$

Question 2. $T_C$ is evidently $\Pi ^0 _1$, but is it in fact recursive?

If we let $P$ denote the maximal perfect subset of $C$ obtained by iteratively removing isolated points of $C$ until this procedure stabilizes (taking intersections at limit stages), then $P$ determines a tree which I believe would be the tree $T_P$ defined above.

Question 3. What is the complexity of the tree determined by $P$?

If $T_P$ is indeed the tree determined by $P$, then the tree determined by $P$ is at worst $\Pi ^0 _3$, but can we do better?

UPDATE: The answers are:

Yes
Yes
Since $C$ is perfect, $P = C$ and so by the answers to 1 and 2, the tree determined by $P$ is just the tree determined by $C$, which is recursive.

I've learnt this after discussing it with Robert Shelton, one of the authors of the paper Gjergji linked to in his response below. In fact, what I've gathered is that there's a function $f$, better than being on the order of $n^2$, such that to determine whether an arbitrary finite string $\sigma$ has a cube-free infinite extension, it suffices to check whether it has one of length $f(|\sigma|)$ (where $|\sigma|$ is the length of $\sigma$). I suppose this would mean furthermore that the tree $T_C$ is not merely recursive, i.e. $\Delta_1$, but in fact $\Delta_0$.

Answer by Amit Kumar Gupta for Fundamental Examples

2011-04-19T06:24:42Z

$$2^{\aleph_0} = \aleph_1$$

The Continuum Hypothesis is an example of an undecidable statement par excellence. It is an example of a problem that is:

natural;
historied -- it was first asked by Cantor himself;
celebrated -- it was Hilbert's first of his famous 23 problems; and
undecidable in a very deep way -- it's independent of all current large cardinal axioms, and in fact something deeper than this can be said, but that is currently beyond my understanding.

Moreover, the desire to "solve" CH was the main motivation, or at least one of the main motivations, for:

Godel's description of the Constructible Universe, which has already been listed as a fundamental example in logic and foundations, and the beginnings of inner model theory; and
Cohen's invention of the method of forcing which is now indispensable and ubiquitous in modern set theory, and also won Cohen a Fields medal.

Answer by Amit Kumar Gupta for Model Theoretic Localization

2011-04-18T15:29:01Z

EDIT: At the bottom, I'll explain how, if you have a ring $R$ and a subset $A$ of $R$, how you can construct a theory such that any model of that theory contains a copy of $R$ such that the copies of elements of $A$ are units.

First, let me comment on a couple issues with the approach you're taking. Then I'll try to resolve these issues by answering your question, but since I'm not 100% sure what your question is I'll give two answers.

Some technical issues: The formula $\exists x, x = x$ doesn't say anything, it just says "there's something which is equal to itself," which essentially just says "there is something." Furthermore, this formula is only well-formed when $x$, is a variable, it doesn't make sense to say it when you're picking $x$ to be some element of your ring, it would be like saying $\exists 4, 4 = 4$. Also, this formula doesn't depend on $x$ the way I think you expect it to. The formulas $\exists x, x = x$ and $\exists y, y = y$ are essentially the same, much like how $\int f(x) dx$ and $\int f(y) dy$ are the same.

I understand what you're trying to do with your theory $T_x$ (or $T_f$ in the comments), it's supposed to be a theory such that any model has an inverse for all the $x \in A \setminus${$0$}. The theory you've constructed won't work for various reasons, some of which can be fixed and some can't. One problem is there's nothing to ensure that a model of $T_x$ has a copy of your original $M$, but this can be fixed. Another problem is that there's no guarantee that $T_x$ has a model at all. Or rather, there is a guarantee, and that guarantee comes from the already known fact in commutative ring theory that localizations exists, but model theory is not doing any work for you here. Similarly, model theory does nothing to guarantee that any resulting model will satisfy the desired universal property.

Now here's how we might try to salvage your approach, and use model theory to "construct" the localization. I won't go into full detail here since I'm not sure this is what you want to know, but if you want more details just ask and I'll edit my post accordingly (edit: I've added some details at the end). The vague outline is this: Forget the universal property for now. Pick an appropriate signature, and theory in this signature, such that a model of this theory would give you the desired object - in this case a commutative ring $N$ into which $M$ embeds such that the image of $A$ under this embedding is contained in the set of units of $N$. Then, show that every finite subset of this theory has a model, which will essentially amount to showing that you can produce a localization (minus the universal property) for any finite subset of $A$. At this point, the Compactness Theorem will give a model of your entire theory, and you'll have your $N$ (and implicitly, your embedding).

There's a couple problems here. First, how would you tackle the stage where you need to be able to show that you can produce a localization (minus the univ. prop.) for finite subsets of $A$? I would use one of the standard ring-theoretic proofs of the existence of the localization. But these proofs are sufficiently general that it's just as easy to apply them to the whole of $A$ as it is to apply them to any finite subset of $A$. In other words, if you're going to have to use a ring-theoretic proof of the existence of localizations at some point in a model-theoretic construction of the localization, why do any of the model theory in the first place and apply your ring-theoretic proof directly to $A$?

More crucially, we have a problem with the universal property. There's no way to express the universal property in first-order language in such a way that the result of applying the Compactness Theorem has the desired universal property. If we are working in a much richer structure (e.g. a model of ZFC) where we can talk about rings and the elements of rings both as objects in our universe, then we can express, in a first-order way, that $N$ is the localization $A^{-1}M$, including saying everything we need to about the universal property. This is just an instance of the fact that most math can be expressed in ZFC. But if we're trying to do something like in the previous paragraph, where we use model theory, especially Compactness, to produce a localization, then we want to work in the language of rings. In this case, our universe has to pretty much be just a ring, thus its elements will be objects of a ring, and so we don't have as objects all rings, and all morphisms between rings, etc, i.e. we don't have enough expressive power to talk about the universal property. And since we can't express the universal property, applying Compactness has no way of guaranteeing us that the resulting object satisfies the universal property.

So to summarize, if you're trying to construct the localization using model theory, you can get all of it except the universal property, but even then, in order to get it you have to make heavy use of ring theory to the point that the model theory isn't doing any of the work for you.

If you merely want to express or axiomatize what it means for something to be the localization of something else, it depends on how rich a structure you want to work in. If you want to work in ZFC, of course you can express pretty much everything. If you want to work in the language of rings, you can express everything except the universal property (and again, I can give details of this if you'd like).

EDIT: Consider the following signature:

$\sigma = (0, 1, +, \times, c_r (r\in R))$

Here, $0, 1$ and each $c_r$ are constant symbols, and the other two symbols are binary function symbols. Let $\mathrm{diag}^+(R, 0, 1, +, \times)$, the so-called positive diagram of $R$, consist of all true atomic formulas in the structure $(R, 0, 1, +, \times, r (r\in R))$ regarded as a $\sigma$-structure. Now consider the $\sigma$ theory which is the union of the following theories:

$\mathrm{diag}^+(R, \dots , \times)$
$\{c_r \neq c_s\ |\ r, s\in R,\ r\neq s\}$
$\{$the commutative ring axioms$\}$
$\{\exists x (x \times c_a = 1)\ |\ a \in A\}$

The first two will guarantee that we have a copy of $R$ sitting inside our resulting structure, the third guarantees that this structure is a commutative ring, and the last guarantees that everything in $A$ has a unit.

Answer by Amit Kumar Gupta for Examples of common false beliefs in mathematics.

2011-04-16T23:29:39Z

$$2^{\aleph_0} = \aleph_1$$

This is a pet peeve of mine, I'm always surprised at the number of people who think that $\aleph_1$ is defined as $2^{\aleph_0}$ or $|\mathbb{R}|$.

If $0^{\sharp}$ exists, then every uncountable cardinal in $V$ is as large as it can be in $L$.

2011-04-15T00:08:04Z

According to Wikipedia, if $0^{\sharp}$ exists, then every uncountable cardinal in $V$ satisfies every large cardinal property in $L$ that can be realized in $L$, e.g. weak compactness, total ineffability, etc. It's easy enough to see why every uncountable in $V$ will be inaccessible, or even Mahlo, in $L$.

How can one see that some of the slightly larger large cardinal properties (e.g. weak compactness, total ineffability, etc.) are satisfied in $L$ by the uncountable cardinals in $V$? Is there a good reference for some of these results?

Does a generic normal measure extend the club filter?

2011-04-08T16:14:41Z

This question is related to this one. The setup is as follows:

In $V$, $\kappa$ is supercompact and $\mathbb{P} = \mathrm{Coll}(\kappa, \aleph_2)$ is the Levy collapse. $G$ is $(V,P)$-generic, and in $V[G]$, $C \subset P_{\kappa}(\lambda)$ is club. Let $j : V \to M$ be an embedding witnessing $\lambda$-supercompactness of $\kappa$. Lift this embedding to $j^{\ast} : V[G] \to M[G \times H]$ where we may assume $H$ is generic over $V[G]$ for the poset $\mathrm{Coll}^{V[G]}(j(\kappa), \aleph_2)$ (note $\aleph_2 ^{V[G]} = \kappa$). Now in $V[G \times H]$ we define $U \subset P_{\kappa}^{V[G]}(\lambda)$ by:

$x \in U$ iff $j[\lambda] \in j^{\ast}(x)$.

This $U$ belongs to $V[G \times H]$, but $V[G]$ "would" think its a normal measure on $P_{\kappa}^{V[G]}(\lambda)$, i.e. it's $\kappa$-complete if we restrict to $<\kappa$-sequences in $V[G]$ and it's normal if we restrict to regressive functions $f : P_{\kappa}^{V[G]}(\lambda) \to \lambda$ where $f \in V[G]$. My question:

Does $U$ also extend the club filter, if we restrict to clubs in $V[G]$?

Answer by Amit Kumar Gupta for Does a generic normal measure extend the club filter?

2011-04-10T19:05:27Z

With the help of Jason's answer to the question I linked to, I think I might be able to solve this one. The key is to show that $P_{\kappa}^{V[G]}(\lambda) \in M[G\times H]$. Let's simply denote this set by $X$. An element $x$ of $X$ can be regarded as a function $x : \omega_1 \to \lambda$, which will be a subset of $\omega_1 \times \lambda$. A nice name for such a subset is a map, in $V$, from $\omega_1 \times \lambda$ to the collection of antichains in $\mathbb{P}$. Since $\mathbb{P}$ has the $\kappa$-chain condition and $\mathbb{P} \in M$, $M$ correctly knows the set of antichains of $\mathbb{P}$. Since $M^{\lambda} \subset M$, $M$ correctly knows the set of nice $(V,\mathbb{P})$-names for subsets of $\omega_1 \times \lambda$, let's call this set $Y$.

Now $\mathbb{P}$ names are $j(\mathbb{P})$ names (since $\mathbb{P} \subset j(\mathbb{P})$), so we get that

$X = \{ \dot{x}^{G\times H}\ |\ \dot{x}^{G\times H} : \omega_1 \to \lambda, \dot{x} \in Y \} $

This is since $\dot{x}^{G \times H} = \dot{x}^G$ for nice $(V,\mathbb{P})$-names. So $X \in M[G \times H]$ as desired.

Recall, we want to show that $U$ extends the club filter, so take $C \in V[G]$ club in $X$. Following the hint in the previous question, we want to show that

$D = \{j^{\ast}(x)\ |\ x \in C\}$ belongs to $M[G \times H]$
$D$ has size less than $j(\kappa)$ in $M[G \times H]$, and
$\bigcup D = j''\lambda$.

Then, since $D$ is a directed subset of $j^{\ast}(C)$, elementarity will give us that $j''\lambda \in j^{\ast}(C)$, as desired.

Since $M^{\lambda} \subset M$, we know that $g := j\upharpoonright \lambda \in M$. So for $x \in X$ (and in particular for $x \in C$), $j^{\ast}(x) = j''x = g''x$. Using this it's not hard to see that $\bigcup D = j''\lambda$. It also implies that

$j^{\ast}$ $''X$ $= \{j^{\ast}(x)\ |\ x \in X\}$ $= \{j''x\ |\ x \in X\} = \{g''x\ |\ x \in X\}$

belongs to $M$. Now if $h : X \to C$ is a surjection in $V[G]$, then $j^{\ast}(h)\upharpoonright j^{\ast}$ $''X$ is belongs to $M[G\times H]$ and its range is $D$, so $D \in M[G\times H]$.

It remains to show $M[G\times H] \vDash |D| < j(\kappa)$. Since $j(\kappa)$ is inaccessible in $M$, there's some bijection $i: \alpha \to Y$ in $M$ for some $\alpha < j(\kappa)$. This gives a surjection $k : \alpha \to X$ in $M[G\times H]$. We can obtain a bijection $l : X \to j^{\ast}$ $''X$ via $l(x) = g''x$. And $j^{\ast}(h)\upharpoonright j^{\ast}$ $''X$ is a surjection onto $D$. So:

$M[G\times H] \vDash |D| \leq |j^{\ast}$ $''X| = |X| \leq \alpha < j(\kappa)$.

Normal measures on $P_{\kappa }(\lambda )$ extend the club filter

2011-04-08T15:58:21Z

This is (a variation on) exercise 20.4 in Jech's "Set Theory." Let $j : V \to M$ witness $\lambda$-supercompactness of $\kappa$, and consider the normal measure $U$ on $P_{\kappa}(\lambda)$ consisting of those $x$ such that $j[\lambda] \in j(x)$. (How do you make the left quotation mark symbol to denote 'j-image-of-lambda'?)

We want to show that this measure extends the club filter.

This hint is as follows: Suppose $C$ is club. Then define $D = j[C]$. Then:

$D$ is a directed subset of $j(C)$.
$D$ has size $|C| \leq \lambda ^{< \kappa} < j(\kappa )$.
Therefore $\bigcup D \in j(C)$.
$\bigcup D = j[\lambda ]$

I'm fine with 1. I'm not sure about 2 - where is the argument taking place, in $V$ or in $M$, or both? For 3, it appears the underlying argument is this:

$V \vDash \forall E \subset C\ (E$ directed and $|E| < \kappa \Rightarrow \bigcup E \in C)$

and so

$M \vDash \forall E \subset j(C)\ (E$ directed and $|E| < j(\kappa) \Rightarrow \bigcup \in j(C))$

I can accept this assuming that 2 means "$D \in M$ and $M \vDash |D| < j(\kappa )$." I'm having trouble with 4 as well - I believe that $j[\lambda] \subseteq \bigcup D$, but why does the reverse inclusion hold, i.e. why is it that $x \in C, \beta \in j(x) \Rightarrow \beta \in j[\lambda]$?

What is the consistency strength of the failure of square, in terms of large cardinals

2011-01-27T08:44:56Z

In Jech one can find a lower bound for the consistency strength of PFA in terms of large cardinals. I don't have my copy of Jech in front of me at the moment, but as I recall the presentation of this fact goes something like this:

It's stated and proven that PFA implies the failure of $\square _{\kappa}$ for all $\kappa > \omega$.
It's stated that a result of Magidor's shows that PFA implies the failure of a weaker version of square, but the proof of this is not given in the chapter (it might appear later in the book, I can't remember).
It's stated that a result of Schimmerling's proves that the failure of this weak version of square implies the existence of a model with countably many Woodin cardinals, and this is also not proved in the chapter.

My question is whether this weaker version of square is necessary to get a lower bound in terms of large cardinals, or whether there is some large cardinal lower bound on the consistency strength of "square fails everywhere" itself?

Statements forced by one condition of a poset, but not the whole thing

2011-03-07T16:42:34Z

In order to get the relative consistency of some statement, it suffices to find a notion of forcing, and a condition $p$ in that forcing, such that $p$ forces the desired statement. It seems to be the case, most often, that the interesting statements we try to force end up being forced by the whole poset.

A sufficient property for a poset to possess to make the above phenomenon occur (in the case where all parameters in the forced statement are canonical names for objects in the ground model) is almost homogeneity: For every $p, q \in P$ there is an automorphism $i$ of $P$ such that $i(p)$ and $q$ are compatible.

It makes sense that if you're building a poset to force something, the whole poset forces it (there's also the ad hoc reason that you could throw out the part that doesn't force it). However, it might happen that in trying to force a particular statement, you build a poset where some, but not all, of the conditions happens to force a different interesting statement. Also, I haven't given this much deep thought, but it seems natural for most posets to be almost homogeneous.

My questions: Are there any interesting, instances of independence results forced by part, but not all, of some poset? Are there examples of commonly encountered posets which aren't almost homogeneous.

(If there ends up being a big list of answers, I'll add the "big-list" tag and make it community wiki)

Decomposing a poset into directed subposets

2011-03-03T08:52:36Z

Let us say that a poset $P$ is $\mathbf{\kappa}$-directed iff every collection of fewer than $\kappa$-many elements in $P$ has an upper bound in $P$. $P$ has the $\mathbf{\kappa}$ chain condition iff every antichain in $P$ has size less than $\kappa$. Consider statements of the form:

Every poset $P$ with the $\kappa$ chain condition is the union of fewer than $\kappa$-many $\kappa$-directed subposets.

For $\kappa = \omega$ the above holds, it is a theorem due to M. Pouzet. The proof hinges on the following fact:

If $P$ is well-founded and has the ccc, then the partial order of downwards-closed subsets of $P$, ordered by inclusion, is well-founded.

This fact follows from a simple application of Ramsey's theorem. The following statement is not amenable to the same Ramsey-theoretic argument, and is in fact false:

(False) If $P$ is well-founded and has the $\omega _1$-cc, then the partial order of downwards-closed subsets of $P$, ordered by inclusion, is well-founded.

Therefore, if we replace $\kappa = \omega$ with $\kappa = \omega_1$ in Pouzet's theorem, we can't apply the same proof. However I've been told (by Todorcevic) that the following is in fact true:

(CH) If $P$ has the $\omega _1$-cc, then it is a countable union of $\omega _1$-directed subposets.

My question is simply a reference request: does anyone know where I can find a proof of this statement?

Answer by Amit Kumar Gupta for Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T04:37:30Z

Just like most mathematical theorems, you can formalize Godel's Theorems in some first order language (with some "standard" interpretation under which the formalization means what it's supposed to mean), turn the proof into a purely syntactic string of formulas, and figure out which formulas in that first order language are needed as axioms. I'm embarrassed to say I don't know exactly how strong the assumptions we need are to carry out the proof of Godel's Theorems, but there will be some weak fragment of ZFC probably not much stronger than PA which will do. So we would be using a theory slightly stronger than PA to establish the incompleteness of PA, but why should that be a problem?

The axioms needed for the proofs of Godel's Theorems are probably pretty natural, probably pretty close to PA, and probably have a natural interpretation. If you believe these axioms have this interpretation, then you would have no problem with Godel's proofs or the interpretation of the theorems. If not, then you're probably pretty close to believing PA is inconsistent, in which case you would probably:

Accept that the formalized versions of Godel's Theorems follow from whatever axioms are used, but only because you believe those axioms are inconsistent.
Deny that the formalized versions of Godel's Theorems mean what they're supposed to mean, and just regard what's happening in point 1 as a valid string of symbolic manipulations.
Accept the natural language meaning of Godel's Theorems, in spite of point 2, for trivial reasons, since they say, "if PA is consistent, ..."

EDIT: (in response to your edit) So we're assuming PA proves FTA, PA is consistent, and FTA might be false? What do you mean by "false," you mean false in the standard intepretation? In that case, PA would be false in the standard interpretation. Now if we take Godel's first theorem to say, "If PA is consistent, then there is a true formula in the standard interpretation which is not provable from PA," then this meta-theorem is certainly true.

EDIT: Ignas requested an explanation of some of the basics to make sense of my claim, "If PA proves FTA, and FTA fails in the standard model, then so does PA." It's too big to fit in a comment so I'm adding it to my response:

Let $\mathcal{L}$ denote the first order language of number theory, we'll have lower case Greek letters vary over sentences of $\mathcal{L}$, upper case Greek letters vary over sets of sentences of $\mathcal{L}$, and upper case Roman letters vary over $\mathcal{L}$ structures. We write $M \vDash \varphi$ to denote that $\varphi$ is true in the model $M$, i.e. when its symbols are interpreted according to $M$. Tarski's definition of truth for a sentence in a given model is by recursion on the complexity of the sentence. We write $M \vDash \Sigma$ if every member of $\Sigma$ is true in $M$. We write $\Sigma \vDash \varphi$ if for every $M$, $M \vDash \Sigma$ implies $M \vDash \varphi$, i.e. if every model of $\Sigma$ is also a model of $\varphi$.

For provability, we write $\Sigma \vdash \varphi$ to say that there is a (finite) proof of $\varphi$ using (finitely many) sentences from $\Sigma$ as axioms.

The Soundness Theorem states that for all $\Sigma ,\ \varphi$, if $\Sigma \vdash \varphi$ then $\Sigma \vDash \varphi$. It's this theorem, with PA in place of $\Sigma$ and FTA in place of $\varphi$, that I'm using to establish the claim you're asking about. The converse of this theorem is also true; it's Godel's Completeness Theorem. Putting these two theorems together, they say that the relations $\vdash$ and $\vDash$ are the same relation between sets of sentences and sentences. One (perhaps not immediately obvious) way to rephrase this is, "being true in every model is the same as being provable from no axioms." Contrast this Godel's Incompletness Theorem, which says that "being true in the standard model of number theory is not the same as being provable from PA."

Decomposing posets into countably many chains

2011-01-25T05:17:56Z

A conjecture of Galvin's is that the following is possible (which I take to mean that the consistency of the following can be proven relative to the consistency of something like ZFC, or ZFC plus some large cardinal):

A partially ordered set $P$ can be decomposed into countably many chains iff the same is true of every suborder $P_0 \subseteq P$ of size at most $\aleph _1$.

You can see it stated as Conjecture 3.3 in Todorcevic's "Combinatorial Dichotomies in Set Theory".

I'm interested in this conjecture and determining its consistency strength, but in order to get a feel for it I want to first look at it in a special case in which it's supposed to be (according to Todorcevic, if I understood what he told me correctly) provable from ZFC alone. I'll actually list three special cases of increasing generality; an answer to the last case would be ideal but I'd be happy to see an answer for the first case.

Galvin's conjecture, restricted to posets $P$ which are the Cartesian product of two linear orders (with the obvious product ordering).
GC restricted to posets which are the Cartesian product of countably many linear orders (countable = finite or denumerable).
GC restricted to posets which are subsets of some Cartesian product of countably many linear orders.

Teaching undergraduate students to write proofs

2011-01-13T01:13:14Z

In my experience, there are roughly two approaches to teaching (North American) undergraduates to write proofs:

Students see proofs in lecture and in the textbooks, and proofs are explained when necessary, for example, the first time the instructor shows a proof by induction to a group of freshman, some additional explanation of this proof method might be given. Also, students are given regular problem sets consisting of genuine mathematical questions - of course not research-level questions, but good honest questions nonetheless - and they get feedback on their proofs. This starts from day one. The general theme here is that all the math these students do is proof-based, and all the proofs they do are for the sake of math, in contrast to:
Students spend the majority of their first two years doing computations. Towards the end of this period they take a course whose primary goal is to teach proofs, and so they study proofs for the sake of learning how to do proofs, understanding the math that the proofs are about is a secondary goal. They are taught truth tables, logical connectives, quantifiers, basic set theory (as in unions and complements), proofs by contraposition, contradiction, induction. The remaining two years consist of real math, as in approach 1.

I won't hide the fact that I'm biased to approach 1. For instance, I believe that rather than specifically teaching students about complements and unions, and giving them quizzes on this stuff, it's more effective to expose it to them early and often, and either expect them to pick it up on their own or at least expect them to seek explanation from peers or teachers without anyone telling them it's time to learn about unions and complements. That said, I am genuinely open to hearing techniques along the lines of approach 2 that are effective. So my question is:

What techniques aimed specifically at teaching proof writing have you found in your experience to be effective?

EDIT: In addition to describing a particular technique, please explain in what sense you believe it to be effective, and what experiences of yours actually demonstrate this effectiveness.

Thierry Zell makes a great point, that approach 1 tends to happen when your curriculum separates math students from non-math students, and approach 2 tends to happen math, engineering, and science students are mixed together for the first two years to learn basic computational math. This brings up a strongly related question to my original question:

Can it be effective to have math majors spend some amount of time taking computational, proof-free math courses along with non-math majors? If so, in what sense can it be effective and what experiences of yours demonstrate this effectiveness?

(Question originally asked by Amit Kumar Gupta)

Answer by Amit Kumar Gupta for Tarski's caracterisation of inaccessible cardinals

2011-01-19T16:40:32Z

In modern notation, it says, "if $\kappa$ is a cardinal and $\kappa ^{< \kappa} = \kappa$, then $\kappa$ is strongly inaccessible." This isn't entirely true since the antecedent holds for $\kappa = \omega$ but $\omega$ isn't considered strongly inaccessible, but that's not a big deal. More importantly, under CH the antecedent will hold of $\aleph _1$ but $\aleph _1$ isn't a limit cardinal. So we need to add the assumptions that $\kappa$ is an uncountable limit cardinal. Given that, we can proceed:

So let's assume $\kappa ^{< \kappa} = \kappa$. First we show $\kappa$ is strong limit: $\kappa \leq 2^{< \kappa} \leq \kappa ^{< \kappa} = \kappa$. Next we show $\kappa$ is regular: Suppose not, then $\kappa ^{< \kappa} = \kappa < \kappa ^{ \mathrm{cf} ( \kappa) } \leq \kappa ^{< \kappa}$, contradiction.

Comment by Amit Kumar Gupta

2013-04-20T09:58:44Z

The question as it stands is unintelligible, and its original intention was purely social commentary. The discussion that's followed is entirely open-ended, highly opinionated, makes no pretense even of there being an attempt to find concrete solutions to concrete problems, and is only vaguely directed at the original post (necessarily so, as the original post doesn't actually make sense in the first place) . How has this not been closed yet?

Comment by Amit Kumar Gupta

2013-04-10T08:59:05Z

What's the difference between a cofinal, order-preserving class function, and a class function with cofinal image, assumed to preserve orderings?

Comment by Amit Kumar Gupta

2013-04-10T08:57:31Z

For $\Gamma=(L,\leq_L)$ then you get a well-ordering $\mathrm{Ord}\to L$. So in that sense it's "possible." Did you mean for arbitrary $\Gamma$?

Comment by Amit Kumar Gupta

2013-04-10T08:55:31Z

It's simpler to just say $\Gamma$ is a well-founded [directed](en.wikipedia.org/wiki/Directed_set) poset with a bottom element and no infinite antichains (making it a [well-quasi-ordering](en.wikipedia.org/wiki/Well-quasi-ordering)). You have a well-ordering $\phi$ due to Choice, there's no need to phrase the claim as a conditional since you're assuming choice to construct $c$ anyways. You can take $\alpha = \mathrm{cof}\Gamma$. Why are you replacing $\phi$?

Comment by Amit Kumar Gupta

2013-04-01T09:37:14Z

Also, your construction of the direct limit of the symmetric groups makes sense in the context of choice, and also gives you a class group which contains an isomorphic copy of every set group.

Comment by Amit Kumar Gupta

2013-04-01T09:32:32Z

Yes, edited.${}$

Comment by Amit Kumar Gupta

2013-01-29T09:11:57Z

What do you mean one cannot prove there exists $n$ such that $one(n)$? (PA2) with $n=0$, together with (PA1), gives precisely $\exists m \mathrm{one}(m)$.

Comment by Amit Kumar Gupta

2013-01-06T10:24:34Z

(math.stackexchange.com) would be a better venue for this question, as mathoverflow is designed for research-level mathematics.

Comment by Amit Kumar Gupta

2012-12-26T10:19:39Z

The question you're asking is equivalent to asking whether ZFC is inconsistent.

Comment by Amit Kumar Gupta

2012-11-15T11:41:33Z

... because it says Con(ZFC + $\exists$ measurable)?

Comment by Amit Kumar Gupta

2012-11-15T11:40:58Z

I chose $\aleph_{\omega_1}$ because it's not regular. If $\lambda$ is singular then $\neg Cof(\lambda,\mathbb{P})$ holds trivially, since if $\lambda$ is singular, it can never be forced to be regular, by upwards absoluteness of singularity. Just so we're on the same page, do we agree that $Cof(\mathbb{P}, \lambda) \Leftrightarrow 1 \Vdash _{\mathbb{P}} \check{\lambda}$ regular, and that $\forall \alpha \in \lambda (cf(\alpha) < cf(\lambda)) \Leftrightarrow \lambda$ regular? Also does it make sense that "$1 \Vdash_{\mathbb{P}} \check{\lambda}$ measurable" has large cardinal strength...

Comment by Amit Kumar Gupta

2012-11-15T11:14:39Z

Also I'm not sure what the spirit of your bold question is. Trivially, "$\mathbb{P}$ forces $\lambda$ is measurable" has large cardinal strength.

Comment by Amit Kumar Gupta

2012-11-15T11:10:40Z

Let $\lambda = \aleph_{\omega_1}$ and let $\mathbb{P}$ be any forcing of size $\lambda^+$ which does nothing. Then the conjunction holds but $\lambda$ is clearly not measurable.

Comment by Amit Kumar Gupta

2012-11-15T11:07:59Z

Yes, the negation of $Cof(\mathbb{P}, \lambda)$ doesn't imply that $\lambda$ is not a cardinal, but I'm not sure why you're mentioning this. $Cof(\mathbb{P},\lambda)$ says that $\mathbb{P}$ forces (and hence preserves in this case) $\lambda$ to be a regular ordinal (and hence a cardinal in this case). The statement $\forall \alpha \in \lambda (cf(\alpha) < cf(\lambda))$ is a convoluted way of saying that $\lambda$ is a regular cardinal [since if $\lambda$ were not regular, then letting $\alpha = cf(\lambda)$ we'd get $cf(\lambda) = cf(cf(\lambda)) < cf(\lambda)$, contradiction].

Comment by Amit Kumar Gupta

2012-11-15T10:25:09Z

Being forced by a dense set and being forced by $1$ are equivalent, as long as your poset has a $1$. Your formalization of $Cof(\mathbb{P},\lambda)$ says that $\mathbb{P}$ forces (and hence preserves) that $\lambda$ is regular. That's not the same as $\forall \alpha \in \lambda (cf(\alpha) < \lambda)$, which is just always true: $cf(\alpha) \leq \alpha < \lambda$.