User apostolos - MathOverflow

$\Pi_0^1$-weakly indescribable cardinals are exactly the regulars

2011-10-09T18:14:18Z

Hi,

I'm not sure if I should ask here or over at math.stackexchange.com, but I think here it's a bit more fitting. This question stems from a homework problem:

Definition:

Given some class of formulas $Q$ we call a cardinal $\kappa$ $Q$-weakly indescribable if for every $Q$-sentence $\phi$ and $R\subset\kappa$, $\langle\kappa,\in,R\rangle\models\phi$ implies that there is some $\alpha<\kappa$ such that $\langle\alpha,\in,R\cap\alpha\rangle\models\phi$.

Background:

The exercise asks to show that $\kappa$ is $\Pi_0^1$-weakly indescribable exactly when it is regular. One part (namely that a regular cardinal is $\Pi_0^1$-weakly indescribable) is easy, but I am unsure about the other direction. If we had $R\subset\kappa\times\kappa$ then it would be fairly easy to "code" the singularity of $\kappa$ into $R$, but I don't see how to do this when $R$ is a subset of $\kappa$. Of course, we have that $\kappa$ can be mapped injectively onto $\kappa\times\kappa$ but -at least to the best of my knowledge- that would require some form of inductive definition, which on principle uses functions, objects that do not exist when our universe is $\langle\kappa,\in,R\rangle$.

After giving it a lot of thought, I actually checked a paper by Levy ("The size of the indescribable cardinals") in which he uses binary predicates, and I also tried to find an old paper by Hanf and Scott ("Classifying inaccessible cardinals") but it turns out that the library threw away most of the Notices of AMS volumes when they moved to a smaller building.

So my question is:

Can we somehow define the bijection inside $\langle\kappa,\in,R\rangle$, or on? And if not is there some other way to prove this?

Thanks,

Disclosure: Even though this is formally homework, we are allowed to use that $R\subseteq\kappa\times\kappa$. Hence this is more of a personal question that arose from the fact that I got stuck on this for a long time.

Answer by Apostolos for How to decompose an infinite set into two isomorphic ones without choice?

2011-05-01T12:47:17Z

No it's not, you need to have at least some choice, for example that for every set $A$ we have $|A|+|A|=|A|$. For every cardinal $\kappa$, using ZFA with $\kappa^+$ atoms, you can create a permutation model where $AC_\kappa$ (and $DC_\kappa$) hold but there doesn't exist a derangement of the atoms. This of course is enough to show that the negation of what you are looking for is consistent relative to ZF since if what you state were true then you would be able to find a derangement for every set by sending each element of $B$ to its image through the bijection and every element of $C$ to its image through the inverse of the bijection.

The idea behind the construction is as follows: Let $\mathcal{G}$ be the group of permutations of the atoms $\mathcal{A}$ and let $\mathcal{F}$ be a normal filter of the group of the permutations of the atoms that is generated by the sets $\{\pi\in\mathcal{G} : \pi_{\upharpoonright E}=id\}$ where $E\subset\mathcal{A}$ and $|E|\leq\kappa$. Observe that this filter is $\kappa^+$-complete since $\kappa^+$ is regular.

Given a set $x$ inside the permutation model with size $\leq\kappa$ it's easy to see that you can find a support for its choice function (the union of the supports of the elements of $x$ plus the union of the supports of the images) and thus the function is inside the permutation model. On the other hand assume that a derangement of $\mathcal{A}$, $f$, is in the permutation model and let $E$ be its support. Then let $\pi$ be the identity on $E$ and for $a,b,c,d\in\mathcal{A}\setminus E$ such that $f(a)=b$ and $f(c)\neq d$ let $\pi(a)=c$ and $\pi(b)=d$ (and let the rest of $\pi$ be arbitrary). Then $\pi(f)=f$ but $\pi(f)(\pi(a))=\pi(f(a))=d\neq f(c)$, a contradiction.

Unfortunately I am unaware of how much choice exactly is needed.

Comment by Apostolos

2012-05-31T15:06:54Z

You can prove that reduction to the absurd is a valid method of proof in classical first order logic. You want to show that $T\cup\{\lnot\phi\}$ is contradictory if and only if $T\vdash\phi$. One direction is trivial. For the other assume that $T\cup\{\lnot\phi\}$ is contradictory, then by the principle of explosion we have $T\vdash\lnot\phi\to\phi$. It's easy to see that $(\lnot\phi\to\phi)\to\phi$ is a tautology hence $T\vdash\phi$.

Comment by Apostolos

2011-10-10T05:43:29Z

@Amit: Jech defines the well ordering of $(\kappa,\kappa)$ as "the order type of $\{(\alpha,\beta):(\alpha,\beta)<(\kappa,\kappa)\}$". My problem is how to define this when our universe is κ. Jech says that two well orders have the same order type when they are isomorphic. How could you say this when you don't have functions? I'm beginning to feel that I'm missing something obvious here. :(

Comment by Apostolos

2011-09-27T14:02:10Z

In Jech's book "The Axiom of Choice" it is stated that the Prime Ideal Theorem may fail while every infinite set has a non-trivial ultrafilter. The proof is the exercise 8.5 (I don't have time to sketch it right now, hence the comment).

Comment by Apostolos

2011-05-01T15:42:32Z

@Asaf: No I mean a permutation that leaves no element unmoved. Isn't this the right term to describe it?