Are the predicates “is finite/is countable” the only predicates failing induction over a finite set $A$ if we remove the premise that $A$ is finite

inductioninfinitylogicset-theory

I have the following theorem stating induction over finite sets from Suppes' Axiomatic Set Theory page 102:

Suppose that:

  1. $A$ is finite,
  2. $\varphi(\varnothing)$
  3. $\forall x \forall B (x \in A \land B \subseteq A \land \varphi(B) \implies \varphi(B\cup \{x\}))$

Then $\varphi(A)$.

I noticed that most predicates I can think of do not require the premise (1) that $A$ be finite, and sometimes don't even require (2) to be true, only requiring (3). For example, if $\varphi$ means "is a set of even numbers", "is a set of coordinate pairs forming a line", "is trichotomous by $\leq$", "is bounded", "is dense", etc., but "is finite" or "is countable" do not work if we remove the first premise and let $A = \mathbb{N}$. Are they the only predicates that don't work? Or are there others that do not contain them? Is there a more general principle at play here?

(edit: thanks to user Alex Kruckman for the "is countable" example)

Best Answer

Are they the only predicates that don't work?

Far from it. There are a great many different predicates that fail this principle. Alex Kruckman's comments already give you enough information to construct an entire family of such predicates, each different from the others. But there are many more ways of obtaining such families: some of them work even if you restrict your attention to predicates defined on sets of natural numbers (where cardinality considerations won't help you construct such a family since every set is going to be finite or countable). I'll give you such a construction below.

We start by choosing a non-principal ultrafilter $\mathcal{F}$ on $\mathbb{N}$, and define $\varphi(X)$ as $X \notin \mathcal{F}$. Notice that either the set of odd numbers belongs to $\mathcal{F}$, or the set of even numbers belongs to $\mathcal{F}$. In the former case, set $A=2\mathbb{N} + 1$, in the latter case set $A=2\mathbb{N}$.

Now, we have $\varphi(\emptyset)$ since the empty set does not belong to any ultrafilter. Now assume that $x \in A$, $B \subseteq A$ and $\varphi(B)$ all hold. Since $B \subseteq A \subseteq \mathbb{N}$, and the filter $\mathcal{F}$ does not contain $B$, it must contain $B^c = \mathbb{N}\setminus B$ instead. We want to prove $\varphi(B \cup \{x\})$, so assume for a contradiction that $\mathcal{F}$ contains $B \cup \{x\}$ as well. Since ultrafilters are closed under intersection, we then have that the intersection

$$(B \cup \{x\}) \cap B^c = (B \cap B^c) \cup (\{x\} \cap B^c) = \{x\} \cap B^c $$

belongs to $\mathcal{F}$. But $\{x\} \cap B^c$ is a subset of $\{x\}$, so it is finite. However, since $\mathcal{F}$ is non-principal, it cannot contain any finite set, a contradiction. We conclude that $\varphi(B \cup \{x\})$ holds whenever $x \in A$, $B \subseteq A$ and $\varphi(B)$ all hold.

If $\varphi$ "worked", then we could use this to get that $\varphi(A)$ holds. But $\varphi(A)$ does not hold, since we chose $A$ specifically to satisfy $A \in \mathcal{F}$. We're done.

Now, if we start with different ultrafilters, we end up with different predicates. The number of non-principal ultrafilters on $\mathbb{N}$ is $2^{2^{\aleph_0}}$, and there are $2^{2^{\aleph_0}}$ predicates on the subsets of $\mathbb{N}$ altogether, so we get that predicates which "do not work" are no less common than ones that "do work".

Related Question