Question on Set Theory

  • Thread starter CornMuffin
  • Start date
  • #1
67
5

Homework Statement


Let A = A1 x ... x An
B = B1 x ... x Bn
C = C1 x ... x Cn
Such that A,B,C are non empty, [itex]A=B\cup C[/itex] and [itex]B\cap C = \emptyset [/itex]

prove that there exists a k in {1,...,n} such that [itex]B_k\cap C_k = \emptyset [/itex]
and for [itex]i\neq k[/itex], [itex]A_i = B_i = C_i [/itex]



Homework Equations





The Attempt at a Solution


I figure the best way to prove this is by induction.

for n=1, there is nothing to show, so I will start with n=2

Assume [itex] B_1 \cap C_1 \neq \emptyset [/itex] and [itex]B_2 \cap C_2 \neq \emptyset [/itex]

then [itex] B \cap C = (B_1 \times B_2 )\cap (C_1 \times C_2) = (B_1 \cap C_1) \times (B_2 \cap C_2) [/itex]

which implies that [itex]B \cap C \neq \emptyset [/itex] since [itex]B_1 \cap C_1 \neq \emptyset [/itex] and [itex]B_2 \cap C_2 \neq \emptyset [/itex]

but this is a contradiction to our conditions, therefore, there exists a k in {1,...,n} such that [itex]B_k\cap C_k = \emptyset [/itex]


it seems like this can be easily extended for any n



but i am having trouble proving the second part of the problem:
for [itex]i\neq k[/itex], [itex]A_i = B_i = C_i [/itex]

I tried using proof by contradiction for n=2, but i couldn't get anywhere with that


Any hints on what I should try?
 

Answers and Replies

  • #2
22,089
3,297
You need to prove two things:

[tex]B_i\subseteq A_i~\text{and}~A_i\subseteq B_i[/tex]

The first is not so hard: pick [itex]x_i\in B_i[/itex], extend it to an element of B. And use that [itex]B\cup C=A[/itex].

The second is more difficult. Pick [itex]x_i\in A_i[/itex]. Assume that it is not in [itex]B_i[/itex]. Try to extend [itex]x_i[/itex] to an element you know is not in [itex]B\cup C[/itex]. This will be a contradiction. (hint: pick a [itex]x_k\in C_k[/itex]).
 

Related Threads on Question on Set Theory

  • Last Post
Replies
1
Views
514
  • Last Post
Replies
3
Views
527
  • Last Post
Replies
3
Views
642
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
786
  • Last Post
Replies
1
Views
805
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
724
Top