Build up a matroid using a "rank-like" function It is not hard to show that given a matroid ($E, L$) and a defined rank function, $L$ is exactly those subsets whose rank is equal to the size. The following question is about how to build up a matroid using a function that has exactly the same 3 properties as a rank function has.
Let $E$ be a finite set and $f$ a function from $\mathscr P(E)$ to $\mathbb{Z}$ such that:


*

*$f(\emptyset) = 0$

*Whenever $X \subseteq Y$, $f(X) \leq f(Y)$

*For any $X, Y$, $f(X)+f(Y) \geq f(X \cup Y)+f(X \cap Y)$ 
The question is: Show that the following set:
{$A \subseteq E \;|\; f(B) \geq |B| \hspace{.1cm} \forall \hspace{.1cm} B \subseteq A$} is the independent set of a matroid on $E$.
I mainly have difficulty in prove the exchange property. One of my attempts is to prove by contradiction. If I assume $X$ and $Y$ are both in $L$ and $|X| = |Y| + 1$, assume $Y \cup {x} \notin L$ for any $x \in X$. Then fix an $x \in X$ \ $Y$ and assume $Y_1 \subseteq Y$ satisfy $f(Y_1) < |Y_1|$. Say $Y_1 = A_1 \cup {x}$ where $A_1 \in L$. Then I can only conclude that:
$f(A_1) + f({x}) \geq |Y_1| > f(Y_1)$
I do not know how to proceed then.
 A: The question is a bit old, but maybe it still interests someone. The reason that it hasn't been answered so far is probably due to a problem with the given definition - it lacks something which forces $f(X)\leq |X|$, so in general, $f$ is not necessarily a rank function of a matroid, and can be the rank function of some polymatroid that is not a matroid. 
But by adding this requirement ($f(X)\leq |X|$), then $f$ is the rank function of a matroid. It can be shown as follows (though probably some simpler proof exists).
First, I'd like to use my favorite definition of a matroid:
$E$ is a finite set and $r:2^{E}\to \mathbb{N}$ is a function satisfying
I) $r(\emptyset)=0$,
II) $r(X)\leq r(X\cup \{x\})\leq r(X)+1$ for all $X\subset E, x\in E$,
III) For all $X\subset E, x,y\in E$, if $r(X)=r(X\cup \{x\})=r(X\cup \{y\})$ then $r(X)=r(X\cup \{x,y\})$.
$f$ in your definition (with additionally $r(X)\leq |X|$) satisfies this: 
Clearly from (1) and (2) $f(X)\geq 0$. From (2) $f(X)\leq f(X\cup \{x\})$. From (3) we get $f(X\cup \{x\})+f(X \cap \{x\})\leq f(X)+f(\{x\})\leq f(X)+1$, the second inequality following from the additional property, so (assuming $x\notin X$, otherwise it is immediate) it follows that $f(X\cup \{x\})\leq f(X)+1$ and (II) holds. 
To see that (III) holds we use (3) with $X\cup \{x\}$ and $X\cup \{y\}$, and assuming $x\neq y$, we get $f(X\cup\{x,y\})+f(X)\leq f(X\cup \{x\})+(X\cup \{y\})=2f(X)$, the equality following from the assumption in (III). So $f(X\cup \{x,y\})=f(X)$.
Now let $L'=\{A\subset E\ |\ r(A)=|A|\}$ (written slightly different than your $L$, but using $r(X)\leq |X|$ and $r(X\cup \{x\})\leq r(X)+1$ it's not hard to see that they are equal). 
Consider $X,Y\in L'$ with $|Y|>|X|$. If $\forall y\in Y\setminus X, r(X\cup \{y\})=r(X)=|X|$, then using (III), $r(X\cup Y)=r(X)=|X|$, but it's easy to see from (II) that  $r(Y)\leq r(X\cup Y)$, so $|Y|\leq |X|$, a contradiction. So $\exists y\in Y, r(X\cup \{y\})=r(X)+1=|X\cup \{y\}|$, so $X\cup \{y\}\in L$. This shows the exchange property. The hereditary property follows easily from (II).
