7
$\begingroup$

A cool way to formulate the axiom of choice (AC) is:

AC. For all sets $X$ and $Y$ and all predicates $P : X \times Y \rightarrow \rm\{True,False\}$, we have: $$(\forall x:X)(\exists y:Y)P(x,y) \rightarrow (\exists f : X \rightarrow Y)(\forall x:X)P(x,f(x))$$

Note the that converse is a theorem of ZF, modulo certain notational issues.

Anyway, what I find cool about formulating AC this way is that, okay, maybe its just me, but this formulation really "feels" like a principle of logic, as opposed to set theory. I mean, its just saying that we can commute an existential quantifier $(\exists y:Y)$ left across a universal quantifier $(\forall x:X)$ so long as we replace existential quantification over the elements of $Y$ with existential quantification over functions from $X$ into $Y.$ And sure, "function" is a set-theoretic concept; nonetheless, this feels very logical to me.

Question. Can the generalized continuum hypothesis also be formulated in a similar way, so that it too feels like a principle of logic?

Obviously this is pretty subjective, so lets lay down some ground rules.

  1. The axiom should be equivalent to the generalized continuum hypothesis over ZFC.
  2. It has to be two lines or fewer. No sprawling 4-page axioms, thank you very much!
  3. Use of concepts like "function" and "predicate" is good and desirable.
  4. Use of the concepts injection/surjection/bijection is moderately frowned upon.
  5. Completely disallowed: use of cardinality and/or cardinal numbers; use of ordinal numbers; mentioning $\mathbb{N}$ or $\omega$ or the words "finite" or "infinite."
$\endgroup$
11
  • $\begingroup$ I think you got the implication backwards there, chief. If for every $x$ there is some $y$ such that $P(x,y)$, then there is $f$ such that bla bla bla. $\endgroup$
    – Asaf Karagila
    Commented Aug 10, 2015 at 9:01
  • 1
    $\begingroup$ I also find it weird that you are asking to express a notion which is explicitly about cardinals and injective functions, without using cardinals at all and preferably without injective functions. I think that you also forgot the rule that the answer must be typed using only the left ring finger, while standing on one leg above a shark tank filled to the brim with sharks and sea wasps, while blindfolded. And any typo or backspace/delete press lowers you by 1 meter into the water. $\endgroup$
    – Asaf Karagila
    Commented Aug 10, 2015 at 9:04
  • $\begingroup$ (I should also add to my previous objection that while function is fairly understandably "logical", the entire point of the Lowenheim-Skolem theorems is that cardinality is not logical at all. So I really don't know how you expect this question to be answered.) $\endgroup$
    – Asaf Karagila
    Commented Aug 10, 2015 at 9:07
  • $\begingroup$ @AsafKaragila, I know; the original question said... "It is a theorem of ZF that... the converse is equivalent to AC." But anyway, I've rephrased it so hopefully it is clearer now. It isn't weird... think about it this way. Imagine we didn't know about the above formulation of AC. All we knew were the formulations: "Hausdorff's maximal principle", "Zorn's Lemma", "The Cardinal Numbers Are Totally Ordered," "The Cardinal Numbers Are Well-Ordered," and "Every Set Can Be Well-Ordered." $\endgroup$ Commented Aug 11, 2015 at 3:20
  • $\begingroup$ Well, then I might well ask a similar question about AC. You would say: "I find it weird that you are asking to express a notion (namely AC) which is explicitly about cardinals and posets well-orders, without using cardinals or posets or well-orders." But of course, its possible. $\endgroup$ Commented Aug 11, 2015 at 3:22

1 Answer 1

2
$\begingroup$

Certainly, the Continuum Hypothesis (simple or generalised) can be formulated in the language of pure second-order logic.

This is done explicitly in Stewart Shapiro's wonderful book on second-order logic, Foundations without Foundationalism: see pp. 105-106.

The full story is a bit too long to give here. But as a taster, you start off by essentially using Dedekind's definition of infinity, so that you define Inf(X), for $X$ a property, as

$$\exists f[\forall x\forall y(fx = fy \to x = y) \land \forall x(Xx \to Xfx) \land \exists y(Xy \land \forall x(Xx \to fx \neq y))].$$

Ok, the first clause of this imposes the requirement that $f$ is injective: but we have done this in purely logical terms, so that shouldn't look worrying to someone looking for logical principles!

Now we can carry on through a sequence of such definitions until you get to a sentence, still in the pure language of second-order logic, which formulates CH. Then with a bit more work we can go on to construct a sentence which expresses GCH. Further details are spelt out in Shapiro.

However, as Asaf rightly points out below, it is one thing to say that a statement can be formulated in the language of pure second-order logic, and another thing to say that it is a logical principle. And it is indeed a nice question what that actually means. Still, we can say this much: as Shapiro notes, on a standard account of the semantics of full second-order logic it turns out that either CH or NCH (a certain natural formulation of the falsity of the continuum hypothesis) must be a logical truth of full second-order logic. But here's the snag: we don't know which!

$\endgroup$
2
  • 1
    $\begingroup$ This is somewhat of cheating since in essence this is using injections, surjections and bijections, as well infinite sets. Even if implicitly. In any case, I don't see how this turns into a statement of the form "Whenever $X$ is infinite, there is no set strictly larger than $X$ and strictly smaller than $\mathcal P(X)$" without just writing that out. And it's not really "as a logical principle" (whatever that means). $\endgroup$
    – Asaf Karagila
    Commented Aug 10, 2015 at 11:09
  • $\begingroup$ Thanks, @Asaf: I read the question too quickly, and have added a para taking up your last point. (As to injections, etc, yes and no -- I wondered if the OP was thinking that talk about injections etc. carries more baggage than it does, so spelling things out as in the defn of Inf might sooth such worries.) $\endgroup$ Commented Aug 10, 2015 at 11:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .