Formal definition of set operations

[V0ODO0CH1LD]

Are set operations on a set $X$ defined as operations on $2^X$? In other words a binary operation on $X$ is an operation $\omega:2^X\times{}2^X\rightarrow{}2^x$?

Surely the basic set operations could be defined that way, but then some weird non-standard operation like $\omega:\{a,b\}\times{}\{c,d\}\mapsto{}\{a\}$ would also be "defined"..

I'm asking this question because I'm wondering if unions and complements, or intersections and complements, are "functionally complete". Can I express ALL definable n-ary set operation using just unions and complements? Like I can express all n-ary boolean functions using just disjunction and negation?

Because if that is the case, the σ-algebra on a set X would be like the subset of the power set of X that is closed under ANY set operation. Or is it that the σ-algebra on X is just the subset of the power set of X closed under enough set operations that allow for all the useful constructions on a σ-algebra to be defined?

 

[economicsnerd]

Not all $n$-ary set operations can be defined using just unions and complements (i.e. of the form $(A_1,...,A_n)\mapsto \phi(A_1,...,A_n),$ where $\phi$ is some first order formula with $n$ free variables in the language $\{\cup, (\cdot)^c\})$. In particular, any such operation will be permutation-invariant (which you can prove by induction on complexity). So an easy counterexample is as follows: Suppose $|X|>1$ and fix $x\in X$. Then the unary operation $A\mapsto \{x\}:2^X\to 2^X$ isn't definable in the given language.

Also, a nitpicky point: the operation you gave isn't well-defined. Say $X = \{6,7,8,9\}$... Would $\omega(\{6,7\},\{8,9\})$ be $6$? Or is it $7$?

 

[V0ODO0CH1LD]

Not all $n$-ary set operations can be defined using just unions and complements (i.e. of the form $(A_1,...,A_n)\mapsto \phi(A_1,...,A_n),$ where $\phi$ is some first order formula with $n$ free variables in the language $\{\cup, (\cdot)^c\})$. In particular, any such operation will be permutation-invariant (which you can prove by induction on complexity). So an easy counterexample is as follows: Suppose $|X|>1$ and fix $x\in X$. Then the unary operation $A\mapsto \{x\}:2^X\to 2^X$ isn't definable in the given language.

Also, a nitpicky point: the operation you gave isn't well-defined. Say $X = \{6,7,8,9\}$... Would $\omega(\{6,7\},\{8,9\})$ be $6$? Or is it $7$?

I realize that not all maps $\omega{}:(2^X)^n\rightarrow{}2^X$ can can be represented by compositions of the union and complement maps. I guess my point was whether or not ALL set operations on the subsets of some set $X$ are a map $\omega{}:(2^X)^n\rightarrow{}2^X$.

The way I see it there are three options:
1. operations on subsets of a set $X$ are maps $\omega{}:(2^X)^n\rightarrow{}2^X$ and therefore union and complement are not functionally complete.
2. not every map $\omega{}:(2^X)^n\rightarrow{}2^X$ represents a set operation on subsets of a set $X$ (like the one I used as an example). Which is why I thought that union and complement might be functionally complete, because it could be the case that only the maps that are constructible using compositions of union and complement are defined set operations.
3. there are set operations that are not maps $\omega{}:(2^X)^n\rightarrow{}2^X$. In which case my original question still stands. What is the formal definition of operations on sets?

 

[economicsnerd]

I guess my point was whether or not ALL set operations on the subsets of some set $X$ are a map $\omega{}:(2^X)^n\rightarrow{}2^X$.

How do you formally define a "set operation on the subsets of $X$"?

 

[V0ODO0CH1LD]

How do you formally define a "set operation on the subsets of $X$"?

That was my question. I'm just phrasing it like "set operation on the subsets of $X$" so that I can talk about $2^X$. But I guess that if you had a definition for set operations in general it would follow from that.