1. ## Bounded Comprehension Principle

Using the Bounded Comprehension Principle, show that if x and y are sets then
so are:

a. $\displaystyle \{z:\forall w( w\epsilon z \rightarrow w\epsilon x) \}$

b. $\displaystyle \{w:\exists z( z\epsilon x \wedge w= y\cap z) \}$

c. $\displaystyle \{w:\exists z( z\epsilon x \wedge w= y\cup z) \}$

I'm just not sure the Bounded Comprehension Principle applies here... could someone explain this?

2. Let me try the first one:

$\displaystyle \{z:\forall w( w\epsilon z \rightarrow w\epsilon x) \}=\{ z\in P(x):\forall w( w\epsilon z \rightarrow w\epsilon x) \}=\{ z\in P(x):z=z\}=P(x)$

(to answer the question you only need the first equation)

3. I guess I wasn't clear in my description

You have to demonstrate that for all of the sets

4. Originally Posted by DrSteve
Let me try the first one:

$\displaystyle \{z:\forall w( w\epsilon z \rightarrow w\epsilon x) \}=\{ z\in P(x):\forall w( w\epsilon z \rightarrow w\epsilon x) \}=\{ z\in P(x):z=z\}=P(x)$

(to answer the question you only need the first equation)
What is P(x)? My definition of Bounded Comprehension is for every property phi(x) and every ordinal a, the set {x: rk(x) <a and phi(x)} exists at time a

5. P(x) is the Power Set of x, that is $\displaystyle P(x)=\{ A: A\subseteq X \}$.

Since x is a set, so is P(x) (by the power set axiom).

I realize that you need to do all of them. I did the first one to start you off. If you understand this one, then you should at least be able to attempt the other two. Give them a try, show your thoughts, and I'll help out if you get stuck.

6. I don't understand how this is using the bounded comprehension principle

7. The Comprehension schema $\displaystyle \{ x:\phi (x)\}$

Bounded Comprehension is $\displaystyle \{ x\in a:\phi (x)\}$ where $\displaystyle a$ is a set.

8. Originally Posted by DrSteve
The Comprehension schema $\displaystyle \{ x:\phi (x)\}$

Bounded Comprehension is $\displaystyle \{ x\in a:\phi (x)\}$ where $\displaystyle a$ is a set.
Bounded Comprehension is for every property $\displaystyle \phi(x)$ and every ordinal $\displaystyle \alpha$, the set $\displaystyle \{x: rk(x) < a \wedge \phi(x)\}$ exists at time $\displaystyle \alpha$

this is my definition and I'm not sure how it relates to yours

9. I've never heard that definition, but it is equivalent to the one I have given you. For example, if $\displaystyle x$ has rank $\displaystyle \alpha$, the rank of $\displaystyle P(x)$ can be expressed in terms of $\displaystyle \alpha$ (I think it has rank $\displaystyle \alpha +1$). Conversely you can find a bounding set for a collection of sets of rank less than a fixed ordinal.