A367901 - OEIS

A367901

Number of sets of subsets of {1..n} contradicting a strict version of the axiom of choice.

1, 2, 9, 195, 63765, 4294780073, 18446744073639513336, 340282366920938463463374607341656713953, 115792089237316195423570985008687907853269984665640564039457583610129753447747

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

COMMENTS

The axiom of choice says that, given any set of nonempty sets Y, it is possible to choose a set containing an element from each. The strict version requires this set to have the same cardinality as Y, meaning no element is chosen more than once.

LINKS

Table of n, a(n) for n=0..8.

Wikipedia, Axiom of choice.

FORMULA

a(n) = 2^2^n - A367902(n). - Christian Sievers, Aug 01 2024

EXAMPLE

The a(2) = 9 sets of sets:

{{}}

{{},{1}}

{{},{2}}

{{},{1,2}}

{{},{1},{2}}

{{},{1},{1,2}}

{{},{2},{1,2}}

{{1},{2},{1,2}}

{{},{1},{2},{1,2}}

MATHEMATICA

Table[Length[Select[Subsets[Subsets[Range[n]]], Select[Tuples[#], UnsameQ@@#&]=={}&]], {n, 0, 3}]

CROSSREFS

The version for simple graphs is A367867, covering A367868.

The complement is counted by A367902, no singletons A367770, ranks A367906.

The version without empty edges is A367903, ranks A367907.

For a unique choice (instead of none) we have A367904, ranks A367908.

A000372 counts antichains, covering A006126, nonempty A014466.

A003465 counts covering set-systems, unlabeled A055621.

A058891 counts set-systems, unlabeled A000612.

A059201 counts covering T_0 set-systems.

A323818 counts covering connected set-systems, unlabeled A323819.

A326031 gives weight of the set-system with BII-number n.

Cf. A007716, A083323, A092918, A102896, A283877, A306445, A355739, A355740, A367769, A367862, A367905.

Sequence in context: A041795 A123625 A216692 * A069649 A111832 A114563

Adjacent sequences: A367898 A367899 A367900 * A367902 A367903 A367904

KEYWORD

nonn

AUTHOR

Gus Wiseman, Dec 05 2023

EXTENSIONS

a(5)-a(8) from Christian Sievers, Aug 01 2024

STATUS

approved