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 𝑆∗: 𝑥∈𝑆∗ ↔ 𝑥∉𝑓(𝑥)?

enter image description here

  • 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?
    – user4894
    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?
    – user4894
    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?
    – user4894
    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.
    – user4894
    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
  • 1
    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.
    – user4894
    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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.