228k views
3 votes
Help please iam stuck

Help please iam stuck-example-1
User Rohitanand
by
5.7k points

1 Answer

2 votes

This is more interesting than the usual stuff.

Prove P(A) ⊆ P(B) ↔ A ⊆ B

It's an if and only if, we'll do → first. Show P(A) ⊆ P(B) → A ⊆ B

Let's assume it's false; We have A⊄B and P(A) ⊆ P(B).

A⊄B means there's an element a∈A such that a∉B. So the singleton subset {a} must be in the powerset of A,

{a} ∈ P(A)

Since P(A) ⊆ P(B) it follows {a} ⊆ P(B)

But that can't possibly be true because a∉B. We found our contradication, so we must have P(A) ⊆ P(B) → A ⊆ B.

← next. Show A ⊆ B → P(A) ⊆ P(B)

Again we'll assume it's false, assume A ⊆ B and P(A) ⊄ P(B)

Since P(A) ⊄ P(B) there must be at least one set S∈P(A) and S∉P(B).

S can't be the empty set because the empty set is in every power set; it's a subset of every set. So S has at least one element, and all the elements must have come from A.

S ≠ ∅

a∈S → a∈A

Since S∉P(B) that means there exists at least one element, let's call it a, such that a is in S but not in B.

a∈S and a∉B

So a∈A and a∉B, contradicting A ⊆ B. We conclude A ⊆ B → P(A) ⊆ P(B).

That proves both ways.

User AntiElephant
by
5.6k points