0
$\begingroup$

Add a primitive a one place function symbol $c$ to represent "True cardinality" of a set, to the first order language of set theory.

Add the following axiom schema:

1. Cardinal Equality: If $\phi(x,y)$ is a formula in which both and only $x,y$ occur free, and only occur free, then all closures of:

$\forall X,Y: \\\forall x \in X \exists! y \in Y (\phi(x,y)) \land \\\forall y \in Y \exists! x \in X (\phi(x,y)) \\ \to c(X)=c(Y)$

are axioms.

Add the following $\omega$-rule of inference:

2. Cardinal Inequality: If $\psi(X); \varphi(Y)$, are formulas in which $X,Y$ occur free and only free respectively, then:

From: $\big{[}$if $\phi(x,y)$ is a formula in which both and only $x,y$ occur free, and they only occur free, then all closures of the following formula are true:

$\forall X,Y (\psi(X) \land \varphi(Y) \to \\\neg [\forall x \in X \exists! y \in Y (\phi(x,y)) \land \\\forall y \in Y \exists! x \in X (\phi(x,y))]) \big{]}$

______________________we Infer

All closures of $\forall X,Y (\psi(X) \land \varphi(Y) \to c(X)\neq c(Y) )$ are true.

Now if a set theory T extended with the above, proves that:

$\exists X,Y: |X|\neq|Y| \land c(X)=c(Y)$

Then its guilty of committing cardinaity error of the first kind.

If it proves that:

$\exists X,Y: |X| = |Y| \land c(X) \neq c(Y)$

Then its guilty of committing cardinality error of the second kind.

Now NFU is an example of a set theory that commit cardinality error of the first kind, but this cannot occur in ZFC.

Can ZFC commit cardinality error of the second kind?

Based on comments with Monroe Eskew. The following question presents itself.

Is there a natural statement that the theory "ZFC + ZFC doesn't commit cardinality error of the second kind" can settle, that ZFC + V=L cannot?

NOTE: The axiom schema and the $\omega$-inference rule had been edited, the prior version didn't require $x,y$ to be the sole free variables in $\phi(x,y)$ and that older version was answered by Greg Kirmayer towards ZFC proving that it cannot commit error of second kind, but it did this via a parameter. The more restrictive version present above is meant to enforce a restrictive principle on ZFC, and the second question is about such a restriction.

After note if we are testing whether a theory T is committing a cardinality error, then only primitives of theory T are allowed in the cardinal equality schema and the cardinal inequality inference rule, i.e. $c$ cannot be used.

$\endgroup$
  • 3
    $\begingroup$ It sounds like you’re asking if it is consistent with ZFC for two sets to be in bijection, without there existing a definable bijection. Do I read that right? If so, please ask your questions in this more straightforward way. Anyway, the answer can be found by looking at a model with a countable set of reals that is not definable. For example, add omega many Cohen reals. See Jech’s book. $\endgroup$ – Monroe Eskew Sep 20 at 7:08
  • $\begingroup$ @MonroeEskew, yes this is part of it, but I'm not really sure if it burns down to that only. For example if I add the axiom that ZFC do not commit cardinality error of second type, would that enforce all sets in ZFC to be definable? $\endgroup$ – Zuhair Al-Johar Sep 20 at 7:59
  • $\begingroup$ It would require that whenever sets are in bijection, then there is a definable bijection. $\endgroup$ – Monroe Eskew Sep 20 at 8:09
  • 1
    $\begingroup$ Yes but more specifically, the least $L_\alpha$ satisfying ZFC. One can prove that every set is definable without parameters in that model. $\endgroup$ – Monroe Eskew Sep 20 at 8:28
  • 1
    $\begingroup$ If $\alpha$ is uncountable and $L_\alpha$ satisfies ZFC, then it will have non-definable reals, and thus countable sets without a definable bijection with $\omega$. $\endgroup$ – Monroe Eskew Sep 20 at 9:06
2
$\begingroup$

We assume |X| is the least von Neuman ordinal for which there is a bijection from it to X. Then ZFC cannot "commit cardinality error of the second kind". This is true because your axiom scheme and rule of inference hold in ZFC when c(X) is |X|.

In order to verify the rule of inference holds when c(X) is |X|, suppose πœ“(𝑋)βˆ§πœ‘(π‘Œ) and |X|=|Y|. Then there is a bijection f between X and Y. Let πœ™(π‘₯,𝑦,z) be the formula (xy)∈z. Then (βˆ€π‘₯βˆˆπ‘‹βˆƒ!π‘¦βˆˆπ‘Œ(πœ™(π‘₯,𝑦,f))βˆ§βˆ€π‘¦βˆˆπ‘Œβˆƒ!π‘₯βˆˆπ‘‹(πœ™(π‘₯,𝑦,f).

Please note that the statement "Now NFU is an example of a set theory that commit cardinality error of the first kind, but this cannot occur in ZFC." is misleading because usually |X| has a different meaning in ZF then in NF.

I deleted my last comment because it was not correct, and am adding the answers to the modified(parameters not allowed) questions. If ZF is consistent, then the answer to the first modified questions is no. If ZF is consistent so is ZF+V=L. The modified axioms and rules of inference hold in ZF+V=L when c(X) is interpreted as |X|. Let < be a definable well ordering of the universe. In order to verify the rule of inference holds when c(X) is |X|, suppose πœ“(𝑋)βˆ§πœ‘(π‘Œ) and |X|=|Y|. Let b be the least cardinal such that there exist s and t for which πœ“(s)βˆ§πœ‘(t) and |s|=|t|=b. Let x be <-least such that πœ“(x) and |x|=b. Let y be <-least such that πœ‘(y) and |y|=b. Let f be the <-least bijection from x to y. Let πœ™(s,t) be a formula which holds when and only when f(s)=t. Then (βˆ€s∈xβˆƒ!t∈y(πœ™(s,t))βˆ§βˆ€t∈yβˆƒ!s∈x(πœ™(s,t). If ZF is consistent then the answer to the second modified question is yes because "ZFC doesn't commit cardinality error of the second kind" implies Con(ZF).

$\endgroup$
  • $\begingroup$ correction of previous comment:Suppose |X|=|Y|. Then there is a bijection f from X to Y. Let πœ™(π‘₯,𝑦,z) be the formula (xy)∈z. Then βˆ€π‘₯βˆˆπ‘‹βˆƒ!π‘¦βˆˆπ‘Œ(πœ™(π‘₯,𝑦.f))βˆ§βˆ€π‘¦βˆˆπ‘Œβˆƒ!π‘₯βˆˆπ‘‹(πœ™(π‘₯,𝑦.f). Thus c(X)=c(Y). Suppose there are X and Y with c(X)=c(Y) and |X|β‰ |Y|. Let b be the least cardinal of such an X. Let πœ“(𝑋) be the formula |X|=b. Let πœ‘(π‘Œ) be the formula |Y|β‰ b. By the inference rule c(X)β‰ c(Y) whenever πœ“(𝑋) and πœ‘(π‘Œ). This contradicts our choice of b and thus c(X)=c(Y) iff |X|=|Y $\endgroup$ – Greg Kirmayer Sep 20 at 19:37
  • $\begingroup$ what if we forbid $\phi(x,y)$ from having parameters? $\endgroup$ – Zuhair Al-Johar Sep 20 at 20:37
  • $\begingroup$ I didn't get your comment regarding the second c(X)=c(Y) and |X| $\neq$|Y|. are you suggesting that b=c(X) and also that b=|X|, why should those agree, there might be no set X assigned the same cardinal object value under both $c$ and || functions? and why the inference rule should result in c(X)$\neq$c(Y) $\endgroup$ – Zuhair Al-Johar Sep 21 at 7:03
  • $\begingroup$ @what is the proof that there is a model of that theory in which c(X)=|X|? by the way I don't think the global choice function is a definable function, so how you'll introduce it in your argument? $\endgroup$ – Zuhair Al-Johar Sep 22 at 18:48
  • $\begingroup$ formulas must not use the symbol "c" because it is not a primitive of the tested theory. $\endgroup$ – Zuhair Al-Johar Sep 23 at 6:11
6
$\begingroup$

This principle as written isn't appropriate for the class of theories including NF and NFU. If the formula $\phi$ is restricted to be stratified and have $x$ and $y$ of the same relative type then the principle is true in NF and so in any of its fragments (this is the real answer).

In NF, the universe is a set, the set of all singletons is a set, and there can be no bijection between them. Suppose there were such a bijection f from singletons onto sets. Then we could define the set $R = \{x : \lnot (x \,E\, f(\{x\}))\}$ (this definition would be stratified). Now consider $f^{-1}(R) = \{r\}$, $r \,E\, R \iff \lnot \ r \,E \,R$ follows.

There are fragments of NF in which this argument does not work: these inevitably have seriously impaired comprehension principles and are very weak. I believe that in versions of NF with predicativity restrictions on comprehension, one can arrange for all infinite sets to be the same size. But mathematically these systems are quite weak, and the principle Zuhair suggests becomes true in a trivial sense.

$\endgroup$
  • 6
    $\begingroup$ Welcome to MO, Professor Holmes! $\endgroup$ – Todd Trimble Sep 20 at 17:40
  • 2
    $\begingroup$ Welcome Professor Holmes! $\endgroup$ – Zuhair Al-Johar Sep 20 at 17:56
  • $\begingroup$ NFU: This time it's MUTUAL. $\endgroup$ – Asaf Karagila Sep 21 at 6:39
  • $\begingroup$ In reality the principle is posed in a general manner over "any" first order theory T. So it has nothing to do with the particulars of NFU or ZFC or any other theory, and its not intended for use in a specific theory. The principle capture the intuitive idea of cardinality errors that runs against existence definable bijections at class level (first kind error), or that pose bijections for which no definable witness is there (second kind error). $\endgroup$ – Zuhair Al-Johar Sep 24 at 3:53
  • $\begingroup$ You need to change your answer about the power of fragments of NF that can escape this argument since clearly SF + Infinity + choice + every object has |V| many co-extensional copies do clearly violate your argument and yet it is as strong as NFU + infinity + choice. So your argument about inevitable weakness of fragments of NFU escaping that argument is not correct. $\endgroup$ – Zuhair Al-Johar Sep 24 at 17:08

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.