## anonymous one year ago Set theory operations from logical operations

1. ParthKohli

$A \cap B = C$is equivalent to$k\in C \iff (k\in A) \wedge (k \in B)$I don't even know what the question is but...

2. anonymous

The set operations seem to mimic logical operations. $A\cap B = C \equiv \forall x:x\in A\land x\in B \iff x \in C$In this sense $$\cap$$ corresponds to $$\land$$, $$\cup$$ corresponds to $$\lor$$, $$\subseteq$$ corresponds to $$\implies$$, $$\setminus$$ is more of a combination of two operations, or as $$a \land \lnot b$$, which is $$\lnot (a \implies b)$$. I'm just sort of thinking aloud here.

3. anonymous

It's not really a tutorial, it's more of a discussion. You can ask questions but there is no actual question.

4. anonymous

$A f(\circ) B = C\equiv \forall x:(x \in A) \circ (x\in B) \iff x \in C$Hmmmmm

5. anonymous

So $$f(\land) = \cap$$.

6. anonymous

so would set theory disallow this? Since it requires that there exist a set of all sets?

7. anonymous

Let $$B = \{ true, false\}$$. We can say $$\circ$$ is an operation on $$B$$, but we can't say $$\cap$$ is an operation/mapping because it acts on all sets, and you can't have a set of all sets.

8. perl

How did you go from operating on a set to a set of all sets.

9. anonymous

Well, what would you say is the domain and codomain of $$\cap$$?

10. perl

I don't know if we can think of intersection as a function or an operation in the traditional sense. the power set i think is an operation

11. perl
12. anonymous

Hmmm

13. anonymous

power set still has 'all sets' as a domain, codomain

14. perl

ok I think I understand you are saying. For intersection U X U -> U for union the same

15. anonymous

Yep

16. perl

but you are using the domain as U, not UXU ?

17. perl

taking the cross product of such a large set can present its own problems

18. anonymous

for a unary operation, you have U -> U

19. perl

complement would be a unary operation

20. anonymous

Yep Well maybe what we need is a new math concept, say "collection" , like a set, but less strict. Less strict to the sense that we can say the "collection" of all sets

21. perl

Why did it bother the early 20th century mathematicians so much, allowing a universal set.

22. anonymous

And a collection would nee the ability to let you know if something is in it or not, to iterate through it, have no duplicates?

23. perl

I would rather have a system that is clear and intuitive , that may have a paradox, than a complicated system that I cannot use.

24. anonymous

Yeah, this is something we can do in programming, yet we can't do it in math. How bizarre!

25. perl

you can allow self reference in programming, as you said with memory earlier?

26. anonymous

yeah

27. perl

what you described above with logic and set theory is whats called an isomorphism

28. anonymous

You can have an array of arrays, where one of the elements is itself

29. perl

with some qualifications , the logical *and* corresponds to intersection

30. perl

can you find a logical operation that is equivalent to A subset B

31. anonymous

Well $$\implies$$ corresponds to $$\supseteq$$

32. perl

with some tweaking it could work. note that you need for all x for the subset condition

33. anonymous

Here is something I found that is interesting: https://en.wikipedia.org/wiki/Type_theory

34. perl

"In type theory, concepts like "and" and "or" can be encoded as types in the type theory itself." This could correspond to memory addresses

35. perl

Here is some of the history behind type theory Types were created to prevent paradoxes, such as Russell's paradox. However, the motives that lead to those paradoxes – being able to say things about all types – still exist. So many type theories have a "universe type", which contains all other types.

36. perl

There is probably no way to avoid universe in some sense

37. anonymous

Here is another idea: $f(\circ)A = y \equiv \forall x\in A: x \circ \bigg(f(\circ) (A\setminus x)\bigg) = y$

38. anonymous

wait, that isn't quite right...

39. anonymous

Here is another idea: $f(\circ)A = y \equiv \bigg( f(\circ)\emptyset = I_{\circ} \bigg) \land x\in A \implies x \circ \bigg(f(\circ) (A\setminus x)\bigg) = y$

40. anonymous

Hmm, what I'm trying to do is describe a map. It takes a binary operation with an identity element. For the empty set, it returns that element. For a non empty set, it removes any element x from the set, finds the result for the set minus x, then performs the operation on x and this result

41. anonymous

The idea is $$f(+)$$ corresponds to $$\sum$$.

42. anonymous

$f(\circ) = \begin{cases} \circ_{identity} & \emptyset \\ x\circ f(\circ) (A\setminus\{x\}) &\text{otherwise} \end{cases}$I wonder if this is problematic in ZF set theory. Can you pick out an arbitrary element, and keep doing this until you have an empty set?

43. anonymous

Also, for $$x$$ to be an arbitrary element in $$A$$, then I'm guessing this operation must be associative.

44. perl

is your latter definition of $$f \circ$$ different from your former definition above $$A f(\circ) B = C\equiv \forall x:(x \in A) \circ (x\in B) \iff x \in C$$

45. anonymous

Yep, they are not the same $$f$$.

46. anonymous

Right now I'm doing something along the lines of: $g(+)A =\sum_{x \in A}x$

47. anonymous

Like $g(\cap) A =y \equiv \left(\bigcup_{x\in A}x \right)= y$

48. anonymous

an accumulator function

49. anonymous

While $$f(\land) = \cap$$ was more of a setwise function.

50. perl

okay that looks valid, but your definition looks recursive

51. perl

$$f(\circ) = \begin{cases} \circ_{identity} & \emptyset \\ x\circ \color{red}{f(\circ)} (A\setminus\{x\}) &\text{otherwise} \end{cases}$$

52. anonymous

Eventually you will run out of elements to use and hit the base case of the empty set.

53. perl

can you show me how it operates on $$\{1,2,3 \}$$ $$\Large f(\circ) \{ 1,2,3\}$$

54. anonymous

$f(\circ) \{1,2,3\} \equiv 1 \circ(2\circ 3) = 1 \circ(3\circ 2) = 2\circ (1\circ 3) = 2\circ(3\circ 1) = \ldots$

55. anonymous

Well, technically: $f(\circ)\{1,2,3\} \equiv 1\circ (2\circ (3\circ \text{idenity} ))$

56. perl

okay so this is defining an associative operation using a binary operation

57. anonymous

Nope

58. anonymous

It's like this: $f(+)\{1,2,3\} \equiv \sum_{k\in\{1,2,3\}}k = 1+ 2+ 3$