1
$\begingroup$

Well i've been having problems trying to prove that $\mathscr{P}(A) \subseteq\mathscr{P}(\mathscr{P}(A)) $ if $ A \subseteq \mathscr{P}(A)$ What i need is to get a proof by using quantifiers

  • 4
    Pick an element of the set on the left. By definition, it is a subset of $A$. By hypothesis, it is a subset of ${\mathcal P}(A)$. By definition, it belongs to the set on the right. Once you follow this, if you really need to "use quantifiers", all you need to do is to write all these statements formally.2012-02-29

2 Answers 2

1

Before I actually do the problem, we should at least think about what we are really trying to prove here. The problem can be translated into words to mean :

If $A$ is a transitive set, then $\mathcal{P}(A)$ is a transitive set. (assuming that our universe contains only sets)

Anyway, here is the proof:

Let $x\in \mathcal{P}(A)$, then by definition of the power set $x \subseteq A$. But by assumption $A\subseteq \mathcal{P}(A)$ thus we see that $x\subseteq A \subseteq \mathcal{P}(A)$ and so $x\in \mathcal{P}(\mathcal{P}(A))$

I'm not sure how detailed "proof by quantifiers" is perhaps something like

$$\forall x \in \mathcal{P}(A) (x\subseteq A) \land (A \subseteq \mathcal{P}(A)) \implies \forall x\in \mathcal{P}(A) (x\subseteq \mathcal{P}(A))$$

  • 1
    Yes, but the proof doesn't really use the fact that $A$ is transitive. Rather, $A \subseteq B$ implies $\mathscr{P} A \subseteq \mathscr{P} B$. It just so happens $B = \mathscr{P} A$ in this case.2012-02-29
  • 0
    I totally understand your proof, right now what i'm having problems with is to structure the proof using quantifiers from the scratch, because if i see your proof, you say $x\in \mathcal{P}(A)$, wich means that you're taking an arbitrary element to make the demostration, so then you don't need to worry about the universal quantifier. My problem is when to introduce that new variable to the demostration, in this case the quantifier is in the goal, but what about if it is on the givens of the problem?, what can i do in that case?, can i introduce a new variable just like that?2012-02-29
  • 0
    @Mayhem You do need the $\forall$ is you want to do it by quantifiers. The definition of $A\subseteq B$ is that $(\forall x\in A)\Rightarrow x\in B$, and you can think of $x$ as a dummy variable (like when you consider the integral $\int_0^a x^2 dx$ $x$ is bound which is the technical name)2012-03-01
1

$$X \subseteq Y \implies \mathscr{P}(X) \subseteq \mathscr{P}(Y)$$

take $x \in \mathscr{P}(X)$ so $x \subseteq X$ and since $X \subseteq Y$ then $x \subseteq Y$ so finaly $x \in \mathscr{P}(Y)$