[FOM] Simple and difficult

[Joe Shipman]

I don't understand why this is a ZFC issue. It is obviously equivalent to a simple pi^0_1 statement:

For all n, every nontrivial union-closed family S of subsets of {1,2,...,n} has a subfamily with nonempty intersection with at least half as many sets as S.

The notion of being a finite integer is easy to represent in ZFC, it's just a set on which the membership relation is a well-order and a reverse well-order.

If this is unsettled, I suppose it is simpler than the twin prime conjecture in the language of set theory, but more complicated in the language of arithmetic.

Harvey's statement that's equivalent to subtle cardinals looks even simpler to state in the language of set theory. The existence of an inaccessible is of comparable simplicity. All these require the notion of an injection or surjection, which must be constructed using something like Kuratowski ordered pairs. Is there any statement of set theory which doesn't require such machinery but is still plausibly independent?

-- JS

Sent from my iPhone

On Apr 5, 2013, at 1:20 PM, "Timothy Y. Chow" <tchow at alum.mit.edu> wrote:

Joe Shipman wrote:

> What's the shortest or simplest sentence you can come up with in the language of set theory that is either (1) not settled (2) provably not a theorem of ZFC if ZFC is consistent?

There's Frankl's union-closed sets conjecture.

http://en.wikipedia.org/wiki/Union-closed_sets_conjecture

One catch is that this conjecture involves the notion of a finite set, and expressing finiteness is a bit of a nuisance.  Maybe there's some way to get around this?

Once you can express finiteness, the conjecture is that if

1. S is finite;
2. if x is in S then x is finite;
3. S is different from {{}};
4. x in S and y in S implies x U y in S;

then there exists z and a surjection from A := {x in S : z in x} onto S\A.

Tim
_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom