Weekend fun puzzle / experiment:

This is the perfect kind of problem to troll people. Its statement can be understood by high school students or anyone who has learned about functions (that's in Math 001). It should be easy. But is it?
Here is where the experts will start to shake their heads knowingly, but I'm conducting an experiment to see if people, including & especially math majors, can solve it without already knowing the main lemma used in the proof. Maybe they can give a new solution too? Try your best, Veeky Forums.

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]

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

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?

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.

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

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.

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

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

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].

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

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.

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].

It's a fair way of thinking, yeah.

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.

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

No.

Where is this from?

>手書き