Question

True or False:
\( \overline{\overline A } \le \overline{\overline B } \implies \mathcal P \overline{\overline {(A) }} \le \mathcal P\overline{\overline{ (B)}} \)

Answer 1

@JamesJ Can you help me?

Answer 2

What does the double overline notation here mean?

Answer 3

cardinality

Answer 4

Well, what do you think? Write down an example or two.

Answer 5

Well it must be true

Answer 6

Yes

Answer 7

Like i am just unsure how to justify it

Answer 8

If A has cardinality less than or equal to the cardinality of B, then there exists a function

f : A --> B

which is 1:1 and potentially onto or not, (because if f were onto and not 1:1, then A would have cardinality greater than that of B.)

Now, given that, can you see how to proceed?

Answer 9

That is, by definition of the fact that the cardinality of A is leq than of B, there is such a function. That's what less cardinality means.

So far so good?

Answer 10

okk gotcha

Answer 11

Now what you want to do is construct a similar function F : P(A) --> P(B). Use the function f to construct the function F.

Answer 12

There's one obvious way to do it and it works.

Answer 13

well \( x \in A \text{ and } x \in P(A) \)

Answer 14

No, \( \{ x \} \in P(A) \)

Answer 15

ohhh ok Well A is a subset of P(A)

Answer 16

No, A is a member of P(A). P(A) is the set of all subsets of A. That is
\[ X \subset A \ \iff \ X \in P(A) \]

Answer 17

rigghhttt

Answer 18

So how would you define F : P(A) --> P(B) ?

Answer 19

not sure what u want

Answer 20

Let's go back to the beginning.

A and B are two sets. We say that A has cardinality less than or equal to that of cardinality of B if there is a 1:1 function

f : A --> B

I am going to write \( || . || \) for cardinality. Hence in symbols, \( ||A|| \leq ||B|| \).

Now, we want to show that we can find a 1:1 function

F : P(A) --> P(B)

If we can show there exists such a function F given that \( ||A|| \leq ||B|| \), then we're finished.

Answer 21

Well me show that elements in A are elements of P(A)

Answer 22

The way to do this is to construct the function F explicitly.

Hence given a subset \( X \subset A \), that is, \( X \) is a member of \( P(A) \), what is the definition of
\[ F(X) \]
?

Answer 23

P(B)

Answer 24

This statement "the elements in A are elements of P(A)" is false.

For instance, if A = {1, 2}, then what is P(A)? None of the members of P(A) are 1 or 2.

Answer 25

or a member of P(B)

Answer 26

Ya Same mistake as above ;|
I just get confused

Answer 27

Let's make this explicit with an example.

Suppose A = { 1, 2 } and B = { cat, dog, mouse }. What is an example of a 1:1 function
f : A --> B ?

Answer 28

SHI*****

Answer 29

Nope, that's the Cartesian product of A and B, A x B.

An example of a function A --> B would be
f(1) = dog
f(2) = cat

Answer 30

right ok so then its not onto

Answer 31

No, but it's 1:1 because f(1) and f(2) have different values.

Answer 32

right

Answer 33

Ok. We are starting still with
A = { 1, 2 } and B = { cat, dog, mouse }

Write down for me the power set of A, P(A).

Answer 34

{(1,2)(1)(2)}

Answer 35

and the emptyset

Answer 36

The power set of A is all the subsets of A. The subsets are
\[ \emptyset \]
\[ \{ 1 \}, \{ 2 \} \]
\[ A = \{ 1, 2 \} \]

Hence
\[ P(A) = \{ \emptyset, \{ 1 \}, \{ 2 \}, A \} \]

Answer 37

yaaaaaaa

Answer 38

So, given our function f : A --> B, what do you think would be a sensible definition for
F : P(A) --> P(B) ?

Answer 39

Maybe write it out explicitly first. We started with this:
An example of a function A --> B would be
f(1) = dog
f(2) = cat

Answer 40

Well the power sets are all the subsets of that original set. Now if \( A \leq B \) Then A will have less or equal amount of subsets than B

Answer 41

That's what we want to prove.

So here's one way to do it. Define F this way
\[ F(\emptyset) = \emptyset \]
\[ F(\{ 1 \}) = \{ f(1) \} = \{ dog \} \]
\[ F(\{ 2 \}) = \{ f(2) \} = \{ cat \} \]
\[ F(A) = F(\{ 1, 2 \}) = \{ f(1), f(2) \} = \{ dog, cat \} \]

Answer 42

F is clearly a function from P(A) to P(B). The "from" part is clear; the "to" part is true because
\[ \emptyset, \{ dog \}, \{ cat \}, \{ dog, cat \} \]
are all subsets of B = {dog, cat, mouse }

Answer 43

yayyyyyyyyyyyyy

Answer 44

Now, is F one-to-one? yes, because if it were not 1:1, then you can show that this would imply f is not 1:1, which it is.

Answer 45

Does this example make sense?

Answer 46

Yes it really clarified everything. I was getting so confused there

Answer 47

U shld write a math textbook

Answer 48

that sounds like a great way to not make a lot of money ;-)

Answer 49

ok, going to help someone else now.

Answer 50

Thannkkkssssssssssss

Answer 51

Its great to see u on