Set Operations Answer:Obviously no.Consider,e.g.,A={1,2,3),B={1),C={2}.Then A\(BU C)={3},but(AB)U(AC)={1,2,3}. The correct formula is:(De Morgan Law)For all sets A,B,C, A(BUC)=(AB)(AC). Proof:For all A\(BUC),we must have z A but BUC.Hence,x B and zC.Therefore, A\B and A\C.Equivalently,(A\B)n(A\C).Consequently,we get that A(BUC)C(A\B)n(A\C). For all z∈(A\B)n(A\C),we must have that x∈A\B and x∈A\C.So,x∈A but z年B and xC. Therefore,BUC.Therefore,A\(BUC).Consequently,we get that (A\B)n(A\C)CA\(BUC). Combining the results,we get that A\(BUC)=(A\B)n(A\C). DONE
Set Operations Answer: Obviously no. Consider, e.g., A={1,2,3}, B={1}, C={2}. Then A\(B ∪ C)={3}, but (A\B)∪(A\C) ={1,2,3}. The correct formula is:
Set Operations The Cartesian product of two sets X and Y is simply the set of ordered pairs where the first element of each pair comes from X,and the second element from Y. X×Yae{(c,ylx∈X,y∈Y. ■Examp1e1:X={1,2},Y={2,3,4},X×Y={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4)}. Example 2:The plane of Euclidean coordinates is the Cartesian product of two number axes,or the square of a number axis.We write p=R2 Side note:What is an ordered pair?In modern mathematics,we can actually define it as (,）={x,y},x}
Set Operations The Cartesian product of two sets X and Y is simply the set of ordered pairs where the first element of each pair comes from X, and the second element from Y. Example 1: X={1,2}, Y={2,3,4}, X×Y={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4)}. Example 2: The plane of Euclidean coordinates is the Cartesian product of two number axes, or the square of a number axis. We write . Side note: What is an ordered pair? In modern mathematics, we can actually define it as
Set Operations Intuitively,it is a set of two elements. One element describes the two components of the pair,and the other specifies which component goes first. There is no ambiguity,because one element is a set and the other element is also its element. The advantage of such a definition is that we can thus eliminate informal description like“ordered.” Modern mathematics is built upon set theory. modern math set theory Almost everything in math can be viewed as a set
Set Operations Modern mathematics is built upon set theory. Almost everything in math can be viewed as a set. Intuitively, it is a set of two elements. One element describes the two components of the pair, and the other specifies which component goes first. There is no ambiguity, because one element is a set and the other element is also its element. The advantage of such a definition is that we can thus eliminate informal description like “ordered
Set Operations We can extend the operation of Cartesian product to any number of sets.The Cartesian product of n sets is just the set of n-tuples where the kth component comes from the kth set. X1×X2×…×Xn{1,2,nl1∈X1,2∈X2,,tn∈Xn}. Clearly this operation is NOT commutative,but it is associative.(Why?) Note that the formal definition of ordered pairs is not naturally extensible to n-tuples.(Why not?)That's part of the reason why we do not always treat everything in the most formal way. Similar to squares of a set,we also have the nth power of a set,which is the Cartesian product of n copies of that set.(We'll revisit this in the future. Example:{0,1)"is the set of n-bit strings. Operating on infinitely many sets is also possible,but we temporarily put it aside
Set Operations We can extend the operation of Cartesian product to any number of sets. The Cartesian product of n sets is just the set of n-tuples where the kth component comes from the kth set. Clearly this operation is NOT commutative, but it is associative.(Why?) Note that the formal definition of ordered pairs is not naturally extensible to n-tuples.(Why not?) That’s part of the reason why we do not always treat everything in the most formal way. Similar to squares of a set, we also have the nth power of a set, which is the Cartesian product of n copies of that set.(We’ll revisit this in the future.) Example: is the set of n-bit strings. Operating on infinitely many sets is also possible, but we temporarily put it aside
Tuple and Relation A set of ordered pairs is called a (binary)relation. ■Example:X={1,2},Y={2,3},X×Y={(1,2),(1,3),(2,2),(2,3)}.Binary relation {(1,2),(2,3),(1,3)}is a subset of XXY. If both components of the ordered pairs come from the same set X,then we say it is a relation on X. Example:X={1,2).Then,{(1,2),(2,3),(1,3)}is a relation on X. A set of n-tuples is called an n-ary relation. Example 1:binary relation {(1,2),(2,3),(1,3)}. Example 2:{(1,2,3,4,3),(2,3,5,1,1)}is also a relation. In most cases,we consider binary relations only,and just call them relations
Tuple and Relation A set of ordered pairs is called a (binary) relation. Example: X={1,2}, Y={2,3}, X×Y={(1,2), (1,3), (2,2), (2,3)}. Binary relation {(1,2), (2,3), (1,3)} is a subset of X×Y. If both components of the ordered pairs come from the same set X, then we say it is a relation on X. Example: X={1,2}. Then, {(1,2), (2,3), (1,3)} is a relation on X. A set of n-tuples is called an n-ary relation. Example 1: binary relation {(1,2), (2,3), (1,3)}. Example 2: {(1,2,3,4,3), (2,3,5,1,1)} is also a relation. In most cases, we consider binary relations only, and just call them relations