2
$\begingroup$

Does there exist anything like a finite set whose cardinality cannot be established by means of an algorithm or mathematical proof? I think ZFC should have no problem in accomodating such an object, but I can't figure out an example.

$\endgroup$
1
  • 1
    $\begingroup$ Let $N = 10^{10^{10^{100}}}$ be a REALLY BIG NUMBER. Let $F = \{n \in \mathbb N \; | \; n \le N \text{ and } n \text{ is not a prime number}\}$. Claim: It has not been determined how many elements are in the finite set $F$. I suspect that a number $N$ can be set so high that mathematicians, cosmologists and theoretical physicists can show that it is impossible for the 'universe' to perform the calculations. $\endgroup$ Mar 9, 2018 at 13:24

2 Answers 2

4
$\begingroup$

Certainly, we can fix a natural number $n>0$ and take the set $$\{x\mid x\leq n\text{ and }\mathsf{ZFC}\text{ is consistent}\}.$$

The set is provably finite. But since we cannot prove, or find algorithmically whether or not $\sf ZFC$ is consistent, we cannot decide whether or not the set is empty, or equals to $\{0,\ldots,n\}$.

The same idea can be applied using any unprovable statement. In fact this can be even simplified to the following case:

Let $\cal L$ be the first-order logic without any extralogical symbols (except equality, which I consider a logical symbol). We write the two statements:

$$\begin{align} &\varphi_1 = \exists x\forall y(x=y)\\ &\varphi_2 = \exists x\exists y(x\neq y\land\forall z(x=z\lor y=z)) \end{align}$$

And let $\varphi=\varphi_1\lor\varphi_2$. Then if $M$ is a structure satisfying $\varphi$ either $M$ has one element, or it has two elements. But picking an arbitrary $M$ we cannot decide which one is true.

$\endgroup$
8
  • $\begingroup$ Being unable to decide the truth-value of a conjunction, does not mean we can't decide it for the conjuncts. "Fermat's Theorem is false $\land$ ZFC is consistent" does not entail that we can't decide Fermat's Theorem. $\endgroup$
    – pafnuti
    Mar 8, 2018 at 0:49
  • $\begingroup$ I don't understand your remark. Yes, you can decide Fermat's theorem's truth. However, you cannot prove if ZFC is consistent, therefore the conjunction is not provable from ZFC. $\endgroup$
    – Asaf Karagila
    Mar 8, 2018 at 7:25
  • $\begingroup$ And I don't know where I claimed that if $\varphi\land\psi$ is undecidable then both $\varphi$ and $\psi$ are undecidable. Can you please show me that statement in my answer? I would like to correct that. $\endgroup$
    – Asaf Karagila
    Mar 8, 2018 at 15:47
  • $\begingroup$ "$\{x\mid x\leq n\text{ and }\mathsf{ZFC}\text{ is consistent}\}$" sounds suggestive. $\endgroup$
    – pafnuti
    Mar 8, 2018 at 18:11
  • $\begingroup$ Okay. How about read more closely? We fixed $n$. Let's say $n=1$. Now the set is either $\{0,1\}$ in case that ZFC is consistent, or empty in case ZFC is not consistent (in your particular model). In either case, ZFC proves that this set is finite, but it does not decide how many elements it has, or even if it is empty or not. $\endgroup$
    – Asaf Karagila
    Mar 8, 2018 at 18:13
3
$\begingroup$

Let me add what happens in intuitionistic set theory. It's a bit tangential, but you might be interested.

In intuitionistic set theories such as IZF and CZF there are three alternative definitions of "finiteness" that are distinct in these theories but turn out to be equivalent when you add excluded middle.

First note that as in ZF, the natural numbers are implemented in such a way that $n = \{0,\ldots,n-1\}$, so the natural number $n$ is also a set of size $n$.

Let $X$ be a set.

$X$ is finite if there is a natural number $n$ and a bijection $f : n \rightarrow X$.

$X$ is finitely enumerable if there is a natural number $n$ and a surjection $f : n \rightarrow X$.

$X$ is subfinite if it is a subset of a finitely enumerable set.

One can show for intuitionistic set theories that every finite set has a fixed cardinality and moreover one can find the cardinality computably from a proof that a set is finite. You can also find computably an "upper bound" for finitely enumerable sets and subfinite sets.

However, there are examples of finitely enumerable and subfinite sets that have "unknown" cardinality. In fact Asaf's example for ZFC also works as an example of a subfinite set in intuitionistic set theory.

$\endgroup$
5
  • $\begingroup$ In my example you have to appeal to the law of excluded middle to prove that such $n$ exists. If the set is empty this $n$ is $0$, if not then $0$ is an unsuitable example. If you would say that the set is $\{0\}$ if $\sf ZFC$ is consistent and otherwise $\{0,1\}$ then the set is indeed subfinite. $\endgroup$
    – Asaf Karagila
    May 20, 2014 at 12:22
  • $\begingroup$ Maybe I'm misunderstanding your example. Certainly for a fixed $n$ the set $\{0,\ldots,n\}$ is finite, and your example appears to be a subset of this obtained by a single instance of separation. $\endgroup$
    – aws
    May 20, 2014 at 12:42
  • $\begingroup$ If ZFC is not consistent, then the set defined is empty. Then there is no surjection onto that set from any non empty set. $\endgroup$
    – Asaf Karagila
    May 20, 2014 at 12:55
  • 1
    $\begingroup$ I think actually it's still okay. I'm claiming that it's a subfinite set, so it only needs to be a subset of a finitely enumerable set, which certainly includes the empty set. In any case $0$, which is implemented as the empty set is a natural number, so $\emptyset$ is finitely enumerable (on the other hand it is not countable). $\endgroup$
    – aws
    May 20, 2014 at 13:05
  • $\begingroup$ Oh, okay. Yes, it is subfinite but not finitely enumerable. My bad. :-) $\endgroup$
    – Asaf Karagila
    May 20, 2014 at 13:09

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.