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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.