# How to define a set of sets with no two elements from the same set

TL;DR I'm trying to notate the phrase in bold.

I'm attempting to define an independence system, but it's been a while since I've used mathematical notation.

I have a set $$E$$ of all the elements. I also have a set $$V$$ which contains sets $$V_1, V_2,$$ etc. Each $$V_x$$ is a subset of $$E$$. (That is, it just contains elements.) Note that each $$V_x$$ is also disjoint from each other $$V_x$$ (they have no elements in common), and that the union of all $$V_x$$ gives $$E$$.

I want to define my independence system to be such that a set that has only zero or one element from each $$V_x$$ is independent. (Thus, a set with one element from each $$V_x$$ will be maximally independent.) In my head, I've phrased this as "no two elements from the same $$V_x$$".

How do I mathematically introduce such an independence system?

Currently, I've defined it as the set $$I$$ such that

$${S}\in{I}\Leftrightarrow\nexists, v_x, v_y \in S \,|\, v_x \ne v_y \land \forall{V_x}, v_x,v_y\in{V_x}$$

This is supposed to read as "$$I$$ is a set consisting of all sets that don't have two elements from the same $$V_x$$".

But my notation just seems messy, unclear, and possibly incorrect. I'm especially having a hard time figuring out how to mathematically say "no two elements from the same set".

Any help writing this idea down in mathematical notation would be appreciated.

There is not a unique approach to this, but here's one idea. Define

$$\mathfrak{I} := \{S\subset E : |S \cap V_x| \leq 1, \text{ for all x} \}.$$

Thus, a set $$S \in \mathfrak{I}$$ satisfies presicely that the cardinal of its elements which belong to $$V_x$$ is at most one, for any $$x$$ (by the way, one should be more precise and indicate what the elements $$x$$ are, i.e. to which set do they belong).

Here's another way.

You really ought to describe $$V$$ using some index set $$X$$, i.e. $$V=\{V_x\mid x\in X\}$$. You could simply take $$X=\{1,2,3,\dots,n\}$$ for example, then $$V=\{V_1,V_2,\dots,V_n\}$$. Then we can define a characteristic function $$f:E\to X$$ with $$f(v)=x$$ if $$v\in V_x$$. If we want to say that each $$V_x$$ is nonempty, then this amounts to saying $$f$$ is surjective.

Now $$I$$ is the set of subsets $$S\subset E$$ such that the set $$g=\{(f(s),s)\mid s\in S\}$$ is a partial function $$g:X\to E$$. That is, if both $$(x,s)$$ and $$(x,s')$$ are pairs in $$g$$, then $$s=s'$$ (since $$g$$ is a function). Thus, if $$s,s'$$ are two distinct elements of $$S$$, then $$f(s)=x\neq x'=f(s)$$, and therefore $$s\in V_x$$ and $$s'\in V_{x'}$$ are in different sets of $$V$$.

Such a function $$g$$ is a partial choice function on $$V$$. Hence $$I$$ can be defined as the set of ranges of the partial choice functions on $$V$$.

Alternatively, we can do without the partiality and define $$I$$ by considering all total choice functions on $$V$$, and let $$I$$ be the smallest set containing the range of each choice function on $$V$$ that is closed under subsets.