Weekend fun puzzle / experiment:

>>8285394
Your question is making me wish I had taken set theory.

The formulation of the statement is odd. You could just say
>Then there is a set [math] A \subset X [/math] such that [math] g[ Y - f[A] ] = X - A [/math].

Anyway, I'll start.

If g is surjective, then A={} works:
[math] g[ Y - f[A] ] = g[ Y - \{\} ] = g[ Y ] = X = X - \{\} = X - A [/math]

If f is surjective so that f(X)=Y, then A=X works:
[math] g[ Y - f[A| ] = g[ Y - f[X| ] = g[ Y - Y ] = g[ \{\} ] = \{\} = X - X = X - A [/math]
...

Anyway, my next idea would be to try and factor the functions into surjective and non-surjective part.
inb4 this needs the axiom of choice or whateva.
...

What else can we construct?
A=X-g[Y]
Then
[math] X - A = g[Y] = g[ Y - \{\} ] [/math]
so this works if
[math] f[X-g[Y]] = \{\} [/math]

>>8285539
Yep. The surjective case is clear. You are probably on the right track, but here's where the problems start to appear...

>>8285394
Is [math]\subset[/math] strict inclusion? If so, it fails when X and Y are empty sets. Or is the use of [math]\subseteq[/math] in one line and [math]\subset[/math] in another just due to taking them from different texts?

>>8285539
You have to show f (a) is a Subset of b and b is a subset of f (a).
You have to show g (y-b) is a subset of x-a and the converse. Then you're done.

>>8285755
It is, but it doesn't matter because the prop assumes X and Y are non empty.

File: tegaki.png (12KB, 800x600px) Image search: [Google]

12KB, 800x600px

>>8285795
I assume you are not OP?

>It is
I'm pretty sure it isn't. Counterexamples are easy if [math]\subset[/math] means strict inclusion.

>the prop assumes X and Y are non empty.
It doesn't say that anywhere, and there are other counterexamples. For example, X = {1,2}, Y = {3}, f(x) = 3, g(y) = 1. Since 2 is not in g(Y), it cannot be in g(Y-B) = X-A, and must be in A. Therefore f(2) = 3 is in B, and Y-B is empty. If Y-B is empty, so is X-A. Thus A=X and B=Y.

>>8285755
Uhm, OP here. Different texts, but assume they are the same. In fact, you can figure it out from counterexamples.

>>8285778
Cool story bro. The problem is trying to find A.

>>8285843
yep,
If A = X and B = Y
then X and Y are definitely not empty.
It could be the set containing the empty set, but not the empty set.
If A and B were empty, then X =/= A and Y =/= B because they wouldn't be subsets of each other.

It's impossible for X and Y to be empty, otherwise there's no way to proceed.

Define [math]T : X \to X[/math] by [math]T(S) = X - g(Y - f(S))[/math].
Let [math]C = \{ S \in \mathcal{P}(X) | S \subseteq T(S) \}[/math].
We will prove [math]A = \cup C[/math] and [math]B = f(A)[/math] satisfy the conditions.

First we show [math]A \subseteq T(A)[/math]:
[math]
A
\\ = \cup_{S \in C} S
\\ \subseteq \cup_{S \in C} T(S) \text{ [since each $S \subseteq T(S)$]}
\\ = \cup_{S \in C} (X - g(Y - f(S)))
\\ = X - \cap_{S \in C} g(Y - f(S))
\\ \subseteq X - g(\cap_{S \in C} (Y - f(S))) \text{ [since image of intersection $\subseteq$ intersection of images]}
\\ = X - g(Y - \cup_{S \in C} f(S))
\\ = X - g(Y - f(\cup_{S \in C} S))
\\ = T(A).
[/math]

It follows that [math]T(A) \subseteq T(T(A))[/math]:
[math]
A \subseteq T(A)
\\ f(A) \subseteq f(T(A))
\\ Y - f(A) \supseteq Y - f(T(A))
\\ g(Y - f(A)) \supseteq g(Y - f(T(A)))
\\ X - g(Y - f(A)) \subseteq X - g(Y - f(T(A)))
[/math]

Since [math]T(A)[/math] satisfies the condition to be in [math]C[/math], we have [math]T(A) \subseteq A[/math].

From [math]T(A) = A[/math], taking the complement of both sides, we find [math]g(Y - B) = X - A[/math].

>>8286286
Lol yeah, you proved and invoked the fixed point theorem.
I was fishing for another way, but perhaps that is the only path.

>>8286308
Well, I started by trying finite cases on paper, figuring out which points belonged to which group, and realized that what I was doing amounted to recursively applying S -> X - g(Y - f(S)). So that led naturally to that sort of solution for the general case.

>>8286326 cont.
Which is not to say that the A obtained that way is the unique solution (there are in some cases multiple solutions). But you can show that for any valid solution [math]A[/math], if [math]S \subseteq A[/math], then [math]T(S) \subseteq T(A) = A[/math], so things like [math]T(T(T(\emptyset)))[/math] necessarily have to be in the [math]A[/math] part. Similarly you can iterate [math]S \to Y - f(X - g(S))[/math] to find points that must be in [math]Y - B[/math].

>>8286326
It's a fair way of thinking, yeah.

>>8286341
I am somewhat spoiled because I already knew about the fixed point theorem of order-preserving functions. But it's good to know people can derive it from trial and error.

>>8285394
Can't you create A and B easily by dividing X and Y into connected graphs where f and g are the vertices? Then define AUB such that if AUB is to contain a member of one of these connected graphs then it must contain all the members of that connected graph. That makes it impossible for g(Y-B) =/= X-A because (Y-B) cannot be connected to A and X-A cannot be connected to B

File: tegaki.png (10KB, 800x600px) Image search: [Google]

10KB, 800x600px

>>8286879
No.

>>8285394
Where is this from?

>>8287591
>手書き