Question

Let \(X\) be a set and consider the function, \(\alpha : \mathcal P \left({X}\right) \rightarrow \mathcal P \left({X}\right)\) such that for all \(S \in \mathcal P \left({X}\right), \alpha (S )= X \backslash S\). Show that \(\alpha\) is a bijection. What is \(( \alpha \circ \alpha) (S)\) for any \(S \in \mathcal P \left({X}\right)?\)

Answer 1

WHERE DO I BEGIN BESIDES REALIZING THAT it's a surjection and an injection.

Answer 2

so it's a surjection which means that every element of the codomain has at least one preimage

Answer 3

and for a surjection for all values of x1 and x2 belonging in X, x1 doesn't equal to x2 and that implies that the f(x1) doesn't equal to f(x2)

Answer 4

injection is a one-to-one function

Answer 5

all I know is the complement part.. we have x that belongs to X, but not S

Answer 6

So\[
a(S) = X\setminus S
\]

Answer 7

Let \(X\) be a set and consider the function, \(\alpha : \mathcal P \left({X}\right) \rightarrow \mathcal P \left({X}\right)\) such that for all \(S \in \mathcal P \left({X}\right), \alpha S = X \backslash S\). Show that \(\alpha\) is a bijection. What is \(( \alpha \circ \alpha) (S)\) for any \(S \in \mathcal P \left({X}\right)?\)

Answer 8

I BROKE THE QUESTION FMLLLl

Answer 9

yes @wio

Answer 10

Well \((\alpha \circ \alpha )(S) = X\setminus (X\setminus S)= S\)

Answer 11

So it is its own inverse.

Answer 12

yes but how to prove that... ?!

Answer 13

or is it a one liner proof?

Answer 14

It's really a matter of how much rigor they really want here.

Answer 15

let's make it as simple as it can get

Answer 16

Let's see.... For any S, we want to show there is only one \(X\setminus S\)

Answer 17

yeah.. . ... but what a sec by complement def we have an x in X but not in S

Answer 18

That much is certain. But then we need to show that for any \(X\setminus S\) there is only one corresponding \(S\).

Answer 19

Since it is so obvious, a proof by contradiction might be easiest.

Answer 20

If it isn't a bijective function, then that would mean \(X\setminus S\) doesn't exist, or there are two of them.

Answer 21

two X's?

Answer 22

wait where is the contradiction part.. like we say that the alpha isn't a bijection... so it's not an injection or surjection... no preimage..

Answer 23

Either not an injection, or not a surjection

Answer 24

Again, it is hard to say how much rigor is required here.

Answer 25

Is there a precise definition of injection or surjection we can start off with?

Answer 26

yeah there is

Answer 27

wait let me latex it and get it back here

Answer 28

A function \(f(x) X \rightarrow Y\) with the property \((\forall Y \in Y)( \exists X \in X ) [f(x) = y ]\) is a surjection of \(X\) onto \(Y\).

Answer 29

you ever use the open study quoting feature?

Answer 30

no

Answer 31

If lets you do this :\(\color{blue}{\text{Originally Posted by}}\) @UsukiDoll
A function \(f(x) X \rightarrow Y\) with the property \((\forall Y \in Y)( \exists X \in X ) [f(x) = y ]\) is a surjection of \(X\) onto \(Y\).
\(\color{blue}{\text{End of Quote}}\)

Answer 32

Make multi-latex posts easier to edit.

Answer 33

A function \(f: X \rightarrow Y\) with the property \( \forall x_1, x_2 \in X)[ x_1 \neq x_2] \rightarrow f(x_1) \neq f(x_2)\) is an injection of \(X\) into \(Y\)

Answer 34

the injection is one to one

Answer 35

Okay, for surjection, it is easy.

Answer 36

alright so the surjection in addition to what I wrote says that every element of the codomain has at least one preimage

Answer 37

so the negation would be that there isn't a preimage for every element of the codomain

Answer 38

In our case, the definition changes to be:\[
\forall T\in \mathcal P(X) \ \exists S\in \mathcal P(X)[X\setminus S = T]
\]

Answer 39

We need to prove this is true.

Answer 40

for all T in a power set X there is an S belonging to a power set x ... so x = t

Answer 41

For all set T that are subsets of X, there is a set S subset of X which is basically the complement.

Answer 42

damn if only I could translate these things better... at least I know the symbols... so the complement..we need to prove that

Answer 43

gahhhh! err there's a composite function too which is alpha dot alpha OH! that's like the composite of itself like you know g o g means put your g function inside g. so the alpha function is put inside its self and then oh dang I have no idea what's next .

Answer 44

and there's power sets too.

Answer 45

alright... so our goal is to prove by contradiction that this stupid thing isn't a bijection which means that's it's not a surjection (1 to 1) and an injection (no element has a preimage)... NOW WHERE TO BEGIN ROFL!

Answer 46

We don't need to actually prove a contradiction. We can do a direct proof since we have this definition.

Answer 47

ooo

Answer 48

what is all this mumbo jumbo

Answer 49

discrete math @dan815 hop in

Answer 50

except this is proving functions.. s(*(*(#)@* . Makes set theory and induction look easy

Answer 51

First, can we start with: \[
\forall T\in \mathcal P(X)\ \exists S\in \mathcal P(x)\quad X\setminus T = S
\]We're just saying there is a subset in \(X\) that is complement for \(T\).

Answer 52

xcool is there an MIT course on it!

Answer 53

so for all T belonging in a power set X, there is some S belonging in a power set X such that the complement of X has an S?!

Answer 54

We are just saying that every T has an complement.

Answer 55

and that complement is also a subset of the universal set X.

Answer 56

alright so it belongs to a universal set X

Answer 57

Actually, don't even worry about complements. Let's just say you can take the set difference from X and a subset T, and the result is a subset S

Answer 58

We can start out even more basic.

Answer 59

We can start with the premise that set minus will yield a result:\[
\forall T\in\mathcal P(X) \quad X\setminus T=S
\]We know that \(S\) is in \(\mathcal P(X)\) because it must be a subset of \(X\).
This allows us to add \(\exists S\in \mathcal P(X)\).

Answer 60

Next thing we do is complement both sides\[
\forall T\in\mathcal P(X)\ \exists S\in\mathcal P(S) \quad (X\setminus T)^C=S^C
\]Then intersect them both with \(X\)\[

\forall T\in\mathcal P(X)\ \exists S\in\mathcal P(S) \quad X\cap (X\setminus T)^C=X\cap S^C
\]

Answer 61

We can simplify \(X\cap S^C\) to be \(X\setminus S\).

Answer 62

huh where did you get the X cap...?! on the left side... I know that for the X\T there's a set property

Answer 63

It turns out that \[X\cap(X\setminus T)^C = X\cap(X\cap T^C)^C= X\cap(X^C\cup T)= (X\cap X^C)\cup (X\cap T)= T\]

Answer 64

This gives us \[

\forall T\in\mathcal P(X)\ \exists S\in\mathcal P(S) \quad T=X\setminus S
\]Which proves we have a surjection.

Answer 65

what about for injection? .-. is it easy to prove or not?

Answer 66

that one is maybe a candidate for direct or contrapositive.

Answer 67

let's try contrapositive

Answer 68

\[
X\setminus S_1 = X\setminus S_2\implies S_1=S_2
\]

Answer 69

You would have to prove this.

Answer 70

It would work the same way. Start with \(X\setminus S_1 = X\setminus S_2\) and then you do \(^C\) and \(X\cap\) to both sides.

Answer 71

k I'll finish this when I wake up...super sleepy.

Answer 72

did some reading and practices earlier... energy went need sleep

Answer 73

uh oh. I got all the way to \[(X \cap X^C) \cup ( X \cap T) = T\]
there's a law that's written as \[X \cup \emptyset = X \]
that leaves
\[X \cup (X \cap T)\]
if I use idempotent law \[X \cup X = X \]
I'll have \[X \cap T\]... how do I get the T to be single for surjection ?

Answer 74

wrong law.. I meant. \[X \cap X^c = \emptyset\]

Answer 75

\[\emptyset \cup (X \cap T)\]

Answer 76

\[X\cup \emptyset = X\] identity law
\[X \cap T \]

Answer 77

Since \(T\subseteq X\) we know that \(T\cap X = T\)

Answer 78

Since\(X\) has all the elements that \(T\) has, we know the intersection will not take away any elements from \(T\)

Answer 79

Suppose \(\alpha\) is an injection.

Definition 5.4.5 states that a function \(f: X \rightarrow Y\) with the property \( \forall x_1, x_2 \in X)[ x_1 \neq x_2] \rightarrow f(x_1) \neq f(x_2)\) is an injection of \(X\) into \(Y\)\\


\(X \setminus S_1 = X\setminus S_2 \rightarrow s_1=s_2\) \\

By complementing both sides, we have:\\

\((X \setminus S_1)^C = (X\setminus S_2)^C \rightarrow (s_1)^C=(s_2)^C\)\\

Then, we intersect both of them with \(X\). \\

\(X \cap (X \setminus S_1)^C = X \cap (X\setminus S_2)^C \rightarrow X \cap (s_1)^C= X \cap(s_2)^C\)\\

Answer 80

\[X \cap (X \cap s_1^c)^c\]

Answer 81

\[X \cap (X^c \cup S_1)\]

Answer 82

You can't prove it by supposing it is true.

Answer 83

O_)OSDApf

Answer 84

\[X \cap X^c \cup X \cap S_1\]

Answer 85

\[\emptyset \cup X \cap S_1\]

Answer 86

\[X \cap S_1\]

Answer 87

When you use the contrapositive, you are changing what you have to prove, you are not assuming that it is true.

Answer 88

Since you a proving a conditional statement, then you get to assume the antecedent is true and then show through a direct proof that the consequent must also be true.

Answer 89

In this case, we start by assuming that \[
X\setminus S_1 = X\setminus S_2
\]is true, and then show that we arrive at \[
S_1=S_2
\]must be true.

Answer 90

oops ._.

Answer 91

but that's by complementing and intersecting both sides right?

Answer 92

Yes.

Answer 93

The point is, you have to prove the conditional relationships, and can't start out on the premise that it is true.

Answer 94

so suppose it's not an injection?!

Answer 95

then do the complement and intersection things as usual.... but would mean that alpha isn't a bijection after all.

Answer 96

Make no assumptions.

Answer 97

Only assume \(X\setminus S_1=X\setminus S_2\)