# Can we define this set?

1. Given an infinite set S in some universe U, construct the set of complementary pairs C: {{A,Ac}} where A,Ac∈P(U), the power set of U, and A or Ac is contained in S, not necessarily a proper subset of S. C is the image of a choice function on the set of all two-part partitions of U.
2. Assume a choice function g:C→P(U), g = {({A,Ac },B), B∈P(U))} that selects an arbitrary element B from {A,Ac}.
3. C':=g(C), g({A,Ac}) = B∈P(U), C'={B}.
4. There exists a bijection h:C'→P(S), since elements of C' are either an element of P(S) or its complement in U, and each element of P(S) has a unique complement in U. So let h={(B,D), B∈C', D∈P(S), D an arbitrary element of P(S)}.
5. Assume there exists k:S→C', k(x) = B∈C' , so k={(x,B), x∈S, B∈C'}.
6. Define a function f:S→P(S), f(x) = h(k(x)), f = {(x,D), x∈S, D∈P(S)}.
7. Can we define 𝑆∗: 𝑥∈𝑆∗ ↔ 𝑥∉𝑓(𝑥)? • Step 5 isn't well defined. Where did c come from, and how does it relate to x ? Oct 31 '18 at 3:47
• I have a little problem with (2) but it may be trivial. C is a set of pairs (A, Ac). So g inputs the pair (A, Ac) and outputs either A or Ac. So g: C→ 𝑃(𝑆). The target set is 𝑃(𝑆, not U. Do I have that right? And does it make any difference to the rest of your idea? Oct 31 '18 at 4:59
• Also in (3) what does g(C) mean? g inputs elements of C. The notation g(C) can only be the image of C by g, meaning the entire set of outputs as g ranges over the elements of C. This image is clearly is 𝑃(𝑆). Am I missing something? Oct 31 '18 at 5:01
• In (4), C' is more than bijective to 𝑃(𝑆). C' = 𝑃(𝑆). They're the same set. Yes? Again am I missing something? Oct 31 '18 at 5:04
• (5) says k is a function from S to 𝑃(𝑆), since I've convinced myself that C' = 𝑃(𝑆). Then h is just the identity function, so f = k. (7) is just the last step of Cantor's theorem. We can certainly define S* as a subset of S, but assuming that S* gets hit by f leads to a contradiction, so f is not a surjection. This is all just a highly convoluted version of the proof of Cantor's theorem that there's no surjection from a set to its powerset. If I am following correctly. Oct 31 '18 at 5:13

1. Given a set 𝑆 in some universe 𝑈, construct the set of complementary pairs 𝐶: {(𝐴,𝐴𝑐)} where 𝐴∈𝑃(𝑆), the power set of 𝑆, and 𝐴𝑐 is the complement of 𝐴 in 𝑈.

For an example, let U = {0, 1, 2} and S={0,1} . (Check: S ⊆ U okay.)

Then we have P(S)={{},{0},{1},{0,1}} and C={({},{0,1,2}), ({0},{1,2}), ({1},{0,2}), ({0,1},{2})}

C ⊆ P(S) × P(U)

1. Assume a choice function 𝑔:𝐶 → 𝑈 that selects an arbitrary element (either 𝐴 or 𝐴𝑐) from each pair.

Not quite. Each pair consists of two subsets of U, not elements of U. That selection would be g:C → P(U)

As we have a arbitrary g, Let us take, for instance, g={(({},{0,1,2}),{}), (({0},{1,2}),{0}), (({1},{0,2}),{0,2}), (({0,1},{2}),{2})}

1. Let 𝑔(𝐶) = 𝐶′.

I think you are trying to define C' to be the g image of C. Let C' := g(C)

For our example, C'={{},{0},{0,2},{2}} and generally C' ⊆ P(U)

1. There exists a bijection ℎ:𝐶′ → 𝑃(𝑆), since elements of 𝐶′ are either an element of 𝑃(𝑆) or its complement in 𝑈, and each element of 𝑃(𝑆) has a unique complement in 𝑈.

Yes. For every element c in C' there is a one-to-one correspondance with a subset s of S since c = s or c = sᶜ . Warning: That is only the case as long as S is a proper subset of U ; to avoid the complements also being subsets of S.

Then in fact h = {(c,x)∈ C'×P(S): c=x or c=xᶜ} , the function which returns the subset of S corresponding to the element of C'. Also h ={(c,x)∈ C'×P(S): c=g(x,xᶜ)}

1. Assume there exists 𝑘:𝑆 → 𝐶′, 𝑘(𝑥) = 𝑐 ∈ 𝐶′.

This is not well defined. You seem to want k: P(S) → C' , k(x) = g(x, xᶜ)

In fact k = {(x,c)∈ P(S)×C' : c=g(x,xᶜ)}

1. Define a function 𝑓:𝑆 → 𝑃(𝑆), 𝑓(𝑥) = ℎ(𝑘(𝑥)).

Uh... h(k(x))=x... and since it is the identity function for P(S), we have f:P(S)→P(S).

Can we define 𝑆∗: 𝑥∈𝑆∗ ↔ 𝑥∉𝑓(𝑥)?

... That would be S*={x∈P(S): x∉x} which means S* is actualy P(S)

• Graham Kemp- I am sorry, I failed to specify at the start that I was making reference via S to an infinite set. I have edited the post to say so. When I reference U, I am thinking of U as the universe of sets whose elements are sets. Nov 3 '18 at 13:57
• Graham Kemp- I put together a paper - notes from thinking about my question myopenmaths3.s3.amazonaws.com/ufiles/85516/alternation_3.pdf Nov 3 '18 at 14:43
• Graham Kemp - h maps sets to sets, let me consider your note elated to h Nov 3 '18 at 15:02
• Graham Kemp - did you man to type s where you typed x in notes under 4.? Nov 3 '18 at 15:09
• When you say U is the universe of sets, do you mean the proper class of sets? So that U is not necessarily a set? Trying to understand your post now that I realize the complements are taken with respect to U. But that's very problematic because those complements are not necessarily sets. If you take S = the primes, the complement in the reals is all real numbers that aren't primes. That's a set. But the complement of the integers in the proper class of sets is every set that's not the positive integers. That's not a set. Am I understanding? If so, the complement is a set if and only if U is. Nov 4 '18 at 5:45

S * is a well defined subset of S determined by the functions g, h, and k. However, it may be induced by a single function f : SP(S) without any other reference, not even to U. S * (f) = {xS | xf(x)}.

To see why this is the case, let C be P(S) x {0,1}. Let g : P(S) → {0,1}. Let h be any bijection P(S) → P(S). Let k : SP(S).

We define C and g in this way to simplify the problem. We may take (A, 0) to denote A and (A, 1) to denote U-A.

Then letting xS, we can see a series of transformations that parallels the process the poster describes:

x to (k(x), g(k(x))) = y to h(π_1(y)) = h(k(x)) = f(x). Or simply x to f(x).

Note that the function g does not influence f at all. Also, composition with a bijection can simply be thought of as a single function.

Below is an in-depth look at the the process the poster described.

1. I am assuming U is a set and not a proper class based on a comment I saw by the poster. Then we let S be a proper subset (proper by the same comment) of U. We then define C = {{A, A^c} ⊂ P(U) | AS}.

2. Let g : CP(U) be a choice function. That is for all AS, g({A, U-A}) ∈ {A, U-A}. Note that we do not need to assume that one exists due to the fact that g' given by g'({A, U-A}) = A for all AS is an explicit choice function (from CP(S) ⊂ P(U)). Furthermore, any choice function is injective. Suppose g({A, U-A}) = g({A', U-A'}). Then A = A', A = U-A', U-A = A', or U-A = U-A'. In any case, we have that {A, U-A} = {A', U-A'}. We can then talk about g^(-1) : g(C) → C, which is also injective.

3. I will simply use g(C) (= {BU | there exists an AS such that g(A) = B}) in my notation.

4. There exists a bijection from g(C) → P(S). Let Bg(C). Note that g'(g^(-1)(B)) = B if BS and U-B if U-BS. This is a composition of injective functions and is therefore injective. Now the surjectivity of g'∘g^(-1) comes from the fact that for every pair of elements A, A' ∈ P(S), {A, U-A} = {A', U-A'} implies that A = A' since S is a proper subset of U.

5. Again, we need not assume that such a function k : Sg(C) exists. In fact, k' given by k'(x) = g({{x}, U-{x}}) for all xS is an explicit (injective) function.

6. I will simply use hk : SP(S) in my notation.

7. Let S * = {xS | x ∉ (hk)(x)}. This is well defined because S, g, h, and k are all well-defined.