Formal Language 1. List the elements for each of the following sets: (1) P({a, b
ID: 3879660 • Letter: F
Question
Formal Language
1. List the elements for each of the following sets:
(1) P({a, b, c}) (Note: P refers to power set)
(2) P{a, b}) - P({a, c})
(3) P()
(4) {x : (x 7 x 7} (Note: is the set of nonnegative integers)
(5) {x : y (y < 10 (y + 2 = x))}
(6) {x : y (z ((x = y + z) (y < 5) (z < 4)))}
(7) {a, b, c} x {c, d} (Note: x refers to Cartesian product)
2. True or False.
Let R = {(1, 2), (2, 3), (1, 1), (2, 2), (3, 3), (1, 3)}.
(1) R is reflexive.
(2) R is transitive.
(3) R is symmetric.
(4) R is antisymmetric.
3. (16) True or False.
(1) Subset-of is a partial order defined on the set of all sets.
(2) Subset-of is a total order defined on the set of all sets.
(3) Proper-subset-of is a partial order defined on the set of all sets.
(4) Proper-subset-of is a total order defined on the set of all sets.
(5) Less than or equal (<=) is a partial order defined on the set of real numbers.
(6) Less than or equal (<=) is a total order defined on the set of real numbers.
(7) Less than (<) is a partial order defined on the set of real numbers.
(8) Less than (<) is a total order defined on the set of real numbers.
4. True or False.
(1) f (x) = 2x is onto where f: R -> R. (Note: R is the set of real numbers)
(2) f (x) = 2x is one-to-one where f: R -> R.
(3) f(x) = x² is onto where f: R -> R.
(4) f(x) = x² is one-to-one where f: R -> R.
(5) f(x) = x² is onto where f: R -> [0, ).
(6) f(x) = x² is one-to-one where f: R -> [0, ).
5. Let be the set of nonnegative integers. For each of the following sentences in first-order logic, state whether the sentence is valid, is satisfiable (but not valid), or is unsatisfiable.
(1) x (y (y < x)).
(2) x (y (y > x)).
(3) x (y f(x) = y).
6. Are the following sets closed under the given operations? Answer yes or no. If the answer is no, please specify what the closure is.
(1) The negative integers under subtraction.
(2) The odd integers under remainder, mod 3.
(3) The positive integers under exponentiation.
(4) The finite sets under Cartesian product.
(5) The rational numbers under addition.
7. True or False. If the answer is true, provide an example (Hint: use subsets of integers and real numbers) as a proof.
(1) The intersection of two countably infinite sets can be finite.
(2) The intersection of two countably infinite sets can be countably infinite.
(3) The intersection of two uncountable sets can be finite.
(4) The intersection of two uncountable sets can be countably infinite.
(5) The intersection of two uncountable sets can be uncountable.
Explanation / Answer
1.
(1)
Power set of the set {a, b, c} is as follows:
Power set = {{}, {a}, {b}, {c}, {a,b}, {b,c}, {a, c}, {a, b, c}}
(2)
P({a, b}) = {{}, {a}, {b}, {a, b}}
P({a, c}) = {{}, {a}, {c}, {a, c}}
Therefore,
P({a, b}) - P({a, c}) = {{b}, {a, b}}
(3)
P() = {}
(4)
{x : (x 7 x 7}
x 7 = {1, 2, 3, 4, 5, 6, 7}
x 7 = {7, 8, 9, 10, 11, 12,………………..}
Therefore,
{x : (x 7 x 7} = {7}
(5)
{x : y (y < 10 (y + 2 = x))}
X = {1, 2, 3, 4,……………}
Since,
y < 10 = {1, 2, 3, 4, 5, 6, 7, 8, 9}
(y + 2 = x) = {3, 4, 5, 6, 7, 8, 9, 10,…………}
Therefore,
(y < 10 (y + 2 = x)) = {3, 4, 5, 6, 7, 8, 9}
(6)
{x : y (z ((x = y + z) (y < 5) (z < 4)))}
Y = {1, 2, 3, 4}
Z = {1, 2, 3}
X = {2, 4, 6}
Therefore,
((x = y + z) (y < 5) (z < 4)) = {2}
(7)
{a, b, c} x {c, d} = {(a,c), (a, d), (b,c), (b, d), (c,c), (c, d)}
2.
Consider the following relation,
R = {(1, 2), (2, 3), (1, 1), (2, 2), (3, 3), (1, 3)}.
True
True
False
False
3.
(1) Subset-of is a partial order defined on the set of all sets. TRUE
(2) Subset-of is a total order defined on the set of all sets. FALSE
(3) Proper-subset-of is a partial order defined on the set of all sets. TRUE
(4) Proper-subset-of is a total order defined on the set of all sets. FALSE
(5) Less than or equal (<=) is a partial order defined on the set of real numbers. TRUE
(6) Less than or equal (<=) is a total order defined on the set of real numbers. FALSE
(7) Less than (<) is a partial order defined on the set of real numbers. FALSE
(8) Less than (<) is a total order defined on the set of real numbers. TRUE
Note: As per chegg policy we are not allowed to answer more than 2 or 3 question at a time. Please ask the remaining question in the other section.