Set Theory and Mathematical Logic Flashcards (58 cards)

What is a statement in logic?

A sentence with a truth value of true or false.

When is the negation $\neg A$ true?

When $A$ is false.

When is the conjunction $A \land B$ true?

When both $A$ and $B$ are true.

When is the disjunction $A \lor B$ false?

When both $A$ and $B$ are false.

What does $A \Rightarrow B$ mean?

Whenever $A$ is true, $B$ is true.

In $A \Rightarrow B$, what is $A$ called?

The hypothesis.

What is the converse of $A \Rightarrow B$?

$B \Rightarrow A$.

What does $A \Leftrightarrow B$ mean?

Both $A \Rightarrow B$ and $B \Rightarrow A$ hold.

In a direct proof of A ⇒ B, what is assumed and what is deduced?

Assume A is true and deduce that B is true.

In induction from k, what base case must be proved?

P(k).

What implication must be proved at each step of induction from k?

P(t) implies P(t+1) for every t ≥ k.

What is a set?

A collection of objects whose membership can be determined and that is not an element of itself.

What does the empty set contain?

No elements.

What does the existential quantifier $\exists$ mean?

At least one element satisfies a property.

What does the universal quantifier $\forall$ mean?

Every element satisfies a property.

When is F a subset of E?

Every element of F is an element of E.

Which two subsets does every set E contain?

The empty set and E itself.

When are sets E and F equal?

Each element of either set belongs to the other set.

What is the power set P(E)?

The set of all subsets of E, including ∅ and E.

Which elements belong to the union of sets E and F?

Elements belonging to E or F.

Which elements belong to the intersection of sets E and F?

Elements belonging to both E and F.

Which elements belong to the set difference $E \setminus F$?

Elements of $E$ that do not belong to $F$.

How are $A$ and its complement in $E$ related when $A \subseteq E$?

They are disjoint, and their union is $E$.

What is the complement of $A \cup B$ for subsets of $E$?

The intersection of the complements of $A$ and $B$.

What is the complement of $A \cap B$ for subsets of $E$?

The union of the complements of $A$ and $B$.

When are two ordered n-tuples equal?

When their corresponding components are equal.

Which tuples belong to the Cartesian product $E_1 \times \cdots \times E_n$?

Tuples whose $i$-th component belongs to $E_i$.

When is the Cartesian product $E_1 \times \cdots \times E_n$ empty?

When any factor is empty.

For sets $A$ and $B$, when does $(x,y)$ belong to $A \times B$?

When $x \in A$ and $y \in B$.

What does a family of sets indexed by a nonempty set assign to each index?

A set.

When does an element belong to the union of a family of sets?

When it belongs to at least one family member.

When does an element belong to the intersection of a family of sets?

When it belongs to every family member.

What does the axiom of choice guarantee for a nonempty family of nonempty pairwise disjoint sets?

A set intersecting each family member in a singleton.

What does the principle of non-contradiction say about $A \land \neg A$?

It is always false.

What does the principle of excluded middle say about $A \lor \neg A$?

It is always true.

What is a tautology?

A statement that is always true.

In $A \Leftrightarrow B$, what does $A \Rightarrow B$ say about $A$?

$A$ is a sufficient condition for $B$.

In $A \Leftrightarrow B$, what does $B \Rightarrow A$ say about $A$?

$A$ is a necessary condition for $B$.

What is the contrapositive of $A \Rightarrow B$?

$\neg B \Rightarrow \neg A$.

What is the negation of $A \Rightarrow B$?

$A \land \neg B$.

In proof by contradiction, what contradiction is derived from assuming A is false?

A statement that is both true and false.

What conclusion does proof by contradiction draw after deriving a contradiction from assuming A is false?

A is true.

Which statement is proved by contraposition to establish A ⇒ B?

¬B ⇒ ¬A.

In the second form of induction from k, what condition implies P(t+1)?

P(s) holds for every s from k through t.

What is the sum of the first n positive integers for n ≥ 1?

$\frac{n(n+1)}{2}$

How is a set written in extension?

By listing its elements.

How is a set written in comprehension?

By specifying a property its elements satisfy.

Why is $\{\emptyset\}$ not empty?

Its sole element is the empty set.

What follows from A ⊆ B and B ⊆ C?

A ⊆ C.

What defines a proper subset of E?

A subset of E that is neither equal to E nor empty.

When are two sets disjoint?

When their intersection is empty.

What commutative property applies to union and intersection?

Changing the order of two sets leaves either operation unchanged.

What associative property applies to union and intersection?

Changing the grouping of three sets leaves either operation unchanged.

How does intersection distribute over union?

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

How does union distribute over intersection?

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

What is the complement of the complement of $A$ within $E$?

$A$.

Which ordered n-tuples belong to the diagonal of $A^n$?

Those whose components are all equal.

When is a family of sets pairwise disjoint?

When sets at distinct indices have empty intersection.