Naive Set Theory: Definitions

Before we delve into set theory, we'll need a brief primer on logic. There are many philosophical books written on different kinds of logic, such as propositional logic, first order logic, and other varieties, but we will avoid that quagmire by working with a straightforward version that is most similar to propositional logic.

Propositions and Truth

Logic deals with statements called propositions. Specifically, a proposition is a concrete claim about the world, such as "the sky is blue" or "$2+2=4$". The former proposition concerns the real world, while the latter concerns the world of mathematics. In general, we are only concerned about propositions regarding the mathematical world, but we can use propositions about the real world as examples to illustrate mathematical concepts.

Propositions are either true or false. A true proposition is one that correctly describes the world, and a false proposition is any proposition that is not true. The fact that there is no third option is a property called the law of the excluded middle. 

When studying logic itself, we typically use abstract symbols such as "A" or "B" to represent propositions. In fact, in the study of logic itself, proposition have no meaning other than their truth value. Thus, this is the only property we will consider going forward.

The Real World and the Mathematical World

The truth or falsity of a proposition about the real world is often imprecise due to the language we use to describe it. For example, when considering the proposition "the sky is blue," does the word "is" imply that the sky is generally blue, blue when unobstructed by clouds, blue right now, or something else? And blue according to whom? One person's eyes may perceive a consistent blue hue, but an advanced camera may detect all kinds of celestial bodies in the sky, even during the day - does blue mean uniformly blue? And how do we distinguish between blue and other colors?

Thankfully, the world of mathematics is much more precise than the real world, and there is no ambiguity about the claim of a proposition that has been rigorously stated. The proposition "2+2=4" is precisely defined. Without any specification to the contrary, the symbols "2" and "4" are understood to be natural numbers, for which the addition operator "+" is well defined, as is the equality symbol "=". This proposition is always true, and there is no ambiguity lurking in any of the symbols we use to represent it.

As we will see later, the mathematical world is defined by axioms, which are propositions about the world that are true by definition. Some axioms state that certain objects exist, and other axioms state the properties of these objects. We can use logic to combine these axioms about the existence of mathematical objects and their properties to conclude that other objects exist with certain other properties. However, we have not defined any mathematical concepts yet, so we will stick to the cozy little world of true and false for now.

Negation and The Law of Noncontradiction

The negation of a proposition $A$ is the proposition that $A$ is not true. Symbolically, the negation of a proposition $A$ is written as $\neg A$, which is read aloud as "not $A$". The negation of the proposition "the sky is blue" is the proposition "it is not true that the sky is blue," and the negation of "$2 + 2 = 4$" is "$2 + 2 \neq 4$". Negation is a unary operator, which is a transformation of one proposition into another. Thus, since $A$ is a proposition, $\neg A$ is also a proposition.

Related to the concept of negation is the law of noncontradiction, which says that a proposition is either true or false, but not both. Thus for any proposition $A$, it is always the case that either $A$ is true or $\neg A$ is true, but it is never true that $A$ and $\neg A$ are both true or both false.

Conjunction and Disjunction

Propositions may be combined using the two binary operators conjunction and disjunction, known more familiarly as "and" and "or". If $A$ and $B$ are logical propositions, then the expression "$A$ and $B$" is itself a proposition, called the conjunction of $A$ and $B$, and it is true only when $A$ and $B$ are both true. If either or both are false, then their conjunction is also false. The expression "$A$ or $B$" is also a proposition, called the disjunction of $A$ and $B$, and it is true if $A$ is true, $B$ is true, or both are true. In other words, the disjunction is only false if both $A$ and $B$ are false.

Conjunctions and disjunctions are typically written with the words "and" and "or", but are sometimes expressed in shorthand using the symbols $\land$ and $\lor$, respectively.

Equality

Two propositions are logically equal, or simply equal, if they have the same truth value. To denote the equality of two propositions $A$ and $B$, we write $A = B$.

The third law of logic we consider is the law of identity, which states that every proposition is equal to itself. Namely, for every proposition $A$, it is true that $A = A$. Logical equality also has the property of symmetry, where $A = B$ is identical to stating $B = A$. Likewise, equality is also transitive, such that if $A = B$ and $B = C$, then $A = C$.

Predicates and Truth Tables

In the preceding sections, the propositions $A$ and $B$ were combined to make new propositions such as $A \land B$. The latter combinations we call compound propositions, for they are propositions made out of propositions. The input propositions are called atomic propositions, since they are not made out of other propositions.

How do we tell whether two compound propositions regarding the same atomic propositions are equal? The simplest answer is simply to evaluate the two given the truth values of the inputs and see if they are equal. However, this is not very satisfying, since what we are really concerned about is whether two compound propositions are always true given all possible values of the inputs. In this regard, we need to introduce the concept of a predicate. A predicate is a compound proposition whose atomic propositions are left as variables, or propositions whose truth value we have not yet determined. More loosely, predicates are simply functions of propositions. We can express predicates using familiar function notation. For example, the conjunction of two propositions we may express as the predicate $P(A, B) = A \land B$, and the disjunction of two propositions we may express as the predicate $Q(A, B) = A \lor B.$

Let's rephrase our original question - how can we tell if two logical predicates are equal? The solution is to use a truth table, which is a table listing all possible combinations of true or false for all the atomic propositions. If the truth tables for both predicates are identical, then the two predicates are equal. For brevity, true is abbreviated with a $T$, and false is abbreviated with an $F$.

For example, here is the truth table for negation:

$A$	$\neg A$
$T$	$F$
$F$	$T$

Clearly, $A$ and $\neg A$ are not equal.

Likewise, here is the truth table for $A$, $B$, $A \land B$, and $B \lor B:$

$A$	$B$	$A \land B$	$A \lor B$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$T$
$F$	$T$	$F$	$T$
$F$	$F$	$F$	$F$

As we might expect, $A \land B$ is not in general equal to $A \lor B$.

In the problems below, you will use truth tables to prove several fundamental properties of logic.