# Bounded Comprehension Principle

• Jan 19th 2011, 02:14 PM
gutnedawg
Bounded Comprehension Principle
Using the Bounded Comprehension Principle, show that if x and y are sets then
so are:

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

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

c. $\{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?
• Jan 19th 2011, 03:58 PM
DrSteve
Let me try the first one:

$\{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)
• Jan 19th 2011, 04:43 PM
gutnedawg
I guess I wasn't clear in my description

You have to demonstrate that for all of the sets
• Jan 19th 2011, 04:54 PM
gutnedawg
Quote:

Originally Posted by DrSteve
Let me try the first one:

$\{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
• Jan 19th 2011, 07:20 PM
DrSteve
P(x) is the Power Set of x, that is $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.
• Jan 19th 2011, 07:25 PM
gutnedawg
I don't understand how this is using the bounded comprehension principle
• Jan 19th 2011, 07:35 PM
DrSteve
The Comprehension schema $\{ x:\phi (x)\}$

Bounded Comprehension is $\{ x\in a:\phi (x)\}$ where $a$ is a set.
• Jan 19th 2011, 08:09 PM
gutnedawg
Quote:

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

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

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

this is my definition and I'm not sure how it relates to yours
• Jan 19th 2011, 08:39 PM
DrSteve
I've never heard that definition, but it is equivalent to the one I have given you. For example, if $x$ has rank $\alpha$, the rank of $P(x)$ can be expressed in terms of $\alpha$ (I think it has rank $\alpha +1$). Conversely you can find a bounding set for a collection of sets of rank less than a fixed ordinal.