Set theory, proof

  • Thread starter bobby2k
  • Start date
  • #1
127
2
I am supposed to prove:

If A [itex]\neq[/itex] [itex]\phi[/itex] and B [itex]\neq[/itex] [itex]\phi[/itex] then
A[itex]\times[/itex] B [itex]\neq[/itex] [itex]\phi[/itex]

The HINT in the back of the book gives:
A [itex]\neq[/itex] [itex]\phi[/itex] [itex]\wedge[/itex] B [itex]\neq[/itex] [itex]\phi[/itex]
[itex]\Rightarrow[/itex] [itex]\exists[/itex]a[itex]\subseteq[/itex]A [itex]\wedge[/itex]b[itex]\subseteq[/itex] B so that (a,b) [itex]\subseteq[/itex] A[itex]\times[/itex] B

I have 2 questions

1.Is it enough for the proof to write the hint, and then say "hence A [itex]\times[/itex]B" is not empty.

2. Or do I have to prove the hint?
If I have to prove the hint, is this a correct way to prove it?
[itex]A \neq \phi \wedge B \neq \phi [/itex] -Premise-(1)
[itex]A \neq \phi [/itex] - 1 and simplification-(2)
[itex]B \neq \phi [/itex] - 1 and simplification-(3)
[itex] \exists a \in A[/itex] - 2 and since A is not empty it has atleast one element-(4)
[itex] \exists b \in B[/itex] - 3 and since B is not empty it has atleast one element-(5)
[itex] (\exists a \in A) \wedge (\exists b \in B)[/itex]- 4 and 5- (6)
[itex](a,b) \in A \times B[/itex] - 6, and definition of [itex]A \times B [/itex] -(7)
[itex] A \times B \neq \phi [/itex] - 7 and definition of [itex]\phi[/itex] (8)

Is step (4) and (5) ok? I haven't read an axiom that specifies that every non-empty set has ateleast one element. Do I maybe have to use the face that there is only one empty set. And since there is only one empty set, every other set must have atleast one element, or else they would be the empty set?

Should step (7) have more explanation?

Also should existencial generalistion or specification have been cited anywhere in the proof?
 
Last edited:

Answers and Replies

  • #2
6,054
391
What is the definition of the empty set that you are supposed to know and use?
 
  • #3
127
2
What is the definition of the empty set that you are supposed to know and use?

Do you mean in step 8?
There I used that the "definition" of the empty set is that it contains no elements. And since we in step (7) showed that A [itex]\times[/itex]B contains an element, it cannot be the empty set.
 
  • #4
6,054
391
I think your proof is OK.

Even though I think just the hint alone is proof enough.
 

Related Threads on Set theory, proof

  • Last Post
Replies
6
Views
605
M
  • Last Post
Replies
12
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
863
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
3
Views
899
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
4
Views
2K
Top