Using the Compactness Theorem for Propositional Logic to prove that the countable union of countable sets is countable

elementary-set-theorylogicpropositional-calculus

Consider a disjoint family $\{A_{n}\}_{n\in\mathbb{N}}$ of countable sets, let $A$ denote the their union. We can define a language $L$ to have atoms $p_{an}$ for each $a\in A$ and $n\in\mathbb{N}$ (expressing $a$ is assigned the number $n$ when true). Then we define $S$ to be the set of $L$ formulas:

  1. $\displaystyle\bigvee_{n\in\mathbb{N}}p_{an}$ for all $a\in A$. (each $a\in A$ is assigned at least one number)
  2. $\neg(p_{an}\wedge p_{am})$ for all $a\in A$ and $n\neq m\in\mathbb{N}$ (each $a\in A$ is assigned at most one number).
  3. $\neg(p_{an}\wedge p_{bn})$ for all $a\neq b\in A$ and $n\in\mathbb{N}$ (no two distinct elements of $A$ are assigned to the same number)

If $S$ is satisfiable, then we can use an $L$-assignment $M$ satisfying $S$ to define an injective function $f:A\rightarrow \mathbb{N}$ by $f(a) = n$ iff $M(p_{am})=\mbox{T}$. It is well defined by 1. and 2. and injective by 3.

Now, if $S_{0}\subseteq S$ is finite, then the elements of $A$ mentioned in $S_{0}$ are finitely many, say $x_{1},\ldots,x_{k}$ and we can simply define an $L$-assignment $M$ by $M(p_{x_{i}m})=\mbox{T}$ iff $i=m$. Then $M$ satisfies $S_{0}$ and as a result $S$ is finitely satisfiable. By Compactness, $S$ is satisfiable and we are done.

Or aren't we? It seems I am missing something important here…at no point I seem to utilize that the family is countable…

Edit: As it is pointed out in a comment below by Timo, the argument is flawed. However, is it possible to use Compactness to prove the well known result?

What if we modify 1. above so that the disjunction is finite? Namely,

1'. $\displaystyle{\bigvee_{n\in F}} p_{an}$ for all $a\in A$ and finite $F\subset\mathbb{N}$.

Thus $S$ would be the set of all the $L$-formulas from 1'., 2. and 3.

Would this work?

Best Answer

Thanks to Karl in the comments for pointing me in the right direction.

We define a language $L$ to have atoms $p_{ij}^{n}$ for each $i,j,n\in\mathbb{N}$ (expressing when true: the $i^{th}$ element of $A_{j}$ (denoted by $a_{ij}$) is assigned the number $n$). Then we define $S$ to be the set of $L$ formulas:

  1. $\displaystyle\bigvee_{n=1}^{N_{ij}}p_{ij}^{n}$ for all $i,j\in\mathbb{N}$, where $N_{ij}$ will be an appropriate natural number. (Each $a_{ij}$ is assigned at least one number)
  2. $\neg(p_{ij}^{n}\wedge p_{ij}^{m})$ for all $i,j\in\mathbb{N}$ and $n\neq m\in\mathbb{N}$. (Each $a_{ij}$ is assigned at most one number).
  3. $\neg(p_{ij}^{n}\wedge p_{uv}^{n})$ for all $(i,j)\neq(u,v)$ and $n\in\mathbb{N}$. (No two distinct elements $a_{ij}$ and $a_{uv}$ are assigned the same number)

Now, if $S_{0}\subseteq S$ is finite, then the elements of $A$ mentioned in $S_{0}$ form a finite subset $B=\{a_{i,j}:\mbox{finitely many $i,j$}\}$ of $A$. Now, we can define a function $g:B\rightarrow\mathbb{N}$

$$g(a_{ij})=3^{i}5^{j}.$$

The function $g$ is injective by the uniqueness of prime factorization. Therefore, if we let $N_{ij}=5^{i+j}$ in 1. we can define an $L$-assignment $M$ by

$$M(p_{ij}^{n})=\mbox{T} \;\;\mbox{iff}\;\; g(a_{ij})=n.$$

$M$ satisfies $S_{0}$ and so $S$ is finitely satisfiable. By Compactness, $S$ is satisfiable.

Finally, we can use any $L$-assignment $M$ satisfying $S$ to define a function $f:A\rightarrow \mathbb{N}$ by

$$f(a) = n \;\;\mbox{iff}\;\; M(p_{ij}^{n})=\mbox{T},$$

which is well defined by 1. and 2., and injective by 3.

Note: $N_{ij}$ in 1. has to be large enough to allow us to prove that $S$ is finitely satisfiable, which in turn depends on the function $g$. That is, it will depend on the indices $i,j$ and we want $N_{ij}>g(a_{ij})$. Notice that we may define the function $g$ differently. Karl in the comments suggested $(i+j)^{2}$ possibly because he was thinking of $g(a_{ij})=\binom{i+j+1}{2}+j$. For this $g$, letting $N_{ij}=(i+j+1)^{2}$ would certainly suffice. (If we work with $\mathbb{N}^{+}$ we may also use $g(a_{ij}) = 2^{i-1}(2j-1)$, in which case $N=2^{i+j}$ will suffice.

Related Question