Prove a function on the set of propositional formulas is well-defined

Question

I define the set $X$ of propositional formulas as the smallest set such that:

1. Every atomic formula is in $X$.
2. If $F$ is in $X$ then $\neg F$ is in $X$.
3. If $F$ and $G$ is in $X$ than $(F\land G ), (F\lor G) $ and $(F \rightarrow G)$ is in $X$.

Let $t$ be a function from the atomic formulas to $\{0,1\}$. A valuation can be defined recursively as

1. $\nu (P)=1$ if and only if $t(p)=1$ for all atomic formulas.

2. $\nu(\neg F)=1$ iff $\nu( F)=0$

3. $\nu((F\land G))=1$ iff $\nu(F)=1$ and $\nu(G)=1$

4. $\nu((F\lor G))=1$ iff $\nu(F)=1$ or $\nu(G)=1$

5. $\nu((F\rightarrow G))=1$ iff $\nu(F)=0$ or $\nu(G)=1$

But how do I know that $\nu$ is well-defined? The reason I am asking is that when defining the set $X$ a formula $F$ can arise many different times, so I must be sure that every time it arises I give it the same value. Do you see how to prove this? I suspect I must use an induction proof, but I am not sure how to do it.

Answer 1

Every formula in $X$ can be formed in exactly one way; this is obvious from your formation rules. You would use induction in the structure of formulae or, equivalently, induction in the size of formulae, showing that for for every $n \geq 1$, if $F$ has size $n$, then there is exactly one $b \in \{ 0,1\}$ such that $v(F) = b$.