Thread: Freely Generated Sets?

Having missed a lecture on Recursive Definitions of Sets and Functions, I got the lecture notes online to catch up, but keep coming across freely generated sets, with no explanation of what they are. Can anybody please give me a definition of a freely generated set?

Originally Posted by ft_fan

Having missed a lecture on Recursive Definitions of Sets and Functions, I got the lecture notes online to catch up, but keep coming across freely generated sets, with no explanation of what they are. Can anybody please give me a definition of a freely generated set?

If C is freely generated from B using f and g, then there are some conditions to satisfy. Besides that C is generated from B using f and g, the restrictions f|C and g|C of f and g to C should meet the following conditions:

1. f|C and g|C are one-to-one.
2. The range of f|C, the range of g|C, and the set B are pairwise disjoint.

Examples.
(a) The integers are generated from {0} by the successor and predecessor operations but not freely generated. (Check the range of each operation)
(b) B={0} with the successor operation. Then C is the set of natural numbers. Since the succesor operation is one-to-one and 0 is not in its range, C is freely generated from {0} by the successor operation.
(c) The wff are freely generated from the sentence symbols by the formula building operations( negation, conjunction, disjunction, conditional, and biconditional operations).

The recursion theorem says that if C is freely generated, then a function h on B always has an extension on C. In other words, any map h of B into V can be extended to a homomorphism from C into V.