Proof regarding the algebra of sets.

In summary, the two usual arguments I have seen are the following:1) Bring the expression into some normal form, for example(X \cup Y_1) \cap (X \cup Y_2) \cap \cdots \cap (X \cup Y_n) \cap (\neg X \cup Z_1) \cap \cdots (\neg X \cup Z_k) using \neg X for the complement (there are theorems that say that this can always be done) and prove your statement for a normal form.2) Use, what you so nicely call structural induction. First you identify which operations make a new valid ("well-formed"
  • #1
F for Freedom
10
0
I am currently trying to prove the following:
An equation in X with righthand member [tex]\oslash[/tex] can be reduced to one of the form (A [tex]\cap[/tex] X) [tex]\cup[/tex] (B [tex]\cap[/tex] ~X) = [tex]\oslash[/tex].
(Where A, B, and X are sets of some universal set U, and ~X is the complement of the set X).

The only problem is that I'm not sure how to formulate or symbolize every possible equation in X. After asking a few friends and doing a bit of research online I came across ideas like structural induction and normal forms, but I'm still not sure how to apply it to prove this statement.

I know that once I can formulate this I can apply the deMorgan laws until complements of individual sets appear, and then expand the resulting lefthand side by the distributive laws and then play around with the X's and ~X's until I get what I need. But again, this all depends on the initial problem I have.

Any help would be appreciated.
 
Physics news on Phys.org
  • #2
Indeed, the two usual arguments I have seen are the following:

1) Bring the expression into some normal form, for example
[tex](X \cup Y_1) \cap (X \cup Y_2) \cap \cdots \cap (X \cup Y_n) \cap (\neg X \cup Z_1) \cap \cdots (\neg X \cup Z_k) [/tex]
using [itex]\neg X[/itex] for the complement (there are theorems that say that this can always be done) and prove your statement for a normal form.

2) Use, what you so nicely call structural induction. First you identify which operations make a new valid ("well-formed" equation). For example:
* a = X is well-formed (i.e. X = 0 with 0 the empty set)
* If a is well-formed, then so is ~a (e.g. [itex]\neg X = 0[/itex])
* If a and b are well-formed, then so are [itex]a \cup b[/itex] and [itex]a \cap b[/itex])
etc.

Then use this to prove your statement. For example,
* X = 0 is in the given form (let A = B = X).
* Suppose that [itex]a = (A \cap X) \cup (B \cap \neg X)[/itex]. Then
[tex]\neg a = \neg( (A \cap X) \cup (B \cap \neg X) )
= \neg(A \cap X) \cap \neg(B \cap \neg X)
= \cdots
[/tex]​
and reason until you again have something of the form [itex]\neg a = (A' \cap X) \cup (B' \cap \neg X)[/itex] (using deMorgan's laws, etc).​
 
  • #3
CompuChip said:
1) Bring the expression into some normal form,
Forgive me, but which expression are you referring to? Are you saying that I need to break the proof up by cases and prove that each separate expression in X can be reduced to the formula in the first post? In that case, is there another proof that shows that there is only a finite number of expressions that I need to test out? (This seems rather tedious...)

for example
[tex](X \cup Y_1) \cap (X \cup Y_2) \cap \cdots \cap (X \cup Y_n) \cap (\neg X \cup Z_1) \cap \cdots (\neg X \cup Z_k) [/tex]
using [itex]\neg X[/itex] for the complement (there are theorems that say that this can always be done) and prove your statement for a normal form.
I'm not sure what you're doing here. Aren't you assuming what we're trying to prove? What do you mean by proving my statement for a normal form? I'm not sure why this is significant, but maybe I just need to read more about normal forms.

2) Use, what you so nicely call structural induction. First you identify which operations make a new valid ("well-formed" equation). For example:
* a = X is well-formed (i.e. X = 0 with 0 the empty set)
* If a is well-formed, then so is ~a (e.g. [itex]\neg X = 0[/itex])
* If a and b are well-formed, then so are [itex]a \cup b[/itex] and [itex]a \cap b[/itex])
etc.
I guess this relates to my first question -- how do I know when to stop making these combinations of well-formed formulas? Until I get [itex](A \cap X) \cup (B \cap \neg X) = \oslash[/itex] ?

Then use this to prove your statement. For example,
* X = 0 is in the given form (let A = B = X).
* Suppose that [itex]a = (A \cap X) \cup (B \cap \neg X)[/itex].
Again, isn't this assuming what I'm trying to prove, since a = [itex]\oslash[/itex] ?

Then
[tex]\neg a = \neg( (A \cap X) \cup (B \cap \neg X) )
= \neg(A \cap X) \cap \neg(B \cap \neg X)
= \cdots
[/tex]​
and reason until you again have something of the form [itex]\neg a = (A' \cap X) \cup (B' \cap \neg X)[/itex] (using deMorgan's laws, etc).
I can follow the logical steps here, but I'm not quite sure why you are doing this. How does showing that [itex]\neg a[/itex] is well-formed prove the original statement?

I'm sorry if all my questions have obvious answers, I just can't see the bigger picture at the moment.
 
  • #4
F for Freedom said:
Forgive me, but which expression are you referring to? Are you saying that I need to break the proof up by cases and prove that each separate expression in X can be reduced to the formula in the first post? In that case, is there another proof that shows that there is only a finite number of expressions that I need to test out? (This seems rather tedious...)

What you want to prove is that any expression in X (which you set equal to the empty set) can be written as [itex](X \cap A) \cup (\neg X \cap B)[/itex], right? The idea of this method of proof is the following:
(1) Take such a formula (the left hand of an equation in X of which the right hand is the empty set)
(2) Write it in a normal form
(3) Prove that any expression in the normal form can be written in the way you want

For the normal form, there are several possibilities, such as Disjunctive normal form (DNF) or Conjunctive normal form (CNF).
On that link you will also find the claim that
Every propositional formula can be converted into an equivalent formula that is in CNF. This transformation is based on rules about logical equivalences: the double negative law, De Morgan's laws, and the distributive law.
Basically what it says is, that every formula like the one you started with in step (1) has a logically equivalent form that looks like (for example, using DNF)
[tex]
(X \cup Y_1) \cap (X \cup Y_2) \cap \cdots \cap (X \cup Y_n) \cap (\neg X \cup Z_1) \cap \cdots (\neg X \cup Z_k)
[/tex]

Then you can use logical steps to rewrite this to the form you want, i.e. show that this in turn can be rewritten as
[tex](X \cap A) \cup (\neg X \cap B)[/tex]
where of course A and B will be expressed in all of the Yi and Zj.
That proves the statement at once for all possible formulas.

For the second method, I think you haven't quite got the idea yet of what we are trying to do. Maybe you should read my post again very slowly. The idea is as follows: if we have any equation in X which we can set equal to the empty set, then we can build this equation from scratch. For this we can use building rules, like:
if you have two of these equations, say
A = 0 and B = 0
(where 0 stands for the empty set, and A and B can be any equation in X), then you can build new equations like
[itex]A \cup B = 0[/itex] and [itex]A \cap B = 0[/itex].
For example, since
[tex](X \cap S) \cap (\neg X \cup T) = 0[/tex] and [tex](X \cup U) \cap (\neg X \cup (X \cap V)) \cup W = 0[/tex]
are valid equations (as opossed to, for example [tex]X \cup = 0[/tex] or [tex]X \cap \cap Y = 0[/tex]) you know that also
[tex]\left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cup \left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0[/tex]
is a valid equation, and so is
[tex]\left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cap\left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0[/tex]
and
[tex]\neg \left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cup \left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0[/tex]
and
[tex]\left(\vphantom{\frac{1}{2}} (X \cap S) \cap (\neg X \cup T) \right) \cap \neg\left(\vphantom{\frac{1}{2}} (X \cup U) \cap (\neg X \cup (X \cap V)) \cup W \right) = 0[/tex]
and so on.

So this is sort of like a proof by induction. In a proof by induction, you assume that some statement (S) is true for the number n and then show that it also holds for n + 1. Then if you show that for n = 0 it is true, you have proved it for all possible values of n (because from n = 0 it follows for n = 1, and from that for n = 2, etc).

Now, you assume some statement (in your case, that an equation be written in the form [itex](X \cup A) \cap (\neg X \cup B)[/itex]) is true for two particular equations. Then you show that it also holds for the conjunction, disjunction and negation of those statements. Now if you show that it is true for the simplest equation you can think of (for example, X) you have proved it for all possible formulas (because from a = X, it also follows for a = (not X), a = X union X, a = X intersection X; and from that for a = not (X union X), A = X intersection (not X), and so on).

Sorry I don't have time to explain in even more detail, I hope this makes it more clear.
Perhaps a book on first order logic would be helpful to you?
 
  • #5


I can offer some guidance on how to approach this proof. To begin, it is important to understand the underlying properties of sets and how they interact with each other. One helpful tool is Venn diagrams, which can visually represent the relationships between sets and their complements.

Next, it may be useful to break down the statement into smaller parts and work on each one individually. For example, start by considering the statement (A \cap X) = \oslash. This means that the intersection of sets A and X is equal to the empty set. How can you use this fact to prove the larger statement?

One approach could be to use proof by contradiction. Assume that the statement is false and that there exists an equation in X with a right-hand member of \oslash that cannot be reduced to the form (A \cap X) \cup (B \cap ~X) = \oslash. Then, by the definition of set equality, there must be at least one element in the left-hand side that is not in the right-hand side. This leads to a contradiction because the right-hand side is equal to the empty set, meaning there can be no elements in it.

Another approach could be to use structural induction, as you mentioned. This involves proving the statement for a base case (such as the empty set) and then showing that if the statement is true for a particular equation in X, it is also true for the next equation in X. This can help to cover all possible equations in X and prove the statement for each one.

In addition, using the properties of sets and the deMorgan laws can also be helpful in manipulating and simplifying equations. Remember to justify each step in your proof and be careful not to make any assumptions or use any properties that have not been previously proven.

Overall, proving statements in algebra of sets can be a challenging but rewarding task. It requires a strong understanding of the properties of sets and how they interact with each other, as well as careful logical reasoning and justification. I hope this provides some guidance and helps you in your proof. Good luck!
 

1. What is the algebra of sets?

The algebra of sets is a branch of mathematics that deals with the study of sets and their operations. It involves the manipulation of sets using various mathematical operations such as union, intersection, and complement.

2. What is the purpose of studying the algebra of sets?

The algebra of sets is an important tool for understanding and solving problems in various fields such as computer science, statistics, and economics. It also helps in developing critical thinking and problem-solving skills.

3. How is the algebra of sets related to other branches of mathematics?

The algebra of sets is closely related to other branches of mathematics such as logic, number theory, and topology. It provides a foundation for these branches and is often used in their applications.

4. What are the basic operations of the algebra of sets?

The basic operations of the algebra of sets are union, intersection, and complement. Union combines two sets and includes all elements from both sets, intersection finds the common elements between two sets, and complement finds the elements that are not in a set.

5. How can the algebra of sets be applied in real-life situations?

The algebra of sets can be applied in various real-life situations such as analyzing data, solving business problems, and making decisions. For example, in statistics, the algebra of sets is used to determine the probability of events. In business, it can be used to analyze market trends and make strategic decisions.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
852
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
925
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
704
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
986
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
18
Views
4K
Back
Top