In Propositional Logic when we define the set of all propositions inductively how we can prove such a set(smallest with such properties) does exists? means that the set (of all sets with these properties) under intersection operation is not empty?
Definition 1.1.2 from Van Dalen book:
The Set $PROP$ of propositions is the smallest set $X$ with the properties:
(i) $p_{i}\in X (i\in \mathbb{N})$, $\bot \in X$
(ii) $A,B \in X$ then $(A\wedge B), (A\vee B), (A\rightarrow B), (\neg A) \in X$
I know in propositional logic we model it mathematically based on ZF(C) as a common accepted foundation for mathematics and I know there is another definition by formation sequences, I think it shows at least one such set exists but I want to know without it, how we can show that $PROP$ is a set in ZFC?
Best Answer
First let us show that if only there is some set somewhere that satisfies both of your conditions, there is also a smallest such set.
It is easy to show that for any nonempty set of solutions to (i)+(ii), their intersection is still a solution. Then, under the assumption that some set $A$ is a solution, we can set $\mathit{PROP}$ to be the intersection of all subsets of $A$ that satisfy (i)+(ii), and that is clearly minimal among all solutions that are subsets of $A$. However, this is also a global minimum, because for any solution $B$, it holds that $\mathit{PROP}\subseteq B\cap A \subseteq B$.
Now for the main part. We suppose we have decided on a fixed set $L$ of proposition letters and and some arbitrary mathematical objects not in $L$ to represent the logical symbols. Then $\Sigma = L\cup\{{\land},{\lor},{\to},{\neg},{\bot},{(},{)}\}$ is a set, and then the collection $\Sigma^*$ of all finite sequences of elements of $\Sigma$ is a set. Now $\Sigma^*$ satisfies both of your conditions (i) and (ii), so we can use it as $A$ in the reasoning above. Therefore $\mathit{PROP}$ exists.
(Why is $\Sigma^*$ a set? Each of its elements is a function from some subset of $\mathbb N$ to $\Sigma$, so in particular it is a relation between $\mathbb N$ and $\Sigma$. So every element of $\Sigma^*$ is a subset of $\mathbb N\times \Sigma$, and therefore $\Sigma^*$ itself is a subset of $\mathcal P(\mathbb N \times \Sigma)$ and so $\Sigma^*$ is a set).