Skip to main content
added 185 characters in body
Source Link
Asaf Karagila
  • 39.9k
  • 8
  • 135
  • 283

This is a delicate issue, because antichains break easily when you're not using the axiom of choice.

More to the point, it is consistent that there is a partial order which satisfies the countable chain condition, simply because every antichain is finite and there are no infinite maximal antichains. In other partial orders there might not be maximal antichains at all.

While we're at it, the maximality principle in forcing is equivalent to the axiom of choice, so that one fails to (I mean the fact that $p\Vdash\exists\tau\varphi(\tau)\iff \exists\dot\tau\ p\Vdash\varphi(\dot\tau)$ which is often used in forcing).

Moreover, in peculiar forcings as I mentioned above it is generally expected for the maximality principle to fail. Making this a double-trouble problem.

But then again, not all is lost. As Mohammad points out, the cardinality of the forcing poset is an upper bound. And that upper bound works out for every function, and every two sets in the ground model. While this is not necessarily an $\aleph$ number, it is still an upper bound in some sense.

If $1_P\Vdash\dot f\colon\check A\to\check B$, then every condition must agree that $\dot f$ is a name for a function. Therefore if $p\Vdash\dot f(\check a)=\check b$, then this $b$ is unique. So if we define $F(a)=\{b\in B\mid\exists p\ p\Vdash\dot f(\check a)=\check b\}$, then there is a surjection from $P$ onto $F(a)$, if $p$ doesn't decide the value of $\dot f(\check a)$ then map it to some fixed element; otherwise map it to the value it decided upon.

Of course, in the absence of choice, the existence of a surjection need not imply the existence of an injection, so if you want an upper bound in the sense of injections ($\leq$) rather than surjections ($\leq^*$) you need to consider $2^P$ instead.

The above can be circumvented if $P$ is already a complete Boolean algebra. In that case we define an injection from $F(a)$ into $P$ defined by $b\mapsto\sum\{p\mid p\Vdash\dot f(\check a)=\check b\}$. Since $P$ is a complete Boolean algebra this condition exists, and it is unique. As Andreas Blass points out, in the case of a complete Boolean algebra which satisfy c.c.c. the different values of $\dot f(\check a)$ form an antichain, which is therefore countable.

This is a delicate issue, because antichains break easily when you're not using the axiom of choice.

More to the point, it is consistent that there is a partial order which satisfies the countable chain condition, simply because every antichain is finite and there are no infinite maximal antichains. In other partial orders there might not be maximal antichains at all.

While we're at it, the maximality principle in forcing is equivalent to the axiom of choice, so that one fails to (I mean the fact that $p\Vdash\exists\tau\varphi(\tau)\iff \exists\dot\tau\ p\Vdash\varphi(\dot\tau)$ which is often used in forcing).

Moreover, in peculiar forcings as I mentioned above it is generally expected for the maximality principle to fail. Making this a double-trouble problem.

But then again, not all is lost. As Mohammad points out, the cardinality of the forcing poset is an upper bound. And that upper bound works out for every function, and every two sets in the ground model. While this is not necessarily an $\aleph$ number, it is still an upper bound in some sense.

If $1_P\Vdash\dot f\colon\check A\to\check B$, then every condition must agree that $\dot f$ is a name for a function. Therefore if $p\Vdash\dot f(\check a)=\check b$, then this $b$ is unique. So if we define $F(a)=\{b\in B\mid\exists p\ p\Vdash\dot f(\check a)=\check b\}$, then there is a surjection from $P$ onto $F(a)$, if $p$ doesn't decide the value of $\dot f(\check a)$ then map it to some fixed element; otherwise map it to the value it decided upon.

Of course, in the absence of choice, the existence of a surjection need not imply the existence of an injection, so if you want an upper bound in the sense of injections ($\leq$) rather than surjections ($\leq^*$) you need to consider $2^P$ instead.

The above can be circumvented if $P$ is already a complete Boolean algebra. In that case we define an injection from $F(a)$ into $P$ defined by $b\mapsto\sum\{p\mid p\Vdash\dot f(\check a)=\check b\}$. Since $P$ is a complete Boolean algebra this condition exists, and it is unique.

This is a delicate issue, because antichains break easily when you're not using the axiom of choice.

More to the point, it is consistent that there is a partial order which satisfies the countable chain condition, simply because every antichain is finite and there are no infinite maximal antichains. In other partial orders there might not be maximal antichains at all.

While we're at it, the maximality principle in forcing is equivalent to the axiom of choice, so that one fails to (I mean the fact that $p\Vdash\exists\tau\varphi(\tau)\iff \exists\dot\tau\ p\Vdash\varphi(\dot\tau)$ which is often used in forcing).

Moreover, in peculiar forcings as I mentioned above it is generally expected for the maximality principle to fail. Making this a double-trouble problem.

But then again, not all is lost. As Mohammad points out, the cardinality of the forcing poset is an upper bound. And that upper bound works out for every function, and every two sets in the ground model. While this is not necessarily an $\aleph$ number, it is still an upper bound in some sense.

If $1_P\Vdash\dot f\colon\check A\to\check B$, then every condition must agree that $\dot f$ is a name for a function. Therefore if $p\Vdash\dot f(\check a)=\check b$, then this $b$ is unique. So if we define $F(a)=\{b\in B\mid\exists p\ p\Vdash\dot f(\check a)=\check b\}$, then there is a surjection from $P$ onto $F(a)$, if $p$ doesn't decide the value of $\dot f(\check a)$ then map it to some fixed element; otherwise map it to the value it decided upon.

Of course, in the absence of choice, the existence of a surjection need not imply the existence of an injection, so if you want an upper bound in the sense of injections ($\leq$) rather than surjections ($\leq^*$) you need to consider $2^P$ instead.

The above can be circumvented if $P$ is already a complete Boolean algebra. In that case we define an injection from $F(a)$ into $P$ defined by $b\mapsto\sum\{p\mid p\Vdash\dot f(\check a)=\check b\}$. Since $P$ is a complete Boolean algebra this condition exists, and it is unique. As Andreas Blass points out, in the case of a complete Boolean algebra which satisfy c.c.c. the different values of $\dot f(\check a)$ form an antichain, which is therefore countable.

Source Link
Asaf Karagila
  • 39.9k
  • 8
  • 135
  • 283

This is a delicate issue, because antichains break easily when you're not using the axiom of choice.

More to the point, it is consistent that there is a partial order which satisfies the countable chain condition, simply because every antichain is finite and there are no infinite maximal antichains. In other partial orders there might not be maximal antichains at all.

While we're at it, the maximality principle in forcing is equivalent to the axiom of choice, so that one fails to (I mean the fact that $p\Vdash\exists\tau\varphi(\tau)\iff \exists\dot\tau\ p\Vdash\varphi(\dot\tau)$ which is often used in forcing).

Moreover, in peculiar forcings as I mentioned above it is generally expected for the maximality principle to fail. Making this a double-trouble problem.

But then again, not all is lost. As Mohammad points out, the cardinality of the forcing poset is an upper bound. And that upper bound works out for every function, and every two sets in the ground model. While this is not necessarily an $\aleph$ number, it is still an upper bound in some sense.

If $1_P\Vdash\dot f\colon\check A\to\check B$, then every condition must agree that $\dot f$ is a name for a function. Therefore if $p\Vdash\dot f(\check a)=\check b$, then this $b$ is unique. So if we define $F(a)=\{b\in B\mid\exists p\ p\Vdash\dot f(\check a)=\check b\}$, then there is a surjection from $P$ onto $F(a)$, if $p$ doesn't decide the value of $\dot f(\check a)$ then map it to some fixed element; otherwise map it to the value it decided upon.

Of course, in the absence of choice, the existence of a surjection need not imply the existence of an injection, so if you want an upper bound in the sense of injections ($\leq$) rather than surjections ($\leq^*$) you need to consider $2^P$ instead.

The above can be circumvented if $P$ is already a complete Boolean algebra. In that case we define an injection from $F(a)$ into $P$ defined by $b\mapsto\sum\{p\mid p\Vdash\dot f(\check a)=\check b\}$. Since $P$ is a complete Boolean algebra this condition exists, and it is unique.