Assume $A = \{a_1,...,a_n\}$ and $B = \{b_1,...,b_k\}$ are finite sets and $P = \{p_{i,j} | 1\leq i \leq n, 1\leq j \leq k\}$ a set of logical variables. Every truth assignment $b$ of $P$ induces a relation $R_b\subset A\times B$ with:
$$(a_i,b_j)\in R_b \Leftrightarrow b(p_{i,j})=1$$
Find a logical formula $\varphi$ so that:
$\hat{b}(\varphi)=1 \Leftrightarrow R_b$ is a function.
My solution:
$R_b$ is a function means that: $\quad \forall a \exists b: aR_bb$
My idea was to make this problem more accessible by writing the variables $p_{i,j}$ in a matrix form. And realizing that exactly one of every row has to be picked, i.e. I need all formulas which are true when only one of every row is true and connect and construct the disjunction of them. (rows are correlating to the first index variable $i$):
$J:=\{1,...,n\}$ $m:=max\{n,k\}$
$\varphi :=\bigvee\limits_{j\in J^m}(\bigwedge\limits_{i\in J}(p_{i,j_i}\land \bigwedge\limits_{k\in J\setminus \{i\}}\lnot p_{k,j_k}))$
My problem is that I don't really know how to prove my result and I also think there is a simpler more elegant solution to this. Can someone help me with another approach to this? I probably have stared to long at it.
Yes, $R_b$ is a function $\Leftrightarrow \forall a\in A,\exists!b\in B:aR_b b\ $. ($\exists!$ means "these exists a unique")
Now, to cover "$\forall a$", we need $\bigwedge$ along all $i\in\{0,1,...,n\}$. So, $\varphi=\bigwedge_{i=1}^n ...$
Then, to cover the "there exist a unique $b$ such that..." part, we have $k$ disjunctions:
"$p_{i,1}$ is true and all other $p_{i, m}, m\neq 1$ are false", OR
"$p_{i,2}$ is true and all other $p_{i, m}, m\neq 2$ are false", OR
..., OR
"$p_{i,k}$ is true and all other $p_{i, m}, m\neq k$ are false."
Formally, the "there exist a unique $b$ such that..." part would be: $\bigvee_{j=1}^k(p_{i,j}\wedge\bigwedge_{m\in \{1,..,k\}\setminus j} \neg p_{i,m}).$
Combining, we get the final formula: $$\varphi=\bigwedge_{i=1}^n\bigvee_{j=1}^k(p_{i,j}\wedge\bigwedge_{m\in \{1,..,k\}\setminus j} \neg p_{i,m}).$$