Tagged Questions

This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

25 views

61 views

Deducing the existence of particular functions $\mathbb{N}\longrightarrow\mathbb{Q}$ in the context of Tom Leinster's “Rethinking Set Theory”

This question concerns the set theory given by Tom Leinster in his paper "Rethinking Set Theory," available here: http://arxiv.org/abs/1212.6543 In this paper, axioms for set theory are given in the ...
59 views

How can I prove that these sets are countable infinite?

I am very new to proofs so please excuse any trivial errors. In lecture we were told that: A set $\mathbb S$ is called finite if there exists a one-to-one mapping (bijective mapping) between ...
1k views

Real numbers as element of a universe

defn. A universe is a set $U$ such that: $x\in u\in U\Rightarrow x\in U$ $u\in U$ and $v\in U$ imply $\left\{u,v\right\}, \langle u,v\rangle, u\times v\in U$ $x\in U\Rightarrow \mathcal{P}(x)$ and ...
24 views

Show that $\bigcup_{n=1}^\infty A_n= B_1 \backslash \bigcap_{n=1}^\infty B_n$

Let $\{B_n\}$ be a decreasing set $B_1 \supseteq B_2 \supseteq B_3 \supseteq ....$ Define $A_n = B_1 \backslash B_n$ i.e. $A_1 = \varnothing, A_2 = B_1 \backslash B_2$ If we imagine $\{B_n\}$ as a ...
27 views

Is it possible to define a set $S=\{ x \ |\ 1<x \le 1\}$?

I was wondering what would happen if I defined a set $S$ like this $S=\{ x\ | \ 1<x \le 1\}$. My main question would be if defining $S$ like that would be valid in set theory or if it is ...
31 views

How to phrase a proof of a function from a set A to a set B

Here is a problem: Let $f \subseteq A \times B$ be a function. In many situations you may want to restrict the domain of $f$ or expand its range. If $C \subseteq A$ then define the restriction of $f$ ...
23 views

finding counterexample for identity of sets

Let $A_i,B_i,C_j,D_j$ be sets. I am wondering if the equation $$\bigcup_{i\in I}(A_i\times B_i) \cap \bigcup_{j\in J}(C_j\times D_j)=\bigcup_{i\in I,j\in J}(A_i\cap C_j)\times (B_i\cap D_j)$$ holds. ...
30 views

set theory simplificaiton (laws of set theory)

I am relatively new to set theory,and I have to simplifiy this $$(Y \setminus X) \cap X$$ I'm stuck, can anyone help me.
25 views

minmum number of subsets of $\{1, 2, 3, … , n\}$, each of cardinality $r$, required such that their intersection is $\{1, 2, 3, … , m\}$

Let $M = \{1, 2, 3, ... , m\}$ and $N = \{1, 2, 3, ... , n\}$ be sets with $m < n$. Let $r \in \{1, ... , n\}$, with $m < r$. What is the minmum number of subsets of $N$, each of ...
29 views

Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive.

I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for. Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive ...
32 views

A = { x:x²=1, x is integer} How to get -1?

A = { x:x²=1, x is integer} How to get -1? The answer is -1 and 1. 1² = 1 But where -1 come from?
39 views

How to prove something is an equivalence class?

I don't understand equivalence class and representative function: http://www.cdhmhome.com/uic/math215/S.pdf , I'm looking at examples 37, 1-7 and have already determined which ones are equivalence ...
34 views

Is there a continuous function $f:X\rightarrow Y$ such that $f\big(\cap_{i\in I} A_i) \neq \cap_{i\in I}f\big(A_i)$

Is there a continuous function $f:X\rightarrow Y$ such that $$f\big(\cap_{i\in I} A_i) \neq \cap_{i\in I}f\big(A_i)$$ Where $A_i\subseteq X$ and $I$ is an arbitrary index set. I can easily find a ...
33 views

I'm looking for a good book on FOL and set theory.

I finally decided to really learn some axiomatic set theory, at least the basics. I've studied a bit of FOL, but a review would be nice. In short, I'm looking for a book that focuses on $\sf ZFC$ or ...
56 views

27 views

Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
31 views

Equivalence Relations and Cardinality

I'm looking at the question below from a past paper: What is an equivalence relation? Say that two sets $X$ and $Y$ are related via the relation $\rho$ if $X$ and $Y$ have the same cardinality. Prove ...
28 views

Clarification needed for a set notation

I have a question with regards to this problem: Let $S = \{1,2,3,4,5,6\}$ and let $P(A): A \cap \{2,4,6\} = \emptyset$ and $Q(A): A \neq \emptyset$ be open sentences over the domain $\mathcal{P}(S)$. ...
86 views

Given $3$ sets if $A \cap B = A \cap C$. Is $B=C$? [closed]

I've been trying to solve this question for a while but I just seem to be missing something. Let $A$, $B$ and $C$ be three sets. If $A \cap B = A \cap C$ Is $B=C$ ?
21 views

10 views

Let $A$ be an infinite set and let $B$ be a set such that $A$ is equinumerous to a subset of $B$. Then, $B$ is infinite.

To me, the proof is as simple as this: Let $C\subset B$ such that $A\sim C$. Then, as $A$ is infinite, we have that $C$ is infinite. Thus, as $C\subset B$, it must be that $B$ is infinite. Thus, $B$ ...
24 views

How many antisymmetrical relations are there on a set $B =\{ 1,2,3\}$? [duplicate]

How many antisymmetrical relations are there on Set $B$ if Set $B = \{1,2,3\}$? I believe its three?
28 views

What is meaning of canonical form of a set?

Let A{1,2,3}, B1={1,2}, B2={2,3}. Find minset canonical form of B1 and B2. We know minsets generated by B1 & B2 are A1 = B1 \cap B2^{c} A2 = B1 \cap B2 A3 = B1^{c} \cap B2 A4 = B1^{c}\cap B2^{c} ...
21 views

Is this reflexive, symmetric, antisymmetric or transitive?

Set A contains all points $(x, y)$ on a coordinate plane. The relation $R$ is defined as: point $(x_1,y_1)$ is related to point $(x_2,y_2)$, if $y_1=y_2$. Is this set (A) reflexive, symmetric, ...
39 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
22 views

Injective: In what circumstances would there be less than one pre-image of an image?

I am trying to get my head around the different types of function in set theory. In the definition of injective where: if (x',y) is in f and (x'',y) is in f, then x'= x'' in other words y has no ...
34 views

Sets and Universes

A universe is a set $\mathcal{U}$ such that: 1) $x\in\mathcal{U}$ and $y\in x$ implies $y\in\mathcal{U}$ 2) $I\in\mathcal{U}$ and $x_i\in\mathcal{U}$ for every $i\in I$ implies ...
22 views

Can we use the terms 'class of sets' and 'family of sets' interchangeably?

I read in pg-4, Introduction to Topology and Modern Analysis by Simmons that class refers to a set of sets while family refers to a set of classes. I formulated an example for the same - if points are ...
20 views

Is it true that if $cl(S) = int(S) \cup \partial (S)$ and $cl(S) = S \cup \partial (S)$ then $int(S) = S$ which means $S$ is open?

Like the title says, I know: $cl(S) = int(S) \cup \partial (S)$ But also; $cl(S) = S \cup \partial (S)$ But then $S = int(S)$ which is only true if $S$ is an open set. Where is this limitation ...
17 views

Let $X, Y$ be topological spaces and let A ∈ B($X$) (Borel $\sigma$ algebra on $X$), B ∈ B($Y$). How to show that A × B ∈ B($X\times Y$)?

Let X be a topological space. All that I know is Borel $\sigma$ algebra on X is the smallest $\sigma$ algebra generated by $T_X$ i.e. set of all open sets in X. Is there any other characterization of ...
624 views

Is directed set countable, if for each element there are only finitely many smaller ones?

A directed set is a pair $(A,\leq)$ where $\leq$ is a reflexive, transitive relation such that for any $x,y\in A$ we have some $z$ such that $x,y\leq z$. (This comes up when dealing with categorical ...
36 views

Standard notation for 'same' function with different ranges

Does anyone know of a standard notation for the situation when we want to define the 'same' function but on a larger or smaller range. More precisely, if $$f:A \to B$$ is a function and $C$ contains ...
18 views

Comparability of a set and a subset of power set.

It's well known that for any set $A$, $A < P(A)$. But now, I have some question that, WITHOUT AC, can we guarantee that $A \leq X$ or $X \leq A$ whenever $X \subseteq P(A)$? Thank you.
The number $\binom{8}{4}$ is equal to the number of subsets of size 4 of the set $\{1, \dots, 8\}$
I can't seem to work around this problem... Let $n$ and $m$ be two positive integers. $F$ is the set of functions from {1,..,n} to {1,...,m}. We define the relation $R$ as: $f R g$ if and only if ...