GUIDE TO LOGIC

Sets II

Contents

22. Subsets
23. Law of Identity for Sets
24. Transitive Law for Subsets
25. Transitive Law not Usable
26. Subset as an Intersection
27. Negation of a Subset Relation
28. Contrary Statements
29. Negation of a Contrary Statement
30. Non-empty Subset of Two Sets
31. No Conclusion from Two Subset Relations
32. Non-empty Intersection of a Subset
33. No Conclusion from an Empty Intersection of a Subset
34. No Conclusion from Two Non-empty Intersections

22. Subsets

When every element of a set A is also an element of a set B, then A is called a subset of B. We shall express this in symbols as follows: A < B.

For example, let A be the set of all butterflies, and let B be the set of all insects. Then A < B.

The definition of a subset is written in symbols as follows:

A < B means Ax: x is in A implies x is in B.

EXERCISE

Say which of the following are subsets of the set of all days in the month of June:
  1. The days from 15 May to 15 June.
  2. The days from 10 June to 20 June.
  3. The days from 15 June to 15 July.

23. Law of Identity for Sets

The composite statement A is a subset of B, and B is a subset of A means that every element of A is also in B, and every element of B is also in A. In other words, A and B have the same elements, so A = B.

For example, let A be the set of temperatures at which water is a liquid, and let B be the set of temperatures between 0oC and 100oC. These two sets of temperatures are the same. Since every temperature at which water is a liquid is between 0oC and 100oC, we have A < B. Since at every temperature between 0oC and 100oC water is a liquid, we have B < A.

This is the law of identity for subsets. It is written in symbols as follows:

For any sets A and B: A < B and B < A, if and only if A = B.

EXERCISE

Let A be the set of ships that are safe at sea, and let B be the set of ships that are well made. Give in words the interpretation of the law of identity for A and B.

24. Transitive Law for Subsets

The composite statement A is a subset of B, and B is a subset of C means that every element of A is also in B, and every element of B is also in C. It follows that every element of A is also in C, in other words A is a subset of C.

For example, let A be the set of students who work hard, let B be the set of students who pass the examinations, and let C be the set of students who graduate. Suppose the following statements are true: All students who work hard pass the examinations, in other words A is a subset of B; and All students who pass the examinations graduate, in other words B is a subset of C. It follows that A is a subset of C, in other words: All students who work hard graduate.

This is the transitive law for subsets. It is written in symbols as follows:

For all sets A, B and C: if A < B and B < C, then we conclude that A < C.
Notice that the conclusion contains the sets A and C, each of which is in only one of the first two statements. The set B, which is in both of the first two statements, is not in the conclusion.

EXERCISE

Say what we conclude from the following two statements:

Every butterfly is an insect
Every insect is an animal.

25. Transitive Law not Usable

Suppose the following statements are true: Nobody in this family can play chess, and All people who can play chess are clever. Let A be the set of all people in this family, let B be the set of all people who can play chess, and let C be the set of all clever people. Then the above two statements can be written in symbols as follows: A < B' and B < C.

In this example, because none of the people in the family can play chess, the second statement, represented by B < C, does not refer to anyone in the family. Therefore, it is not possible to say whether or not there are clever people in the family.

The general law may be summarized in symbols as follows:

We cannot conclude anything about the relation between A and C from the two statements: A < B' and B < C.

EXERCISE

Say whether or not we can conclude anything from the following pairs of statements, and give the conclusion if there is one.
  1. All frogs can swim.
    No animal that can swim will drown.
  2. No donkey is stupid.
    All stupid animals can be caught easily.

26. Subset as an Intersection

The statement A < B means:

Ax: x is in A implies x is in B.

By the definition of the implication, this has the same meaning as:

Ax: x is not in A or x is in B.

The double negation of this statement, namely:

not-Ex: x is in A and x is not in B,

also has the same meaning. The interpretation of this double negation is: There does not exist an element in A . B', in other words: The set A . B' is empty.

For example, let A be the set of all birds, and let B be the set of all animals. Then A < B means: The set of all birds is a subset of the set of all animals. This has the same meaning as: There does not exist anything that is a bird and not an animal, in other words: No bird is not an animal.

The general law connecting a subset with an intersection is:

A < B has the same meaning as A . B' = O.

EXERCISE

Give another statement with the same meaning as: No house is without a roof.

27. Negation of a Subset Statement

The statement A < B has the same meaning as A . B' = O. Therefore:
The negation of A < B is A . B' not= O.
For example, let A be the set of all coloured stones, and let B be the set of all valuable things. Then A < B means: All coloured stones are valuable. The negation, A . B' not= O, means: The intersection of the set of coloured stones and things that are not valuable is not empty, in other words: There exists a coloured stone that is not valuable.

EXERCISE

Give the negation of the statement: Every child in the village is healthy.

28. Contrary Statements

The statement A < B has a contrary statement A < B'.

For example, let A be the set of all the flowers in a garden, and let B be the set of all red flowers. Then A < B means: Every flower in the garden is red, and the contrary statement A < B' means Every flower in the garden is not red, in other words: No flower in the garden is red.

Note that the contrary statement for A < B is not the same as the negation of A < B. In the above example the negation of the statement Every flower in the garden is red is the statement There is at least one flower in the garden that is not red.

EXERCISE

Give the contrary statement for: Every child in the village is healthy.

29. Negation of a Contrary Statement

The contrary statement for A < B, is A < B'. By the law connecting a subset with an intersection, A < B' has the same meaning as A . B = O. Therefore:
The negation of A < B' is A . B not= O.
For example, let A be the set of all the flowers in a garden, and let B be the set of all red flowers. Then A < B means Every flower in the garden is red. The contrary statement is A . B not= O, which means: The intersection of the set of flowers in the garden and the set of red flowers is not empty, in other words: There is at least one red flower in the garden.

EXERCISE

Give the negation of the contrary statement for: Every child in the village is healthy.

30. Non-empty Subset of Two Sets

Suppose A not= O, A < B and A < C. The meaning of A not= O is: Ex: x is in A. This means that we can find an element a in A. Since A < B, a is also in B. Since A < C, a is also in C. Therefore, a is in B . C, which shows that B . C not= O.

For example, let A be the set of electricians in a village. Suppose we know that A not= O, that is: There is an electrician in the village. Let B be the set of builders in the village, and let C be the set of mechanics in the village. Suppose we are told that A < B and A < C, that is: Every electrician in the village is a builder, and Every electrician in the village is a mechanic. Then we may conclude: There is someone in the village (an electrician) who is both a builder and a mechanic, that is: B . C not= O.

The general law is summarized in symbols as follows:

If A not= O, A < B, and A < C, then we conclude that B . C not= O.

EXERCISE

Say what we can conclude from the following statements:

There is a large house in the village.
Every large house in the village has electricity.
Every large house in the village has a water supply.

31. No Conclusion from Two Subset Relations

Suppose A < B and A < C, but the statement A not= O is not given. Then we do not know whether or not we can find an element a in A, and we cannot conclude anything about the relation between B and C.

For example, let A be the set of electricians in a village, let B be the set of builders in the village, and let C be the set of mechanics in the village. Suppose we are told that A < B and A < C, but we are not told that A not= O. Then we know that: Every electrician in the village is a builder, and Every electrician in the village is a mechanic, but we do not know whether or not there exists an electrician in the village. Then we cannot conclude anything about the builders and mechanics in the village.

The general law is summarized in symbols as follows:

We cannot conclude anything about the relation between B and C from the two statements: A < B and A < C.

EXERCISE

Say whether or not we can conclude anything from the following pairs of statements.
  1. All ghosts are difficult to see.
    All ghosts are hungry.
  2. Every day in July this year it rained.
    Every day in July this year it was hot.

32. Non-empty Intersection of a Subset

Suppose A . B not= O and B < C. The meaning of A . B not= O is: Ex: x is in A and x is in B. This means that we can find an element a that is in A and in B. Since B < C, a is also in C. Therefore a is in A . C, which shows that A . C not= O.

For example, let A be the set of all clothes in a shop, let B be the set of all high quality clothes, and let C be the set of all expensive clothes. Then A . B not= O means the set of all high quality clothes in the shop is not empty, that is There exist high quality clothes in the shop. Also, B < C means All high quality clothes are expensive. The conclusion A . C not= O means that the set of clothes that are in the shop and are also expensive is not empty, in other words: There exist expensive clothes in the shop.

The general law is summarized in symbols as follows:

If A . B not= O and B < C, then we conclude that A . C not= O.

EXERCISE

Say what we can conclude from the following statements:

Some of the plants in this garden are poisonous
Everything poisonous is dangerous to eat.

33. No Conclusion from an Empty Intersection of a Subset

Suppose A . B = O and B < C. The statement A . B = O means: there is no element that is in both A and B. The statement B < C means: every element in B is also in C. Here we do not have enough information to conclude anything about the relation between the sets A and C.

For example, let A be the set of all clothes in a shop, let B be the set of all high quality clothes, and let C be the set of all expensive clothes. Then A . B = O means There do not exist any high quality clothes in the shop, and B < C means All high quality clothes are expensive. We do not know from these two statements whether or not any of the clothes in the shop are expensive.

The general law is summarized in symbols as follows:

We cannot conclude anything about the relation between A and C from the two statments: A . B = O and B < C.

EXERCISE

Say whether or not we can conclude anything from the following pairs of statements, and give the conclusion if there is one.
  1. All of the plants in this garden are poisonous.
    Everything that is safe to eat is not poisonous.
  2. None of the plants in this garden are poisonous.
    Everything poisonous is dangerous to eat.

34. No Conclusion from Two Non-empty Intersections

Suppose A . B not= O and B . C not= O. The statement A . B not= O means there exists an element that is in both A and B. The statement B . C not= O means there exists an element that is in both B and C. Here we do not have enough information to conclude anything about the relation between the sets A and C.

For example, let A be the set of people in a group who speak English, let B be the set of people in the group who speak Thai, and let C be the set of people in the group who speak Chinese. Then A . B not= O means There exists at least one person in the group who speaks English and Thai, and B . C not= O means There exists at least one person in the group who speaks Thai and Chinese. We cannot conclude from this information anything about the relation between the set of those who speak English and the set of those who speak Chinese. There may or may not be someone in the group who can speak both English and Chinese.

The general law is summarized in symbols as follows:

We cannot conclude anything about the relation between A and C from the two statements A . C not= O and B . C not= O.

EXERCISE

Say whether or not we can conclude anything from the following pairs of statements, and give the conclusion if there is one.
  1. There are architects who are wealthy.
    There are wealthy people who live in small houses.
  2. There are architects who are wealthy.
    There are no wealthy people who live in small houses.

Backward links: Statements I   Statements II   Quantifiers I   Quantifiers II   Sets I

Forward links: Relations I   Relations II

By R. H. B. Exell, 1998. King Mongkut's University of Technology Thonburi.
Back to Home Page